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 */