lib/fribidi-run.c

   1 /* FriBidi
   2  * fribidi-run.c - text run data type
   3  *
   4  * Authors:
   5  *   Behdad Esfahbod, 2001, 2002, 2004
   6  *   Dov Grobgeld, 1999, 2000, 2017
   7  *
   8  * Copyright (C) 2004 Sharif FarsiWeb, Inc
   9  * Copyright (C) 2001,2002 Behdad Esfahbod
  10  * Copyright (C) 1999,2000,2017 Dov Grobgeld
  11  *
  12  * This library is free software; you can redistribute it and/or
  13  * modify it under the terms of the GNU Lesser General Public
  14  * License as published by the Free Software Foundation; either
  15  * version 2.1 of the License, or (at your option) any later version.
  16  *
  17  * This library is distributed in the hope that it will be useful,
  18  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  19  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  20  * Lesser General Public License for more details.
  21  *
  22  * You should have received a copy of the GNU Lesser General Public License
  23  * along with this library, in a file named COPYING; if not, write to the
  24  * Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  25  * Boston, MA 02110-1301, USA
  26  *
  27  * For licensing issues, contact <fribidi.license@gmail.com>.
  28  */
  29
  30 #include "common.h"
  31
  32 #include <fribidi-bidi-types.h>
  33
  34 #include "run.h"
  35 #include "bidi-types.h"
  36
  37 FriBidiRun *
  38 new_run (
  39   void
  40 )
  41 {
  42   register FriBidiRun *run;
  43
  44   run = fribidi_malloc (sizeof (FriBidiRun));
  45
  46   if LIKELY
  47     (run)
  48     {
  49       run->len = run->pos = run->level = run->isolate_level = 0;
  50       run->next = run->prev = run->prev_isolate = run->next_isolate = NULL;
  51     }
  52   return run;
  53 }
  54
  55 FriBidiRun *
  56 new_run_list (
  57   void
  58 )
  59 {
  60   register FriBidiRun *run;
  61
  62   run = new_run ();
  63
  64   if LIKELY
  65     (run)
  66     {
  67       run->type = FRIBIDI_TYPE_SENTINEL;
  68       run->level = FRIBIDI_SENTINEL;
  69       run->pos = FRIBIDI_SENTINEL;
  70       run->len = FRIBIDI_SENTINEL;
  71       run->next = run->prev = run;
  72     }
  73
  74   return run;
  75 }
  76
  77 void
  78 free_run_list (
  79   FriBidiRun *run_list
  80 )
  81 {
  82   if (!run_list)
  83     return;
  84
  85   fribidi_validate_run_list (run_list);
  86
  87   {
  88     register FriBidiRun *pp;
  89
  90     pp = run_list;
  91     pp->prev->next = NULL;
  92     while LIKELY
  93       (pp)
  94       {
  95         register FriBidiRun *p;
  96
  97         p = pp;
  98         pp = pp->next;
  99         fribidi_free (p);
 100       };
 101   }
 102 }
 103
 104
 105 FriBidiRun *
 106 run_list_encode_bidi_types (
 107   /* input */
 108   const FriBidiCharType *bidi_types,
 109   const FriBidiBracketType *bracket_types,
 110   const FriBidiStrIndex len
 111 )
 112 {
 113   FriBidiRun *list, *last;
 114   register FriBidiRun *run = NULL;
 115   FriBidiStrIndex i;
 116
 117   fribidi_assert (bidi_types);
 118
 119   /* Create the list sentinel */
 120   list = new_run_list ();
 121   if UNLIKELY
 122     (!list) return NULL;
 123   last = list;
 124
 125   /* Scan over the character types */
 126   for (i = 0; i < len; i++)
 127     {
 128       register FriBidiCharType char_type = bidi_types[i];
 129       register FriBidiBracketType bracket_type = FRIBIDI_NO_BRACKET;
 130       if (bracket_types)
 131         bracket_type = bracket_types[i];
 132
 133       if (char_type != last->type
 134           || bracket_type != FRIBIDI_NO_BRACKET /* Always separate bracket into single char runs! */
 135           || last->bracket_type != FRIBIDI_NO_BRACKET
 136           || FRIBIDI_IS_ISOLATE(char_type)
 137           )
 138         {
 139           run = new_run ();
 140           if UNLIKELY
 141             (!run) break;
 142           run->type = char_type;
 143           run->pos = i;
 144           last->len = run->pos - last->pos;
 145           last->next = run;
 146           run->prev = last;
 147           run->bracket_type = bracket_type;
 148           last = run;
 149         }
 150     }
 151
 152   /* Close the circle */
 153   last->len = len - last->pos;
 154   last->next = list;
 155   list->prev = last;
 156
 157   if UNLIKELY
 158     (!run)
 159     {
 160       /* Memory allocation failed */
 161       free_run_list (list);
 162       return NULL;
 163     }
 164
 165   fribidi_validate_run_list (list);
 166
 167   return list;
 168 }
 169
 170 /* override the run list 'base', with the runs in the list 'over', to
 171    reinsert the previously-removed explicit codes (at X9) from
 172    'explicits_list' back into 'type_rl_list' for example. This is used at the
 173    end of I2 to restore the explicit marks, and also to reset the character
 174    types of characters at L1.
 175
 176    it is assumed that the 'pos' of the first element in 'base' list is not
 177    more than the 'pos' of the first element of the 'over' list, and the
 178    'pos' of the last element of the 'base' list is not less than the 'pos'
 179    of the last element of the 'over' list. these two conditions are always
 180    satisfied for the two usages mentioned above.
 181
 182    Note:
 183      frees the over list.
 184
 185    Todo:
 186      use some explanatory names instead of p, q, ...
 187      rewrite comment above to remove references to special usage.
 188 */
 189 fribidi_boolean
 190 shadow_run_list (
 191   /* input */
 192   FriBidiRun *base,
 193   FriBidiRun *over,
 194   fribidi_boolean preserve_length
 195 )
 196 {
 197   register FriBidiRun *p = base, *q, *r, *s, *t;
 198   register FriBidiStrIndex pos = 0, pos2;
 199   fribidi_boolean status = false;
 200
 201   fribidi_validate_run_list (base);
 202   fribidi_validate_run_list (over);
 203
 204   for_run_list (q, over)
 205   {
 206     if UNLIKELY
 207       (!q->len || q->pos < pos) continue;
 208     pos = q->pos;
 209     while (p->next->type != FRIBIDI_TYPE_SENTINEL && p->next->pos <= pos)
 210       p = p->next;
 211     /* now p is the element that q must be inserted 'in'. */
 212     pos2 = pos + q->len;
 213     r = p;
 214     while (r->next->type != FRIBIDI_TYPE_SENTINEL && r->next->pos < pos2)
 215       r = r->next;
 216     if (preserve_length)
 217       r->len += q->len;
 218     /* now r is the last element that q affects. */
 219     if LIKELY
 220       (p == r)
 221       {
 222         /* split p into at most 3 intervals, and insert q in the place of
 223            the second interval, set r to be the third part. */
 224         /* third part needed? */
 225         if (p->pos + p->len > pos2)
 226           {
 227             r = new_run ();
 228             if UNLIKELY
 229               (!r) goto out;
 230             p->next->prev = r;
 231             r->next = p->next;
 232             r->level = p->level;
 233             r->isolate_level = p->isolate_level;
 234             r->type = p->type;
 235             r->len = p->pos + p->len - pos2;
 236             r->pos = pos2;
 237           }
 238         else
 239           r = r->next;
 240
 241         if LIKELY
 242           (p->pos + p->len >= pos)
 243           {
 244             /* first part needed? */
 245             if (p->pos < pos)
 246               /* cut the end of p. */
 247               p->len = pos - p->pos;
 248             else
 249               {
 250                 t = p;
 251                 p = p->prev;
 252                 fribidi_free (t);
 253               }
 254           }
 255       }
 256     else
 257       {
 258         if LIKELY
 259           (p->pos + p->len >= pos)
 260           {
 261             /* p needed? */
 262             if (p->pos < pos)
 263               /* cut the end of p. */
 264               p->len = pos - p->pos;
 265             else
 266               p = p->prev;
 267           }
 268
 269         /* r needed? */
 270         if (r->pos + r->len > pos2)
 271           {
 272             /* cut the beginning of r. */
 273             r->len = r->pos + r->len - pos2;
 274             r->pos = pos2;
 275           }
 276         else
 277           r = r->next;
 278
 279         /* remove the elements between p and r. */
 280         for (s = p->next; s != r;)
 281           {
 282             t = s;
 283             s = s->next;
 284             fribidi_free (t);
 285           }
 286       }
 287     /* before updating the next and prev runs to point to the inserted q,
 288        we must remember the next element of q in the 'over' list.
 289      */
 290     t = q;
 291     q = q->prev;
 292     delete_node (t);
 293     p->next = t;
 294     t->prev = p;
 295     t->next = r;
 296     r->prev = t;
 297   }
 298   status = true;
 299
 300   fribidi_validate_run_list (base);
 301
 302 out:
 303   free_run_list (over);
 304
 305   return status;
 306 }
 307
 308 #ifdef DEBUG
 309
 310 void
 311 fribidi_validate_run_list (
 312   FriBidiRun *run_list          /* input run list */
 313 )
 314 {
 315   register FriBidiRun *q;
 316
 317   fribidi_assert (run_list);
 318   fribidi_assert (run_list->next);
 319   fribidi_assert (run_list->next->prev == run_list);
 320   fribidi_assert (run_list->type == FRIBIDI_TYPE_SENTINEL);
 321   for_run_list (q, run_list)
 322   {
 323     fribidi_assert (q->next);
 324     fribidi_assert (q->next->prev == q);
 325   }
 326   fribidi_assert (q == run_list);
 327 }
 328
 329 #endif /* !DEBUG */
 330
 331 /* Editor directions:
 332  * vim:textwidth=78:tabstop=8:shiftwidth=2:autoindent:cindent
 333  */