Mercurial > hg > xemacs-beta

comparison src/rangetab.c @ 2421:ab71ad6ff3dd

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
[xemacs-hg @ 2004-12-06 03:50:53 by ben] (none) README.packages: Document use of --package-prefix. Fix error in specifying standard package location. make-docfile.c: Use QXE_PATH_MAX. info.el: Correct doc string giving example package path. menubar-items.el: Move Prefix Rectangle command up one level. xemacs/packages.texi: Add long form of Lisp Reference Manual to links. Add links pointing to Lisp Reference Manual for more detailed package discussion. lispref/range-tables.texi: Document range-table changes. internals/internals.texi: Update history section. elhash.c, elhash.h, profile.c: Create inchash_eq() to allow direct incrementing of hash-table entry. Use in profile.c to try to reduce profiling overhead. Increase initial size of profile hash tables to reduce profiling overhead. buffer.c, device-msw.c, dialog-msw.c, dired-msw.c, editfns.c, event-msw.c, events.c, glyphs-msw.c, keymap.c, objects-msw.c, process-nt.c, syswindows.h, text.c, text.h, unexnt.c: Rename xetcs* -> qxetcs* for consistency with qxestr*. Rename ei*_c(_*) -> ei*_ascii(_*) since they work with ASCII-only strings not "C strings", whatever those are. This is the last place where "c" was incorrectly being used for "ascii". dialog-msw.c, dumper.c, event-msw.c, fileio.c, glyphs-gtk.c, glyphs-x.c, nt.c, process-nt.c, realpath.c, sysdep.c, sysfile.h, unexcw.c, unexnext.c, unexnt.c: Try to avoid differences in systems that do or do not include final null byte in PATH_MAX. Create PATH_MAX_INTERNAL and PATH_MAX_EXTERNAL and use them everywhere. Rewrite code in dumper.c to avoid use of PATH_MAX. When necessary in nt.c, use _MAX_PATH instead of MAX_PATH to be consistent with other places. text.c: Code to short-circuit when binary or Unicode was not working due to EOL wrapping. Fix this code to work when either no EOL autodetection or no CR's or LF's in the text. lisp.h, rangetab.c, rangetab.h, regex.c, search.c: Implement different types of ranges (open/closed start and end). Change default to be start-closed, end-open.
author ben
date Mon, 06 Dec 2004 03:52:23 +0000
parents ecf1ebac70d8
children b3315b0c8558
comparison
equal deleted inserted replaced
2420:ad56e5a6d09f 2421:ab71ad6ff3dd
1 /* XEmacs routines to deal with range tables. 1 /* XEmacs routines to deal with range tables.
2 Copyright (C) 1995 Sun Microsystems, Inc. 2 Copyright (C) 1995 Sun Microsystems, Inc.
3 Copyright (C) 1995, 2002 Ben Wing. 3 Copyright (C) 1995, 2002, 2004 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
28 #include "rangetab.h" 28 #include "rangetab.h"
29 29
30 Lisp_Object Qrange_tablep; 30 Lisp_Object Qrange_tablep;
31 Lisp_Object Qrange_table; 31 Lisp_Object Qrange_table;
32 32
33 Lisp_Object Qstart_closed_end_open;
34 Lisp_Object Qstart_open_end_open;
35 Lisp_Object Qstart_closed_end_closed;
36 Lisp_Object Qstart_open_end_closed;
37
33 38
34 /************************************************************************/ 39 /************************************************************************/
35 /* Range table object */ 40 /* Range table object */
36 /************************************************************************/ 41 /************************************************************************/
42
43 static enum range_table_type
44 range_table_symbol_to_type (Lisp_Object symbol)
45 {
46 if (NILP (symbol))
47 return RANGE_START_CLOSED_END_OPEN;
48
49 CHECK_SYMBOL (symbol);
50 if (EQ (symbol, Qstart_closed_end_open))
51 return RANGE_START_CLOSED_END_OPEN;
52 if (EQ (symbol, Qstart_closed_end_closed))
53 return RANGE_START_CLOSED_END_CLOSED;
54 if (EQ (symbol, Qstart_open_end_open))
55 return RANGE_START_OPEN_END_OPEN;
56 if (EQ (symbol, Qstart_open_end_closed))
57 return RANGE_START_OPEN_END_CLOSED;
58
59 invalid_constant ("Unknown range table type", symbol);
60 RETURN_NOT_REACHED (RANGE_START_CLOSED_END_OPEN);
61 }
62
63 static Lisp_Object
64 range_table_type_to_symbol (enum range_table_type type)
65 {
66 switch (type)
67 {
68 case RANGE_START_CLOSED_END_OPEN:
69 return Qstart_closed_end_open;
70 case RANGE_START_CLOSED_END_CLOSED:
71 return Qstart_closed_end_closed;
72 case RANGE_START_OPEN_END_OPEN:
73 return Qstart_open_end_open;
74 case RANGE_START_OPEN_END_CLOSED:
75 return Qstart_open_end_closed;
76 }
77
78 abort ();
79 return Qnil;
80 }
37 81
38 /* We use a sorted array of ranges. 82 /* We use a sorted array of ranges.
39 83
40 #### We should be using the gap array stuff from extents.c. This 84 #### We should be using the gap array stuff from extents.c. This
41 is not hard but just requires moving that stuff out of that file. */ 85 is not hard but just requires moving that stuff out of that file. */
56 int UNUSED (escapeflag)) 100 int UNUSED (escapeflag))
57 { 101 {
58 Lisp_Range_Table *rt = XRANGE_TABLE (obj); 102 Lisp_Range_Table *rt = XRANGE_TABLE (obj);
59 int i; 103 int i;
60 104
61 write_c_string (printcharfun, "#s(range-table data ("); 105 if (print_readably)
106 write_fmt_string_lisp (printcharfun, "#s(range-table type %s data (",
107 1, range_table_type_to_symbol (rt->type));
108 else
109 write_c_string (printcharfun, "#<range-table ");
62 for (i = 0; i < Dynarr_length (rt->entries); i++) 110 for (i = 0; i < Dynarr_length (rt->entries); i++)
63 { 111 {
64 struct range_table_entry *rte = Dynarr_atp (rt->entries, i); 112 struct range_table_entry *rte = Dynarr_atp (rt->entries, i);
113 int so, ec;
65 if (i > 0) 114 if (i > 0)
66 write_c_string (printcharfun, " "); 115 write_c_string (printcharfun, " ");
67 if (rte->first == rte->last) 116 switch (rt->type)
68 write_fmt_string (printcharfun, "%ld ", (long) (rte->first)); 117 {
69 else 118 case RANGE_START_CLOSED_END_OPEN: so = 0, ec = 0; break;
70 write_fmt_string (printcharfun, "(%ld %ld) ", (long) (rte->first), 119 case RANGE_START_CLOSED_END_CLOSED: so = 0, ec = 1; break;
71 (long) (rte->last)); 120 case RANGE_START_OPEN_END_OPEN: so = 1, ec = 0; break;
121 case RANGE_START_OPEN_END_CLOSED: so = 1; ec = 1; break;
122 default: abort (); so = 0, ec = 0; break;
123 }
124 write_fmt_string (printcharfun, "%c%ld %ld%c ",
125 print_readably ? '(' : so ? '(' : '[',
126 (long) (rte->first - so),
127 (long) (rte->last - ec),
128 print_readably ? ')' : ec ? ']' : ')'
129 );
72 print_internal (rte->val, printcharfun, 1); 130 print_internal (rte->val, printcharfun, 1);
73 } 131 }
74 write_c_string (printcharfun, "))"); 132 if (print_readably)
133 write_c_string (printcharfun, "))");
134 else
135 write_fmt_string (printcharfun, " 0x%x>", rt->header.uid);
75 } 136 }
76 137
77 static int 138 static int
78 range_table_equal (Lisp_Object obj1, Lisp_Object obj2, int depth) 139 range_table_equal (Lisp_Object obj1, Lisp_Object obj2, int depth)
79 { 140 {
178 for (i = 0; i < Dynarr_length (rt->entries); i++) 239 for (i = 0; i < Dynarr_length (rt->entries); i++)
179 { 240 {
180 struct range_table_entry *rte = Dynarr_atp (rt->entries, i); 241 struct range_table_entry *rte = Dynarr_atp (rt->entries, i);
181 assert (rte->last >= rte->first); 242 assert (rte->last >= rte->first);
182 if (i > 0) 243 if (i > 0)
183 assert (Dynarr_at (rt->entries, i - 1).last < rte->first); 244 assert (Dynarr_at (rt->entries, i - 1).last <= rte->first);
184 } 245 }
185 } 246 }
186 247
187 #else 248 #else
188 249
205 { 266 {
206 /* RIGHT might not point to a valid entry (i.e. it's at the end 267 /* RIGHT might not point to a valid entry (i.e. it's at the end
207 of the list), so NEWPOS must round down. */ 268 of the list), so NEWPOS must round down. */
208 int newpos = (left + right) >> 1; 269 int newpos = (left + right) >> 1;
209 struct range_table_entry *entry = tab + newpos; 270 struct range_table_entry *entry = tab + newpos;
210 if (pos > entry->last) 271 if (pos >= entry->last)
211 left = newpos+1; 272 left = newpos + 1;
212 else if (pos < entry->first) 273 else if (pos < entry->first)
213 right = newpos; 274 right = newpos;
214 else 275 else
215 return entry->val; 276 return entry->val;
216 } 277 }
224 (object)) 285 (object))
225 { 286 {
226 return RANGE_TABLEP (object) ? Qt : Qnil; 287 return RANGE_TABLEP (object) ? Qt : Qnil;
227 } 288 }
228 289
229 DEFUN ("make-range-table", Fmake_range_table, 0, 0, 0, /* 290 DEFUN ("range-table-type", Frange_table_type, 1, 1, 0, /*
291 Return non-nil if OBJECT is a range table.
292 */
293 (range_table))
294 {
295 CHECK_RANGE_TABLE (range_table);
296 return range_table_type_to_symbol (XRANGE_TABLE (range_table)->type);
297 }
298
299 DEFUN ("make-range-table", Fmake_range_table, 0, 1, 0, /*
230 Return a new, empty range table. 300 Return a new, empty range table.
231 You can manipulate it using `put-range-table', `get-range-table', 301 You can manipulate it using `put-range-table', `get-range-table',
232 `remove-range-table', and `clear-range-table'. 302 `remove-range-table', and `clear-range-table'.
233 */ 303 Range tables allow you to efficiently set values for ranges of integers.
234 ()) 304
305 TYPE is a symbol indicating how ranges are assumed to function at their
306 ends. It can be one of
307
308 SYMBOL RANGE-START RANGE-END
309 ------ ----------- ---------
310 `start-closed-end-open' (the default) closed open
311 `start-closed-end-closed' closed closed
312 `start-open-end-open' open open
313 `start-open-end-closed' open closed
314
315 A `closed' endpoint of a range means that the number at that end is included
316 in the range. For an `open' endpoint, the number would not be included.
317
318 For example, a closed-open range from 5 to 20 would be indicated as [5,
319 20) where a bracket indicates a closed end and a parenthesis an open end,
320 and would mean `all the numbers between 5 and 20', including 5 but not 20.
321 This seems a little strange at first but is in fact extremely common in
322 the outside world as well as in computers and makes things work sensibly.
323 For example, if I say "there are seven days between today and next week
324 today", I'm including today but not next week today; if I included both,
325 there would be eight days. Similarly, there are 15 (= 20 - 5) elements in
326 the range [5, 20), but 16 in the range [5, 20].
327 */
328 (type))
235 { 329 {
236 Lisp_Range_Table *rt = alloc_lcrecord_type (Lisp_Range_Table, 330 Lisp_Range_Table *rt = alloc_lcrecord_type (Lisp_Range_Table,
237 &lrecord_range_table); 331 &lrecord_range_table);
238 rt->entries = Dynarr_new (range_table_entry); 332 rt->entries = Dynarr_new (range_table_entry);
333 rt->type = range_table_symbol_to_type (type);
239 return wrap_range_table (rt); 334 return wrap_range_table (rt);
240 } 335 }
241 336
242 DEFUN ("copy-range-table", Fcopy_range_table, 1, 1, 0, /* 337 DEFUN ("copy-range-table", Fcopy_range_table, 1, 1, 0, /*
243 Return a new range table which is a copy of RANGE-TABLE. 338 Return a new range table which is a copy of RANGE-TABLE.
251 CHECK_RANGE_TABLE (range_table); 346 CHECK_RANGE_TABLE (range_table);
252 rt = XRANGE_TABLE (range_table); 347 rt = XRANGE_TABLE (range_table);
253 348
254 rtnew = alloc_lcrecord_type (Lisp_Range_Table, &lrecord_range_table); 349 rtnew = alloc_lcrecord_type (Lisp_Range_Table, &lrecord_range_table);
255 rtnew->entries = Dynarr_new (range_table_entry); 350 rtnew->entries = Dynarr_new (range_table_entry);
351 rtnew->type = rt->type;
256 352
257 Dynarr_add_many (rtnew->entries, Dynarr_atp (rt->entries, 0), 353 Dynarr_add_many (rtnew->entries, Dynarr_atp (rt->entries, 0),
258 Dynarr_length (rt->entries)); 354 Dynarr_length (rt->entries));
259 return wrap_range_table (rtnew); 355 return wrap_range_table (rtnew);
260 } 356 }
281 EMACS_INT last, Lisp_Object val) 377 EMACS_INT last, Lisp_Object val)
282 { 378 {
283 int i; 379 int i;
284 int insert_me_here = -1; 380 int insert_me_here = -1;
285 Lisp_Range_Table *rt = XRANGE_TABLE (table); 381 Lisp_Range_Table *rt = XRANGE_TABLE (table);
382
383 /* Fix up the numbers in accordance with the open/closedness to make
384 them behave like default open/closed. */
385
386 switch (rt->type)
387 {
388 case RANGE_START_CLOSED_END_OPEN: break;
389 case RANGE_START_CLOSED_END_CLOSED: last++; break;
390 case RANGE_START_OPEN_END_OPEN: first++; break;
391 case RANGE_START_OPEN_END_CLOSED: first++, last++; break;
392 }
393
394 if (first == last)
395 return;
396 if (first > last)
397 /* This will happen if originally first == last and both ends are
398 open. #### Should we signal an error? */
399 return;
286 400
287 /* Now insert in the proper place. This gets tricky because 401 /* Now insert in the proper place. This gets tricky because
288 we may be overlapping one or more existing ranges and need 402 we may be overlapping one or more existing ranges and need
289 to fix them up. */ 403 to fix them up. */
290 404
302 continue; 416 continue;
303 if (entry->first > last) 417 if (entry->first > last)
304 /* completely after the new range. No more possibilities of 418 /* completely after the new range. No more possibilities of
305 finding overlapping ranges. */ 419 finding overlapping ranges. */
306 break; 420 break;
421 /* At this point the existing ENTRY overlaps or touches the new one. */
307 if (entry->first < first && entry->last <= last) 422 if (entry->first < first && entry->last <= last)
308 { 423 {
309 /* looks like: 424 /* looks like:
310 425
311 [ NEW ] 426 [ NEW )
312 [ EXISTING ] 427 [ EXISTING )
428
429 or
430
431 [ NEW )
432 [ EXISTING )
313 433
314 */ 434 */
315 /* truncate the end off of it. */ 435 /* truncate the end off of it. */
316 entry->last = first - 1; 436 entry->last = first;
317 } 437 }
318 else if (entry->first < first && entry->last > last) 438 else if (entry->first < first && entry->last > last)
319 /* looks like: 439 /* looks like:
320 440
321 [ NEW ] 441 [ NEW )
322 [ EXISTING ] 442 [ EXISTING )
323 443
324 */ 444 */
325 /* need to split this one in two. */ 445 /* need to split this one in two. */
326 { 446 {
327 struct range_table_entry insert_me_too; 447 struct range_table_entry insert_me_too;
328 448
329 insert_me_too.first = last + 1; 449 insert_me_too.first = last;
330 insert_me_too.last = entry->last; 450 insert_me_too.last = entry->last;
331 insert_me_too.val = entry->val; 451 insert_me_too.val = entry->val;
332 entry->last = first - 1; 452 entry->last = first;
333 Dynarr_insert_many (rt->entries, &insert_me_too, 1, i + 1); 453 Dynarr_insert_many (rt->entries, &insert_me_too, 1, i + 1);
334 } 454 }
335 else if (entry->last > last) 455 else if (entry->last >= last)
336 { 456 {
337 /* looks like: 457 /* looks like:
338 458
339 [ NEW ] 459 [ NEW )
340 [ EXISTING ] 460 [ EXISTING )
461
462 or
463
464 [ NEW )
465 [ EXISTING )
341 466
342 */ 467 */
343 /* truncate the start off of it. */ 468 /* truncate the start off of it. */
344 entry->first = last + 1; 469 entry->first = last;
345 } 470 }
346 else 471 else
347 { 472 {
348 /* existing is entirely within new. */ 473 /* existing is entirely within new. */
349 Dynarr_delete_many (rt->entries, i, 1); 474 Dynarr_delete_many (rt->entries, i, 1);
375 500
376 if (insert_me_here > 0) 501 if (insert_me_here > 0)
377 { 502 {
378 struct range_table_entry *entry = Dynarr_atp (rt->entries, 503 struct range_table_entry *entry = Dynarr_atp (rt->entries,
379 insert_me_here - 1); 504 insert_me_here - 1);
380 if (EQ (val, entry->val) && entry->last == first - 1) 505 if (EQ (val, entry->val) && entry->last == first)
381 { 506 {
382 entry->last = last; 507 entry->last = last;
383 Dynarr_delete_many (rt->entries, insert_me_here, 1); 508 Dynarr_delete_many (rt->entries, insert_me_here, 1);
384 insert_me_here--; 509 insert_me_here--;
385 /* We have morphed into a larger range. Update our records 510 /* We have morphed into a larger range. Update our records
390 515
391 if (insert_me_here < Dynarr_length (rt->entries) - 1) 516 if (insert_me_here < Dynarr_length (rt->entries) - 1)
392 { 517 {
393 struct range_table_entry *entry = Dynarr_atp (rt->entries, 518 struct range_table_entry *entry = Dynarr_atp (rt->entries,
394 insert_me_here + 1); 519 insert_me_here + 1);
395 if (EQ (val, entry->val) && entry->first == last + 1) 520 if (EQ (val, entry->val) && entry->first == last)
396 { 521 {
397 entry->first = first; 522 entry->first = first;
398 Dynarr_delete_many (rt->entries, insert_me_here, 1); 523 Dynarr_delete_many (rt->entries, insert_me_here, 1);
399 } 524 }
400 } 525 }
401 } 526 }
402 527
403 DEFUN ("put-range-table", Fput_range_table, 4, 4, 0, /* 528 DEFUN ("put-range-table", Fput_range_table, 4, 4, 0, /*
404 Set the value for range (START, END) to be VALUE in RANGE-TABLE. 529 Set the value for range START .. END to be VALUE in RANGE-TABLE.
405 */ 530 */
406 (start, end, value, range_table)) 531 (start, end, value, range_table))
407 { 532 {
408 EMACS_INT first, last; 533 EMACS_INT first, last;
409 534
419 verify_range_table (XRANGE_TABLE (range_table)); 544 verify_range_table (XRANGE_TABLE (range_table));
420 return Qnil; 545 return Qnil;
421 } 546 }
422 547
423 DEFUN ("remove-range-table", Fremove_range_table, 3, 3, 0, /* 548 DEFUN ("remove-range-table", Fremove_range_table, 3, 3, 0, /*
424 Remove the value for range (START, END) in RANGE-TABLE. 549 Remove the value for range START .. END in RANGE-TABLE.
425 */ 550 */
426 (start, end, range_table)) 551 (start, end, range_table))
427 { 552 {
428 return Fput_range_table (start, end, Qunbound, range_table); 553 return Fput_range_table (start, end, Qunbound, range_table);
429 } 554 }
489 /************************************************************************/ 614 /************************************************************************/
490 /* Range table read syntax */ 615 /* Range table read syntax */
491 /************************************************************************/ 616 /************************************************************************/
492 617
493 static int 618 static int
619 rangetab_type_validate (Lisp_Object UNUSED (keyword), Lisp_Object value,
620 Error_Behavior UNUSED (errb))
621 {
622 /* #### should deal with ERRB */
623 range_table_symbol_to_type (value);
624 return 1;
625 }
626
627 static int
494 rangetab_data_validate (Lisp_Object UNUSED (keyword), Lisp_Object value, 628 rangetab_data_validate (Lisp_Object UNUSED (keyword), Lisp_Object value,
495 Error_Behavior UNUSED (errb)) 629 Error_Behavior UNUSED (errb))
496 { 630 {
497 /* #### should deal with ERRB */ 631 /* #### should deal with ERRB */
498 EXTERNAL_PROPERTY_LIST_LOOP_3 (range, data, value) 632 EXTERNAL_PROPERTY_LIST_LOOP_3 (range, data, value)
507 641
508 return 1; 642 return 1;
509 } 643 }
510 644
511 static Lisp_Object 645 static Lisp_Object
512 rangetab_instantiate (Lisp_Object data) 646 rangetab_instantiate (Lisp_Object plist)
513 { 647 {
514 Lisp_Object rangetab = Fmake_range_table (); 648 Lisp_Object data = Qnil, type = Qnil;
515 649
516 if (!NILP (data)) 650 PROPERTY_LIST_LOOP_3 (key, value, plist)
517 { 651 {
518 data = Fcar (Fcdr (data)); /* skip over 'data keyword */ 652 if (EQ (key, Qtype)) type = value;
519 while (!NILP (data)) 653 else if (EQ (key, Qdata)) data = value;
520 { 654 else
521 Lisp_Object range = Fcar (data); 655 abort ();
522 Lisp_Object val = Fcar (Fcdr (data)); 656 }
523 657
524 data = Fcdr (Fcdr (data)); 658 Lisp_Object rangetab = Fmake_range_table (type);
525 if (CONSP (range)) 659
526 Fput_range_table (Fcar (range), Fcar (Fcdr (range)), val, 660 {
527 rangetab); 661 PROPERTY_LIST_LOOP_3 (range, val, data)
528 else 662 {
529 Fput_range_table (range, range, val, rangetab); 663 if (CONSP (range))
530 } 664 Fput_range_table (Fcar (range), Fcar (Fcdr (range)), val,
531 } 665 rangetab);
666 else
667 Fput_range_table (range, range, val, rangetab);
668 }
669 }
532 670
533 return rangetab; 671 return rangetab;
534 } 672 }
535 673
536 674
731 INIT_LRECORD_IMPLEMENTATION (range_table); 869 INIT_LRECORD_IMPLEMENTATION (range_table);
732 870
733 DEFSYMBOL_MULTIWORD_PREDICATE (Qrange_tablep); 871 DEFSYMBOL_MULTIWORD_PREDICATE (Qrange_tablep);
734 DEFSYMBOL (Qrange_table); 872 DEFSYMBOL (Qrange_table);
735 873
874 DEFSYMBOL (Qstart_closed_end_open);
875 DEFSYMBOL (Qstart_open_end_open);
876 DEFSYMBOL (Qstart_closed_end_closed);
877 DEFSYMBOL (Qstart_open_end_closed);
878
736 DEFSUBR (Frange_table_p); 879 DEFSUBR (Frange_table_p);
880 DEFSUBR (Frange_table_type);
737 DEFSUBR (Fmake_range_table); 881 DEFSUBR (Fmake_range_table);
738 DEFSUBR (Fcopy_range_table); 882 DEFSUBR (Fcopy_range_table);
739 DEFSUBR (Fget_range_table); 883 DEFSUBR (Fget_range_table);
740 DEFSUBR (Fput_range_table); 884 DEFSUBR (Fput_range_table);
741 DEFSUBR (Fremove_range_table); 885 DEFSUBR (Fremove_range_table);
749 struct structure_type *st; 893 struct structure_type *st;
750 894
751 st = define_structure_type (Qrange_table, 0, rangetab_instantiate); 895 st = define_structure_type (Qrange_table, 0, rangetab_instantiate);
752 896
753 define_structure_type_keyword (st, Qdata, rangetab_data_validate); 897 define_structure_type_keyword (st, Qdata, rangetab_data_validate);
754 } 898 define_structure_type_keyword (st, Qtype, rangetab_type_validate);
899 }