lib/fribidi-run.c

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