Mercurial > hg > xemacs-beta
comparison src/rangetab.c @ 5495:1f0b15040456
Merge.
author | Aidan Kehoe <kehoea@parhasard.net> |
---|---|
date | Sun, 01 May 2011 18:44:03 +0100 |
parents | 308d34e9f07d |
children | 58b38d5b32d0 |
comparison
equal
deleted
inserted
replaced
5494:861f2601a38b | 5495:1f0b15040456 |
---|---|
2 Copyright (C) 1995 Sun Microsystems, Inc. | 2 Copyright (C) 1995 Sun Microsystems, Inc. |
3 Copyright (C) 1995, 2002, 2004, 2005, 2010 Ben Wing. | 3 Copyright (C) 1995, 2002, 2004, 2005, 2010 Ben Wing. |
4 | 4 |
5 This file is part of XEmacs. | 5 This file is part of XEmacs. |
6 | 6 |
7 XEmacs is free software; you can redistribute it and/or modify it | 7 XEmacs is free software: you can redistribute it and/or modify it |
8 under the terms of the GNU General Public License as published by the | 8 under the terms of the GNU General Public License as published by the |
9 Free Software Foundation; either version 2, or (at your option) any | 9 Free Software Foundation, either version 3 of the License, or (at your |
10 later version. | 10 option) any later version. |
11 | 11 |
12 XEmacs is distributed in the hope that it will be useful, but WITHOUT | 12 XEmacs is distributed in the hope that it will be useful, but WITHOUT |
13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or | 13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or |
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | 14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
15 for more details. | 15 for more details. |
16 | 16 |
17 You should have received a copy of the GNU General Public License | 17 You should have received a copy of the GNU General Public License |
18 along with XEmacs; see the file COPYING. If not, write to | 18 along with XEmacs. If not, see <http://www.gnu.org/licenses/>. */ |
19 the Free Software Foundation, Inc., 59 Temple Place - Suite 330, | |
20 Boston, MA 02111-1307, USA. */ | |
21 | 19 |
22 /* Synched up with: Not in FSF. */ | 20 /* Synched up with: Not in FSF. */ |
23 | 21 |
24 /* Written by Ben Wing, August 1995. */ | 22 /* Written by Ben Wing, August 1995. */ |
25 | 23 |
88 mark_range_table (Lisp_Object obj) | 86 mark_range_table (Lisp_Object obj) |
89 { | 87 { |
90 Lisp_Range_Table *rt = XRANGE_TABLE (obj); | 88 Lisp_Range_Table *rt = XRANGE_TABLE (obj); |
91 int i; | 89 int i; |
92 | 90 |
93 for (i = 0; i < Dynarr_length (rt->entries); i++) | 91 for (i = 0; i < gap_array_length (rt->entries); i++) |
94 mark_object (Dynarr_at (rt->entries, i).val); | 92 mark_object (rangetab_gap_array_at (rt->entries, i).val); |
95 | 93 |
96 return Qnil; | 94 return Qnil; |
97 } | 95 } |
98 | 96 |
99 static void | 97 static void |
102 { | 100 { |
103 Lisp_Range_Table *rt = XRANGE_TABLE (obj); | 101 Lisp_Range_Table *rt = XRANGE_TABLE (obj); |
104 int i; | 102 int i; |
105 | 103 |
106 if (print_readably) | 104 if (print_readably) |
107 write_fmt_string_lisp (printcharfun, "#s(range-table type %s data (", | 105 write_fmt_string_lisp (printcharfun, "#s(range-table :type %s :data (", |
108 1, range_table_type_to_symbol (rt->type)); | 106 1, range_table_type_to_symbol (rt->type)); |
109 else | 107 else |
110 write_ascstring (printcharfun, "#<range-table "); | 108 write_ascstring (printcharfun, "#<range-table "); |
111 for (i = 0; i < Dynarr_length (rt->entries); i++) | 109 for (i = 0; i < gap_array_length (rt->entries); i++) |
112 { | 110 { |
113 struct range_table_entry *rte = Dynarr_atp (rt->entries, i); | 111 struct range_table_entry rte = rangetab_gap_array_at (rt->entries, i); |
114 int so, ec; | 112 int so, ec; |
115 if (i > 0) | 113 if (i > 0) |
116 write_ascstring (printcharfun, " "); | 114 write_ascstring (printcharfun, " "); |
117 switch (rt->type) | 115 switch (rt->type) |
118 { | 116 { |
122 case RANGE_START_OPEN_END_CLOSED: so = 1; ec = 1; break; | 120 case RANGE_START_OPEN_END_CLOSED: so = 1; ec = 1; break; |
123 default: ABORT (); so = 0, ec = 0; break; | 121 default: ABORT (); so = 0, ec = 0; break; |
124 } | 122 } |
125 write_fmt_string (printcharfun, "%c%ld %ld%c ", | 123 write_fmt_string (printcharfun, "%c%ld %ld%c ", |
126 print_readably ? '(' : so ? '(' : '[', | 124 print_readably ? '(' : so ? '(' : '[', |
127 (long) (rte->first - so), | 125 (long) (rte.first - so), |
128 (long) (rte->last - ec), | 126 (long) (rte.last - ec), |
129 print_readably ? ')' : ec ? ']' : ')' | 127 print_readably ? ')' : ec ? ']' : ')' |
130 ); | 128 ); |
131 print_internal (rte->val, printcharfun, 1); | 129 print_internal (rte.val, printcharfun, 1); |
132 } | 130 } |
133 if (print_readably) | 131 if (print_readably) |
134 write_ascstring (printcharfun, "))"); | 132 write_ascstring (printcharfun, "))"); |
135 else | 133 else |
136 write_fmt_string (printcharfun, " 0x%x>", rt->header.uid); | 134 write_fmt_string (printcharfun, " 0x%x>", LISP_OBJECT_UID (obj)); |
137 } | 135 } |
138 | 136 |
139 static int | 137 static int |
140 range_table_equal (Lisp_Object obj1, Lisp_Object obj2, int depth, int foldcase) | 138 range_table_equal (Lisp_Object obj1, Lisp_Object obj2, int depth, int foldcase) |
141 { | 139 { |
142 Lisp_Range_Table *rt1 = XRANGE_TABLE (obj1); | 140 Lisp_Range_Table *rt1 = XRANGE_TABLE (obj1); |
143 Lisp_Range_Table *rt2 = XRANGE_TABLE (obj2); | 141 Lisp_Range_Table *rt2 = XRANGE_TABLE (obj2); |
144 int i; | 142 int i; |
145 | 143 |
146 if (Dynarr_length (rt1->entries) != Dynarr_length (rt2->entries)) | 144 if (gap_array_length (rt1->entries) != gap_array_length (rt2->entries)) |
147 return 0; | 145 return 0; |
148 | 146 |
149 for (i = 0; i < Dynarr_length (rt1->entries); i++) | 147 for (i = 0; i < gap_array_length (rt1->entries); i++) |
150 { | 148 { |
151 struct range_table_entry *rte1 = Dynarr_atp (rt1->entries, i); | 149 struct range_table_entry *rte1 = |
152 struct range_table_entry *rte2 = Dynarr_atp (rt2->entries, i); | 150 rangetab_gap_array_atp (rt1->entries, i); |
151 struct range_table_entry *rte2 = | |
152 rangetab_gap_array_atp (rt2->entries, i); | |
153 | 153 |
154 if (rte1->first != rte2->first | 154 if (rte1->first != rte2->first |
155 || rte1->last != rte2->last | 155 || rte1->last != rte2->last |
156 || !internal_equal_0 (rte1->val, rte2->val, depth + 1, foldcase)) | 156 || !internal_equal_0 (rte1->val, rte2->val, depth + 1, foldcase)) |
157 return 0; | 157 return 0; |
159 | 159 |
160 return 1; | 160 return 1; |
161 } | 161 } |
162 | 162 |
163 static Hashcode | 163 static Hashcode |
164 range_table_entry_hash (struct range_table_entry *rte, int depth) | 164 range_table_entry_hash (struct range_table_entry *rte, int depth, |
165 { | 165 Boolint equalp) |
166 return HASH3 (rte->first, rte->last, internal_hash (rte->val, depth + 1)); | 166 { |
167 return HASH3 (rte->first, rte->last, | |
168 internal_hash (rte->val, depth + 1, equalp)); | |
167 } | 169 } |
168 | 170 |
169 static Hashcode | 171 static Hashcode |
170 range_table_hash (Lisp_Object obj, int depth) | 172 range_table_hash (Lisp_Object obj, int depth, Boolint equalp) |
171 { | 173 { |
172 Lisp_Range_Table *rt = XRANGE_TABLE (obj); | 174 Lisp_Range_Table *rt = XRANGE_TABLE (obj); |
173 int i; | 175 int i; |
174 int size = Dynarr_length (rt->entries); | 176 int size = gap_array_length (rt->entries); |
175 Hashcode hash = size; | 177 Hashcode hash = size; |
176 | 178 |
177 /* approach based on internal_array_hash(). */ | 179 /* approach based on internal_array_hash(). */ |
178 if (size <= 5) | 180 if (size <= 5) |
179 { | 181 { |
180 for (i = 0; i < size; i++) | 182 for (i = 0; i < size; i++) |
181 hash = HASH2 (hash, | 183 hash = HASH2 (hash, |
182 range_table_entry_hash (Dynarr_atp (rt->entries, i), | 184 range_table_entry_hash |
183 depth)); | 185 (rangetab_gap_array_atp (rt->entries, i), depth, equalp)); |
184 return hash; | 186 return hash; |
185 } | 187 } |
186 | 188 |
187 /* just pick five elements scattered throughout the array. | 189 /* just pick five elements scattered throughout the array. |
188 A slightly better approach would be to offset by some | 190 A slightly better approach would be to offset by some |
189 noise factor from the points chosen below. */ | 191 noise factor from the points chosen below. */ |
190 for (i = 0; i < 5; i++) | 192 for (i = 0; i < 5; i++) |
191 hash = HASH2 (hash, range_table_entry_hash (Dynarr_atp (rt->entries, | 193 hash = HASH2 (hash, |
192 i*size/5), | 194 range_table_entry_hash |
193 depth)); | 195 (rangetab_gap_array_atp (rt->entries, i*size/5), |
196 depth, equalp)); | |
194 return hash; | 197 return hash; |
195 } | 198 } |
199 | |
200 #ifndef NEW_GC | |
201 | |
202 /* #### This leaks memory under NEW_GC. To fix this, convert to Lisp object | |
203 gap array. */ | |
204 | |
205 static void | |
206 finalize_range_table (Lisp_Object obj) | |
207 { | |
208 Lisp_Range_Table *rt = XRANGE_TABLE (obj); | |
209 if (rt->entries) | |
210 { | |
211 if (!DUMPEDP (rt->entries)) | |
212 free_gap_array (rt->entries); | |
213 rt->entries = 0; | |
214 } | |
215 } | |
216 | |
217 #endif /* not NEW_GC */ | |
196 | 218 |
197 static const struct memory_description rte_description_1[] = { | 219 static const struct memory_description rte_description_1[] = { |
198 { XD_LISP_OBJECT, offsetof (range_table_entry, val) }, | 220 { XD_LISP_OBJECT, offsetof (range_table_entry, val) }, |
199 { XD_END } | 221 { XD_END } |
200 }; | 222 }; |
202 static const struct sized_memory_description rte_description = { | 224 static const struct sized_memory_description rte_description = { |
203 sizeof (range_table_entry), | 225 sizeof (range_table_entry), |
204 rte_description_1 | 226 rte_description_1 |
205 }; | 227 }; |
206 | 228 |
207 static const struct memory_description rted_description_1[] = { | 229 static const struct memory_description rtega_description_1[] = { |
208 XD_DYNARR_DESC (range_table_entry_dynarr, &rte_description), | 230 XD_GAP_ARRAY_DESC (&rte_description), |
209 { XD_END } | 231 { XD_END } |
210 }; | 232 }; |
211 | 233 |
212 static const struct sized_memory_description rted_description = { | 234 static const struct sized_memory_description rtega_description = { |
213 sizeof (range_table_entry_dynarr), | 235 0, rtega_description_1 |
214 rted_description_1 | |
215 }; | 236 }; |
216 | 237 |
217 static const struct memory_description range_table_description[] = { | 238 static const struct memory_description range_table_description[] = { |
218 { XD_BLOCK_PTR, offsetof (Lisp_Range_Table, entries), 1, | 239 { XD_BLOCK_PTR, offsetof (Lisp_Range_Table, entries), 1, |
219 { &rted_description } }, | 240 { &rtega_description } }, |
220 { XD_END } | 241 { XD_END } |
221 }; | 242 }; |
222 | 243 |
223 DEFINE_LRECORD_IMPLEMENTATION ("range-table", range_table, | 244 DEFINE_DUMPABLE_LISP_OBJECT ("range-table", range_table, |
224 1, /*dumpable-flag*/ | 245 mark_range_table, print_range_table, |
225 mark_range_table, print_range_table, 0, | 246 IF_OLD_GC (finalize_range_table), |
226 range_table_equal, range_table_hash, | 247 range_table_equal, range_table_hash, |
227 range_table_description, | 248 range_table_description, |
228 Lisp_Range_Table); | 249 Lisp_Range_Table); |
229 | 250 |
230 /************************************************************************/ | 251 /************************************************************************/ |
231 /* Range table operations */ | 252 /* Range table operations */ |
232 /************************************************************************/ | 253 /************************************************************************/ |
233 | 254 |
236 static void | 257 static void |
237 verify_range_table (Lisp_Range_Table *rt) | 258 verify_range_table (Lisp_Range_Table *rt) |
238 { | 259 { |
239 int i; | 260 int i; |
240 | 261 |
241 for (i = 0; i < Dynarr_length (rt->entries); i++) | 262 for (i = 0; i < gap_array_length (rt->entries); i++) |
242 { | 263 { |
243 struct range_table_entry *rte = Dynarr_atp (rt->entries, i); | 264 struct range_table_entry *rte = rangetab_gap_array_atp (rt->entries, i); |
244 assert (rte->last >= rte->first); | 265 assert (rte->last >= rte->first); |
245 if (i > 0) | 266 if (i > 0) |
246 assert (Dynarr_at (rt->entries, i - 1).last <= rte->first); | 267 assert (rangetab_gap_array_at (rt->entries, i - 1).last <= rte->first); |
247 } | 268 } |
248 } | 269 } |
249 | 270 |
250 #else | 271 #else |
251 | 272 |
252 #define verify_range_table(rt) | 273 #define verify_range_table(rt) |
253 | 274 |
254 #endif | 275 #endif |
255 | 276 |
256 /* Look up in a range table without the Dynarr wrapper. | 277 /* Locate the range table entry corresponding to the value POS, and return |
257 Used also by the unified range table format. */ | 278 it. If found, FOUNDP is set to 1 and the return value specifies an entry |
258 | 279 that encloses POS. Otherwise, FOUNDP is set to 0 and the return value |
259 static Lisp_Object | 280 specifies where an entry that encloses POS would be inserted. */ |
260 get_range_table (EMACS_INT pos, int nentries, struct range_table_entry *tab, | 281 |
261 Lisp_Object default_) | 282 static Elemcount |
262 { | 283 get_range_table_pos (Elemcount pos, Elemcount nentries, |
263 int left = 0, right = nentries; | 284 struct range_table_entry *tab, |
285 Elemcount gappos, Elemcount gapsize, | |
286 int *foundp) | |
287 { | |
288 Elemcount left = 0, right = nentries; | |
264 | 289 |
265 /* binary search for the entry. Based on similar code in | 290 /* binary search for the entry. Based on similar code in |
266 extent_list_locate(). */ | 291 extent_list_locate(). */ |
267 while (left != right) | 292 while (left != right) |
268 { | 293 { |
269 /* RIGHT might not point to a valid entry (i.e. it's at the end | 294 /* RIGHT might not point to a valid entry (i.e. it's at the end |
270 of the list), so NEWPOS must round down. */ | 295 of the list), so NEWPOS must round down. */ |
271 int newpos = (left + right) >> 1; | 296 Elemcount newpos = (left + right) >> 1; |
272 struct range_table_entry *entry = tab + newpos; | 297 struct range_table_entry *entry = |
298 tab + GAP_ARRAY_ARRAY_TO_MEMORY_POS_1 (newpos, gappos, gapsize); | |
273 if (pos >= entry->last) | 299 if (pos >= entry->last) |
274 left = newpos + 1; | 300 left = newpos + 1; |
275 else if (pos < entry->first) | 301 else if (pos < entry->first) |
276 right = newpos; | 302 right = newpos; |
277 else | 303 else |
278 return entry->val; | 304 { |
305 *foundp = 1; | |
306 return newpos; | |
307 } | |
308 } | |
309 | |
310 *foundp = 0; | |
311 return left; | |
312 } | |
313 | |
314 /* Look up in a range table without the gap array wrapper. | |
315 Used also by the unified range table format. */ | |
316 | |
317 static Lisp_Object | |
318 get_range_table (Elemcount pos, Elemcount nentries, | |
319 struct range_table_entry *tab, | |
320 Elemcount gappos, Elemcount gapsize, | |
321 Lisp_Object default_) | |
322 { | |
323 int foundp; | |
324 Elemcount entrypos = get_range_table_pos (pos, nentries, tab, gappos, | |
325 gapsize, &foundp); | |
326 if (foundp) | |
327 { | |
328 struct range_table_entry *entry = | |
329 tab + GAP_ARRAY_ARRAY_TO_MEMORY_POS_1 (entrypos, gappos, gapsize); | |
330 return entry->val; | |
279 } | 331 } |
280 | 332 |
281 return default_; | 333 return default_; |
282 } | 334 } |
283 | 335 |
330 there would be eight days. Similarly, there are 15 (= 20 - 5) elements in | 382 there would be eight days. Similarly, there are 15 (= 20 - 5) elements in |
331 the range [5, 20), but 16 in the range [5, 20]. | 383 the range [5, 20), but 16 in the range [5, 20]. |
332 */ | 384 */ |
333 (type)) | 385 (type)) |
334 { | 386 { |
335 Lisp_Range_Table *rt = ALLOC_LCRECORD_TYPE (Lisp_Range_Table, | 387 Lisp_Object obj = ALLOC_NORMAL_LISP_OBJECT (range_table); |
336 &lrecord_range_table); | 388 Lisp_Range_Table *rt = XRANGE_TABLE (obj); |
337 rt->entries = Dynarr_new (range_table_entry); | 389 rt->entries = make_gap_array (sizeof (struct range_table_entry), 0); |
338 rt->type = range_table_symbol_to_type (type); | 390 rt->type = range_table_symbol_to_type (type); |
339 return wrap_range_table (rt); | 391 return obj; |
340 } | 392 } |
341 | 393 |
342 DEFUN ("copy-range-table", Fcopy_range_table, 1, 1, 0, /* | 394 DEFUN ("copy-range-table", Fcopy_range_table, 1, 1, 0, /* |
343 Return a new range table which is a copy of RANGE-TABLE. | 395 Return a new range table which is a copy of RANGE-TABLE. |
344 It will contain the same values for the same ranges as RANGE-TABLE. | 396 It will contain the same values for the same ranges as RANGE-TABLE. |
345 The values will not themselves be copied. | 397 The values will not themselves be copied. |
346 */ | 398 */ |
347 (range_table)) | 399 (range_table)) |
348 { | 400 { |
349 Lisp_Range_Table *rt, *rtnew; | 401 Lisp_Range_Table *rt, *rtnew; |
402 Lisp_Object obj; | |
403 Elemcount i; | |
350 | 404 |
351 CHECK_RANGE_TABLE (range_table); | 405 CHECK_RANGE_TABLE (range_table); |
352 rt = XRANGE_TABLE (range_table); | 406 rt = XRANGE_TABLE (range_table); |
353 | 407 |
354 rtnew = ALLOC_LCRECORD_TYPE (Lisp_Range_Table, &lrecord_range_table); | 408 obj = ALLOC_NORMAL_LISP_OBJECT (range_table); |
355 rtnew->entries = Dynarr_new (range_table_entry); | 409 rtnew = XRANGE_TABLE (obj); |
410 rtnew->entries = make_gap_array (sizeof (struct range_table_entry), 0); | |
356 rtnew->type = rt->type; | 411 rtnew->type = rt->type; |
357 | 412 |
358 Dynarr_add_many (rtnew->entries, Dynarr_begin (rt->entries), | 413 for (i = 0; i < gap_array_length (rt->entries); i++) |
359 Dynarr_length (rt->entries)); | 414 rtnew->entries = |
360 return wrap_range_table (rtnew); | 415 gap_array_insert_els (rtnew->entries, i, |
416 rangetab_gap_array_atp (rt->entries, i), 1); | |
417 return obj; | |
361 } | 418 } |
362 | 419 |
363 DEFUN ("get-range-table", Fget_range_table, 2, 3, 0, /* | 420 DEFUN ("get-range-table", Fget_range_table, 2, 3, 0, /* |
364 Find value for position POS in RANGE-TABLE. | 421 Find value for position POS in RANGE-TABLE. |
365 If there is no corresponding value, return DEFAULT (defaults to nil). | 422 If there is no corresponding value, return DEFAULT (defaults to nil). |
371 CHECK_RANGE_TABLE (range_table); | 428 CHECK_RANGE_TABLE (range_table); |
372 rt = XRANGE_TABLE (range_table); | 429 rt = XRANGE_TABLE (range_table); |
373 | 430 |
374 CHECK_INT_COERCE_CHAR (pos); | 431 CHECK_INT_COERCE_CHAR (pos); |
375 | 432 |
376 return get_range_table (XINT (pos), Dynarr_length (rt->entries), | 433 return get_range_table (XINT (pos), gap_array_length (rt->entries), |
377 Dynarr_begin (rt->entries), default_); | 434 gap_array_begin (rt->entries, |
435 struct range_table_entry), | |
436 gap_array_gappos (rt->entries), | |
437 gap_array_gapsize (rt->entries), | |
438 default_); | |
378 } | 439 } |
379 | 440 |
380 static void | 441 static void |
381 external_to_internal_adjust_ends (enum range_table_type type, | 442 external_to_internal_adjust_ends (enum range_table_type type, |
382 EMACS_INT *first, EMACS_INT *last) | 443 EMACS_INT *first, EMACS_INT *last) |
412 EMACS_INT last, Lisp_Object val) | 473 EMACS_INT last, Lisp_Object val) |
413 { | 474 { |
414 int i; | 475 int i; |
415 int insert_me_here = -1; | 476 int insert_me_here = -1; |
416 Lisp_Range_Table *rt = XRANGE_TABLE (table); | 477 Lisp_Range_Table *rt = XRANGE_TABLE (table); |
478 int foundp; | |
417 | 479 |
418 external_to_internal_adjust_ends (rt->type, &first, &last); | 480 external_to_internal_adjust_ends (rt->type, &first, &last); |
419 if (first == last) | 481 if (first == last) |
420 return; | 482 return; |
421 if (first > last) | 483 if (first > last) |
422 /* This will happen if originally first == last and both ends are | 484 /* This will happen if originally first == last and both ends are |
423 open. #### Should we signal an error? */ | 485 open. #### Should we signal an error? */ |
424 return; | 486 return; |
425 | 487 |
488 if (DUMPEDP (rt->entries)) | |
489 rt->entries = gap_array_clone (rt->entries); | |
490 | |
491 i = get_range_table_pos (first, gap_array_length (rt->entries), | |
492 gap_array_begin (rt->entries, | |
493 struct range_table_entry), | |
494 gap_array_gappos (rt->entries), | |
495 gap_array_gapsize (rt->entries), &foundp); | |
496 | |
497 #ifdef ERROR_CHECK_TYPES | |
498 if (foundp) | |
499 { | |
500 if (i < gap_array_length (rt->entries)) | |
501 { | |
502 struct range_table_entry *entry = | |
503 rangetab_gap_array_atp (rt->entries, i); | |
504 assert (first >= entry->first && first < entry->last); | |
505 } | |
506 } | |
507 else | |
508 { | |
509 if (i < gap_array_length (rt->entries)) | |
510 { | |
511 struct range_table_entry *entry = | |
512 rangetab_gap_array_atp (rt->entries, i); | |
513 assert (first < entry->first); | |
514 } | |
515 if (i > 0) | |
516 { | |
517 struct range_table_entry *entry = | |
518 rangetab_gap_array_atp (rt->entries, i - 1); | |
519 assert (first >= entry->last); | |
520 } | |
521 } | |
522 #endif /* ERROR_CHECK_TYPES */ | |
523 | |
524 /* If the beginning of the new range isn't within any existing range, | |
525 it might still be just grazing the end of an end-open range (remember, | |
526 internally all ranges are start-close end-open); so back up one | |
527 so we consider this range. */ | |
528 if (!foundp && i > 0) | |
529 i--; | |
530 | |
426 /* Now insert in the proper place. This gets tricky because | 531 /* Now insert in the proper place. This gets tricky because |
427 we may be overlapping one or more existing ranges and need | 532 we may be overlapping one or more existing ranges and need |
428 to fix them up. */ | 533 to fix them up. */ |
429 | 534 |
430 /* First delete all sections of any existing ranges that overlap | 535 /* First delete all sections of any existing ranges that overlap |
431 the new range. */ | 536 the new range. */ |
432 for (i = 0; i < Dynarr_length (rt->entries); i++) | 537 for (; i < gap_array_length (rt->entries); i++) |
433 { | 538 { |
434 struct range_table_entry *entry = Dynarr_atp (rt->entries, i); | 539 struct range_table_entry *entry = |
540 rangetab_gap_array_atp (rt->entries, i); | |
435 /* We insert before the first range that begins at or after the | 541 /* We insert before the first range that begins at or after the |
436 new range. */ | 542 new range. */ |
437 if (entry->first >= first && insert_me_here < 0) | 543 if (entry->first >= first && insert_me_here < 0) |
438 insert_me_here = i; | 544 insert_me_here = i; |
439 if (entry->last < first) | 545 if (entry->last < first) |
473 | 579 |
474 insert_me_too.first = last; | 580 insert_me_too.first = last; |
475 insert_me_too.last = entry->last; | 581 insert_me_too.last = entry->last; |
476 insert_me_too.val = entry->val; | 582 insert_me_too.val = entry->val; |
477 entry->last = first; | 583 entry->last = first; |
478 Dynarr_insert_many (rt->entries, &insert_me_too, 1, i + 1); | 584 rt->entries = |
585 gap_array_insert_els (rt->entries, i + 1, &insert_me_too, 1); | |
479 } | 586 } |
480 else if (entry->last >= last) | 587 else if (entry->last >= last) |
481 { | 588 { |
482 /* looks like: | 589 /* looks like: |
483 | 590 |
494 entry->first = last; | 601 entry->first = last; |
495 } | 602 } |
496 else | 603 else |
497 { | 604 { |
498 /* existing is entirely within new. */ | 605 /* existing is entirely within new. */ |
499 Dynarr_delete_many (rt->entries, i, 1); | 606 gap_array_delete_els (rt->entries, i, 1); |
500 i--; /* back up since everything shifted one to the left. */ | 607 i--; /* back up since everything shifted one to the left. */ |
501 } | 608 } |
502 } | 609 } |
503 | 610 |
504 /* Someone asked us to delete the range, not insert it. */ | 611 /* Someone asked us to delete the range, not insert it. */ |
515 | 622 |
516 insert_me.first = first; | 623 insert_me.first = first; |
517 insert_me.last = last; | 624 insert_me.last = last; |
518 insert_me.val = val; | 625 insert_me.val = val; |
519 | 626 |
520 Dynarr_insert_many (rt->entries, &insert_me, 1, insert_me_here); | 627 rt->entries = |
628 gap_array_insert_els (rt->entries, insert_me_here, &insert_me, 1); | |
521 } | 629 } |
522 | 630 |
523 /* Now see if we can combine this entry with adjacent ones just | 631 /* Now see if we can combine this entry with adjacent ones just |
524 before or after. */ | 632 before or after. */ |
525 | 633 |
526 if (insert_me_here > 0) | 634 if (insert_me_here > 0) |
527 { | 635 { |
528 struct range_table_entry *entry = Dynarr_atp (rt->entries, | 636 struct range_table_entry *entry = |
529 insert_me_here - 1); | 637 rangetab_gap_array_atp (rt->entries, insert_me_here - 1); |
530 if (EQ (val, entry->val) && entry->last == first) | 638 if (EQ (val, entry->val) && entry->last == first) |
531 { | 639 { |
532 entry->last = last; | 640 entry->last = last; |
533 Dynarr_delete_many (rt->entries, insert_me_here, 1); | 641 gap_array_delete_els (rt->entries, insert_me_here, 1); |
534 insert_me_here--; | 642 insert_me_here--; |
535 /* We have morphed into a larger range. Update our records | 643 /* We have morphed into a larger range. Update our records |
536 in case we also combine with the one after. */ | 644 in case we also combine with the one after. */ |
537 first = entry->first; | 645 first = entry->first; |
538 } | 646 } |
539 } | 647 } |
540 | 648 |
541 if (insert_me_here < Dynarr_length (rt->entries) - 1) | 649 if (insert_me_here < gap_array_length (rt->entries) - 1) |
542 { | 650 { |
543 struct range_table_entry *entry = Dynarr_atp (rt->entries, | 651 struct range_table_entry *entry = |
544 insert_me_here + 1); | 652 rangetab_gap_array_atp (rt->entries, insert_me_here + 1); |
545 if (EQ (val, entry->val) && entry->first == last) | 653 if (EQ (val, entry->val) && entry->first == last) |
546 { | 654 { |
547 entry->first = first; | 655 entry->first = first; |
548 Dynarr_delete_many (rt->entries, insert_me_here, 1); | 656 gap_array_delete_els (rt->entries, insert_me_here, 1); |
549 } | 657 } |
550 } | 658 } |
551 } | 659 } |
552 | 660 |
553 DEFUN ("put-range-table", Fput_range_table, 4, 4, 0, /* | 661 DEFUN ("put-range-table", Fput_range_table, 4, 4, 0, /* |
582 Flush RANGE-TABLE. | 690 Flush RANGE-TABLE. |
583 */ | 691 */ |
584 (range_table)) | 692 (range_table)) |
585 { | 693 { |
586 CHECK_RANGE_TABLE (range_table); | 694 CHECK_RANGE_TABLE (range_table); |
587 Dynarr_reset (XRANGE_TABLE (range_table)->entries); | 695 gap_array_delete_all_els (XRANGE_TABLE (range_table)->entries); |
588 return Qnil; | 696 return Qnil; |
589 } | 697 } |
590 | 698 |
591 DEFUN ("map-range-table", Fmap_range_table, 2, 2, 0, /* | 699 DEFUN ("map-range-table", Fmap_range_table, 2, 2, 0, /* |
592 Map FUNCTION over entries in RANGE-TABLE, calling it with three args, | 700 Map FUNCTION over entries in RANGE-TABLE, calling it with three args, |
608 | 716 |
609 rt = XRANGE_TABLE (range_table); | 717 rt = XRANGE_TABLE (range_table); |
610 | 718 |
611 /* Do not "optimize" by pulling out the length computation below! | 719 /* Do not "optimize" by pulling out the length computation below! |
612 FUNCTION may have changed the table. */ | 720 FUNCTION may have changed the table. */ |
613 for (i = 0; i < Dynarr_length (rt->entries); i++) | 721 for (i = 0; i < gap_array_length (rt->entries); i++) |
614 { | 722 { |
615 struct range_table_entry *entry = Dynarr_atp (rt->entries, i); | 723 struct range_table_entry entry = |
724 rangetab_gap_array_at (rt->entries, i); | |
616 EMACS_INT first, last; | 725 EMACS_INT first, last; |
617 Lisp_Object args[4]; | 726 Lisp_Object args[4]; |
618 int oldlen; | 727 int oldlen; |
619 | 728 |
620 again: | 729 again: |
621 first = entry->first; | 730 first = entry.first; |
622 last = entry->last; | 731 last = entry.last; |
623 oldlen = Dynarr_length (rt->entries); | 732 oldlen = gap_array_length (rt->entries); |
624 args[0] = function; | 733 args[0] = function; |
625 /* Fix up the numbers in accordance with the open/closedness of the | 734 /* Fix up the numbers in accordance with the open/closedness of the |
626 table. */ | 735 table. */ |
627 { | 736 { |
628 EMACS_INT premier = first, dernier = last; | 737 EMACS_INT premier = first, dernier = last; |
629 internal_to_external_adjust_ends (rt->type, &premier, &dernier); | 738 internal_to_external_adjust_ends (rt->type, &premier, &dernier); |
630 args[1] = make_int (premier); | 739 args[1] = make_int (premier); |
631 args[2] = make_int (dernier); | 740 args[2] = make_int (dernier); |
632 } | 741 } |
633 args[3] = entry->val; | 742 args[3] = entry.val; |
634 Ffuncall (countof (args), args); | 743 Ffuncall (countof (args), args); |
635 /* Has FUNCTION removed the entry? */ | 744 /* Has FUNCTION removed the entry? */ |
636 if (oldlen > Dynarr_length (rt->entries) | 745 if (oldlen > gap_array_length (rt->entries) |
637 && i < Dynarr_length (rt->entries) | 746 && i < gap_array_length (rt->entries) |
638 && (first != entry->first || last != entry->last)) | 747 && (first != entry.first || last != entry.last)) |
639 goto again; | 748 goto again; |
640 } | 749 } |
641 | 750 |
642 return Qnil; | 751 return Qnil; |
643 } | 752 } |
677 static Lisp_Object | 786 static Lisp_Object |
678 rangetab_instantiate (Lisp_Object plist) | 787 rangetab_instantiate (Lisp_Object plist) |
679 { | 788 { |
680 Lisp_Object data = Qnil, type = Qnil, rangetab; | 789 Lisp_Object data = Qnil, type = Qnil, rangetab; |
681 | 790 |
682 PROPERTY_LIST_LOOP_3 (key, value, plist) | 791 if (KEYWORDP (Fcar (plist))) |
683 { | 792 { |
684 if (EQ (key, Qtype)) type = value; | 793 PROPERTY_LIST_LOOP_3 (key, value, plist) |
685 else if (EQ (key, Qdata)) data = value; | 794 { |
686 else | 795 if (EQ (key, Q_type)) type = value; |
687 ABORT (); | 796 else if (EQ (key, Q_data)) data = value; |
688 } | 797 else if (!KEYWORDP (key)) |
798 signal_error | |
799 (Qinvalid_read_syntax, | |
800 "can't mix keyword and non-keyword structure syntax", | |
801 key); | |
802 else | |
803 ABORT (); | |
804 } | |
805 } | |
806 #ifdef NEED_TO_HANDLE_21_4_CODE | |
807 else | |
808 { | |
809 PROPERTY_LIST_LOOP_3 (key, value, plist) | |
810 { | |
811 if (EQ (key, Qtype)) type = value; | |
812 else if (EQ (key, Qdata)) data = value; | |
813 else if (KEYWORDP (key)) | |
814 signal_error | |
815 (Qinvalid_read_syntax, | |
816 "can't mix keyword and non-keyword structure syntax", | |
817 key); | |
818 else | |
819 ABORT (); | |
820 } | |
821 } | |
822 #endif /* NEED_TO_HANDLE_21_4_CODE */ | |
689 | 823 |
690 rangetab = Fmake_range_table (type); | 824 rangetab = Fmake_range_table (type); |
691 | 825 |
692 { | 826 { |
693 PROPERTY_LIST_LOOP_3 (range, val, data) | 827 PROPERTY_LIST_LOOP_3 (range, val, data) |
775 | 909 |
776 int | 910 int |
777 unified_range_table_bytes_needed (Lisp_Object rangetab) | 911 unified_range_table_bytes_needed (Lisp_Object rangetab) |
778 { | 912 { |
779 return (sizeof (struct range_table_entry) * | 913 return (sizeof (struct range_table_entry) * |
780 (Dynarr_length (XRANGE_TABLE (rangetab)->entries) - 1) + | 914 (gap_array_length (XRANGE_TABLE (rangetab)->entries) - 1) + |
781 sizeof (struct unified_range_table) + | 915 sizeof (struct unified_range_table) + |
782 /* ALIGNOF a struct may be too big. */ | 916 /* ALIGNOF a struct may be too big. */ |
783 /* We have four bytes for the size numbers, and an extra | 917 /* We have four bytes for the size numbers, and an extra |
784 four or eight bytes for making sure we get the alignment | 918 four or eight bytes for making sure we get the alignment |
785 OK. */ | 919 OK. */ |
795 { | 929 { |
796 /* We cast to the above structure rather than just casting to | 930 /* We cast to the above structure rather than just casting to |
797 char * and adding sizeof(int), because that will lead to | 931 char * and adding sizeof(int), because that will lead to |
798 mis-aligned data on the Alpha machines. */ | 932 mis-aligned data on the Alpha machines. */ |
799 struct unified_range_table *un; | 933 struct unified_range_table *un; |
800 range_table_entry_dynarr *rted = XRANGE_TABLE (rangetab)->entries; | 934 Gap_Array *rtega = XRANGE_TABLE (rangetab)->entries; |
801 int total_needed = unified_range_table_bytes_needed (rangetab); | 935 int total_needed = unified_range_table_bytes_needed (rangetab); |
802 void *new_dest = ALIGN_PTR ((char *) dest + 4, EMACS_INT); | 936 void *new_dest = ALIGN_PTR ((char *) dest + 4, EMACS_INT); |
937 Elemcount i; | |
803 | 938 |
804 * (char *) dest = (char) ((char *) new_dest - (char *) dest); | 939 * (char *) dest = (char) ((char *) new_dest - (char *) dest); |
805 * ((unsigned char *) dest + 1) = total_needed & 0xFF; | 940 * ((unsigned char *) dest + 1) = total_needed & 0xFF; |
806 total_needed >>= 8; | 941 total_needed >>= 8; |
807 * ((unsigned char *) dest + 2) = total_needed & 0xFF; | 942 * ((unsigned char *) dest + 2) = total_needed & 0xFF; |
808 total_needed >>= 8; | 943 total_needed >>= 8; |
809 * ((unsigned char *) dest + 3) = total_needed & 0xFF; | 944 * ((unsigned char *) dest + 3) = total_needed & 0xFF; |
810 un = (struct unified_range_table *) new_dest; | 945 un = (struct unified_range_table *) new_dest; |
811 un->nentries = Dynarr_length (rted); | 946 un->nentries = gap_array_length (rtega); |
812 un->type = XRANGE_TABLE (rangetab)->type; | 947 un->type = XRANGE_TABLE (rangetab)->type; |
813 memcpy (&un->first, Dynarr_begin (rted), | 948 for (i = 0; i < gap_array_length (rtega); i++) |
814 sizeof (struct range_table_entry) * Dynarr_length (rted)); | 949 (&un->first)[i] = rangetab_gap_array_at (rtega, i); |
815 } | 950 } |
816 | 951 |
817 /* Return number of bytes actually used by a unified range table. */ | 952 /* Return number of bytes actually used by a unified range table. */ |
818 | 953 |
819 int | 954 int |
852 | 987 |
853 align_the_damn_table (unrangetab); | 988 align_the_damn_table (unrangetab); |
854 new_dest = (char *) unrangetab + * (char *) unrangetab; | 989 new_dest = (char *) unrangetab + * (char *) unrangetab; |
855 un = (struct unified_range_table *) new_dest; | 990 un = (struct unified_range_table *) new_dest; |
856 | 991 |
857 return get_range_table (pos, un->nentries, &un->first, default_); | 992 return get_range_table (pos, un->nentries, &un->first, 0, 0, default_); |
858 } | 993 } |
859 | 994 |
860 /* Return number of entries in a unified range table. */ | 995 /* Return number of entries in a unified range table. */ |
861 | 996 |
862 int | 997 int |
900 /************************************************************************/ | 1035 /************************************************************************/ |
901 | 1036 |
902 void | 1037 void |
903 syms_of_rangetab (void) | 1038 syms_of_rangetab (void) |
904 { | 1039 { |
905 INIT_LRECORD_IMPLEMENTATION (range_table); | 1040 INIT_LISP_OBJECT (range_table); |
906 | 1041 |
907 DEFSYMBOL_MULTIWORD_PREDICATE (Qrange_tablep); | 1042 DEFSYMBOL_MULTIWORD_PREDICATE (Qrange_tablep); |
908 DEFSYMBOL (Qrange_table); | 1043 DEFSYMBOL (Qrange_table); |
909 | 1044 |
910 DEFSYMBOL (Qstart_closed_end_open); | 1045 DEFSYMBOL (Qstart_closed_end_open); |
928 { | 1063 { |
929 struct structure_type *st; | 1064 struct structure_type *st; |
930 | 1065 |
931 st = define_structure_type (Qrange_table, 0, rangetab_instantiate); | 1066 st = define_structure_type (Qrange_table, 0, rangetab_instantiate); |
932 | 1067 |
1068 define_structure_type_keyword (st, Q_data, rangetab_data_validate); | |
1069 define_structure_type_keyword (st, Q_type, rangetab_type_validate); | |
1070 #ifdef NEED_TO_HANDLE_21_4_CODE | |
933 define_structure_type_keyword (st, Qdata, rangetab_data_validate); | 1071 define_structure_type_keyword (st, Qdata, rangetab_data_validate); |
934 define_structure_type_keyword (st, Qtype, rangetab_type_validate); | 1072 define_structure_type_keyword (st, Qtype, rangetab_type_validate); |
935 } | 1073 #endif /* NEED_TO_HANDLE_21_4_CODE */ |
1074 } |