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 }