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 (size: 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 (ptr: 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 (run_list: list); |
162 | return NULL; |
163 | } |
164 | |
165 | fribidi_validate_run_list (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 (run_list: base); |
202 | fribidi_validate_run_list (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 (ptr: 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 (ptr: 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 (run_list: base); |
301 | |
302 | out: |
303 | free_run_list (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 | */ |
334 | |