cgit.sxemacs.org Git - sxemacs/blob - src/rangetab.c

   1 /* SXEmacs routines to deal with range tables.
   2    Copyright (C) 1995 Sun Microsystems, Inc.
   3    Copyright (C) 1995 Ben Wing.
   4
   5 This file is part of SXEmacs
   6
   7 SXEmacs is free software: you can redistribute it and/or modify
   8 it under the terms of the GNU General Public License as published by
   9 the Free Software Foundation, either version 3 of the License, or
  10 (at your option) any later version.
  11
  12 SXEmacs is distributed in the hope that it will be useful,
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 GNU General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with this program.  If not, see <http://www.gnu.org/licenses/>. */
  19
  20
  21 /* Synched up with: Not in FSF. */
  22
  23 /* Written by Ben Wing, August 1995. */
  24
  25 #include <config.h>
  26 #include "lisp.h"
  27 #include "rangetab.h"
  28
  29 Lisp_Object Qrange_tablep;
  30 Lisp_Object Qrange_table;
  31 \f
  32 /************************************************************************/
  33 /*                            Range table object                        */
  34 /************************************************************************/
  35
  36 /* We use a sorted array of ranges.
  37
  38    #### We should be using the gap array stuff from extents.c.  This
  39    is not hard but just requires moving that stuff out of that file. */
  40
  41 static Lisp_Object mark_range_table(Lisp_Object obj)
  42 {
  43         Lisp_Range_Table *rt = XRANGE_TABLE(obj);
  44         int i;
  45
  46         for (i = 0; i < Dynarr_length(rt->entries); i++)
  47                 mark_object(Dynarr_at(rt->entries, i).val);
  48         return Qnil;
  49 }
  50
  51 static void
  52 print_range_table(Lisp_Object obj, Lisp_Object printcharfun, int escapeflag)
  53 {
  54         Lisp_Range_Table *rt = XRANGE_TABLE(obj);
  55         char buf[200];
  56         int i;
  57
  58         write_c_string("#s(range-table data (", printcharfun);
  59         for (i = 0; i < Dynarr_length(rt->entries); i++) {
  60                 struct range_table_entry *rte = Dynarr_atp(rt->entries, i);
  61                 if (i > 0)
  62                         write_c_string(" ", printcharfun);
  63                 if (rte->first == rte->last)
  64                         sprintf(buf, "%ld ", (long)(rte->first));
  65                 else
  66                         sprintf(buf, "(%ld %ld) ", (long)(rte->first),
  67                                 (long)(rte->last));
  68                 write_c_string(buf, printcharfun);
  69                 print_internal(rte->val, printcharfun, 1);
  70         }
  71         write_c_string("))", printcharfun);
  72 }
  73
  74 static int range_table_equal(Lisp_Object obj1, Lisp_Object obj2, int depth)
  75 {
  76         Lisp_Range_Table *rt1 = XRANGE_TABLE(obj1);
  77         Lisp_Range_Table *rt2 = XRANGE_TABLE(obj2);
  78         int i;
  79
  80         if (Dynarr_length(rt1->entries) != Dynarr_length(rt2->entries))
  81                 return 0;
  82
  83         for (i = 0; i < Dynarr_length(rt1->entries); i++) {
  84                 struct range_table_entry *rte1 = Dynarr_atp(rt1->entries, i);
  85                 struct range_table_entry *rte2 = Dynarr_atp(rt2->entries, i);
  86
  87                 if (rte1->first != rte2->first
  88                     || rte1->last != rte2->last
  89                     || !internal_equal(rte1->val, rte2->val, depth + 1))
  90                         return 0;
  91         }
  92
  93         return 1;
  94 }
  95
  96 static unsigned long
  97 range_table_entry_hash(struct range_table_entry *rte, int depth)
  98 {
  99         return HASH3(rte->first, rte->last, internal_hash(rte->val, depth + 1));
 100 }
 101
 102 static unsigned long range_table_hash(Lisp_Object obj, int depth)
 103 {
 104         Lisp_Range_Table *rt = XRANGE_TABLE(obj);
 105         int i;
 106         int size = Dynarr_length(rt->entries);
 107         unsigned long hash = size;
 108
 109         /* approach based on internal_array_hash(). */
 110         if (size <= 5) {
 111                 for (i = 0; i < size; i++)
 112                         hash = HASH2(hash,
 113                                      range_table_entry_hash(Dynarr_atp
 114                                                             (rt->entries, i),
 115                                                             depth));
 116                 return hash;
 117         }
 118
 119         /* just pick five elements scattered throughout the array.
 120            A slightly better approach would be to offset by some
 121            noise factor from the points chosen below. */
 122         for (i = 0; i < 5; i++)
 123                 hash =
 124                     HASH2(hash,
 125                           range_table_entry_hash(Dynarr_atp
 126                                                  (rt->entries, i * size / 5),
 127                                                  depth));
 128         return hash;
 129 }
 130
 131 static const struct lrecord_description rte_description_1[] = {
 132         {XD_LISP_OBJECT, offsetof(range_table_entry, val)},
 133         {XD_END}
 134 };
 135
 136 static const struct struct_description rte_description = {
 137         sizeof(range_table_entry),
 138         rte_description_1
 139 };
 140
 141 static const struct lrecord_description rted_description_1[] = {
 142         XD_DYNARR_DESC(range_table_entry_dynarr, &rte_description),
 143         {XD_END}
 144 };
 145
 146 static const struct struct_description rted_description = {
 147         sizeof(range_table_entry_dynarr),
 148         rted_description_1
 149 };
 150
 151 static const struct lrecord_description range_table_description[] = {
 152         {XD_STRUCT_PTR, offsetof(Lisp_Range_Table, entries), 1,
 153          &rted_description},
 154         {XD_END}
 155 };
 156
 157 DEFINE_LRECORD_IMPLEMENTATION("range-table", range_table,
 158                               mark_range_table, print_range_table, 0,
 159                               range_table_equal, range_table_hash,
 160                               range_table_description, Lisp_Range_Table);
 161 \f
 162 /************************************************************************/
 163 /*                        Range table operations                        */
 164 /************************************************************************/
 165
 166 #ifdef ERROR_CHECK_TYPECHECK
 167
 168 static void verify_range_table(Lisp_Range_Table * rt)
 169 {
 170         int i;
 171
 172         for (i = 0; i < Dynarr_length(rt->entries); i++) {
 173                 struct range_table_entry *rte = Dynarr_atp(rt->entries, i);
 174                 assert(rte->last >= rte->first);
 175                 if (i > 0)
 176                         assert(Dynarr_at(rt->entries, i - 1).last < rte->first);
 177         }
 178 }
 179
 180 #else
 181
 182 #define verify_range_table(rt)
 183
 184 #endif
 185
 186 /* Look up in a range table without the Dynarr wrapper.
 187    Used also by the unified range table format. */
 188
 189 static Lisp_Object
 190 get_range_table(EMACS_INT pos, int nentries, struct range_table_entry *tab,
 191                 Lisp_Object default_)
 192 {
 193         int left = 0, right = nentries;
 194
 195         /* binary search for the entry.  Based on similar code in
 196            extent_list_locate(). */
 197         while (left != right) {
 198                 /* RIGHT might not point to a valid entry (i.e. it's at the end
 199                    of the list), so NEWPOS must round down. */
 200                 unsigned int newpos = (left + right) >> 1;
 201                 struct range_table_entry *entry = tab + newpos;
 202                 if (pos > entry->last)
 203                         left = newpos + 1;
 204                 else if (pos < entry->first)
 205                         right = newpos;
 206                 else
 207                         return entry->val;
 208         }
 209
 210         return default_;
 211 }
 212
 213 DEFUN("range-table-p", Frange_table_p, 1, 1, 0, /*
 214 Return non-nil if OBJECT is a range table.
 215 */
 216       (object))
 217 {
 218         return RANGE_TABLEP(object) ? Qt : Qnil;
 219 }
 220
 221 DEFUN("make-range-table", Fmake_range_table, 0, 0, 0,   /*
 222 Return a new, empty range table.
 223 You can manipulate it using `put-range-table', `get-range-table',
 224 `remove-range-table', and `clear-range-table'.
 225 */
 226       ())
 227 {
 228         Lisp_Object obj;
 229         Lisp_Range_Table *rt = alloc_lcrecord_type(Lisp_Range_Table,
 230                                                    &lrecord_range_table);
 231         rt->entries = Dynarr_new(range_table_entry);
 232         XSETRANGE_TABLE(obj, rt);
 233         return obj;
 234 }
 235
 236 DEFUN("copy-range-table", Fcopy_range_table, 1, 1, 0,   /*
 237 Return a new range table which is a copy of RANGE-TABLE.
 238 It will contain the same values for the same ranges as RANGE-TABLE.
 239 The values will not themselves be copied.
 240 */
 241       (range_table))
 242 {
 243         Lisp_Range_Table *rt, *rtnew;
 244         Lisp_Object obj;
 245
 246         CHECK_RANGE_TABLE(range_table);
 247         rt = XRANGE_TABLE(range_table);
 248
 249         rtnew = alloc_lcrecord_type(Lisp_Range_Table, &lrecord_range_table);
 250         rtnew->entries = Dynarr_new(range_table_entry);
 251
 252         Dynarr_add_many(rtnew->entries, Dynarr_atp(rt->entries, 0),
 253                         Dynarr_length(rt->entries));
 254         XSETRANGE_TABLE(obj, rtnew);
 255         return obj;
 256 }
 257
 258 DEFUN("get-range-table", Fget_range_table, 2, 3, 0,     /*
 259 Find value for position POS in RANGE-TABLE.
 260 If there is no corresponding value, return DEFAULT (defaults to nil).
 261 */
 262       (pos, range_table, default_))
 263 {
 264         Lisp_Range_Table *rt;
 265
 266         CHECK_RANGE_TABLE(range_table);
 267         rt = XRANGE_TABLE(range_table);
 268
 269         CHECK_INT_COERCE_CHAR(pos);
 270
 271         return get_range_table(XINT(pos), Dynarr_length(rt->entries),
 272                                Dynarr_atp(rt->entries, 0), default_);
 273 }
 274
 275 void
 276 put_range_table(Lisp_Object table, EMACS_INT first,
 277                 EMACS_INT last, Lisp_Object val)
 278 {
 279         int i;
 280         int insert_me_here = -1;
 281         Lisp_Range_Table *rt = XRANGE_TABLE(table);
 282
 283         /* Now insert in the proper place.  This gets tricky because
 284            we may be overlapping one or more existing ranges and need
 285            to fix them up. */
 286
 287         /* First delete all sections of any existing ranges that overlap
 288            the new range. */
 289         for (i = 0; i < Dynarr_length(rt->entries); i++) {
 290                 struct range_table_entry *entry = Dynarr_atp(rt->entries, i);
 291                 /* We insert before the first range that begins at or after the
 292                    new range. */
 293                 if (entry->first >= first && insert_me_here < 0)
 294                         insert_me_here = i;
 295                 if (entry->last < first)
 296                         /* completely before the new range. */
 297                         continue;
 298                 if (entry->first > last)
 299                         /* completely after the new range.  No more possibilities of
 300                            finding overlapping ranges. */
 301                         break;
 302                 if (entry->first < first && entry->last <= last) {
 303                         /* looks like:
 304
 305                            [ NEW ]
 306                            [ EXISTING ]
 307
 308                          */
 309                         /* truncate the end off of it. */
 310                         entry->last = first - 1;
 311                 } else if (entry->first < first && entry->last > last)
 312                         /* looks like:
 313
 314                            [ NEW ]
 315                            [ EXISTING ]
 316
 317                          */
 318                         /* need to split this one in two. */
 319                 {
 320                         struct range_table_entry insert_me_too;
 321
 322                         insert_me_too.first = last + 1;
 323                         insert_me_too.last = entry->last;
 324                         insert_me_too.val = entry->val;
 325                         entry->last = first - 1;
 326                         Dynarr_insert_many(rt->entries, &insert_me_too, 1,
 327                                            i + 1);
 328                 } else if (entry->last > last) {
 329                         /* looks like:
 330
 331                            [ NEW ]
 332                            [ EXISTING ]
 333
 334                          */
 335                         /* truncate the start off of it. */
 336                         entry->first = last + 1;
 337                 } else {
 338                         /* existing is entirely within new. */
 339                         Dynarr_delete_many(rt->entries, i, 1);
 340                         i--;    /* back up since everything shifted one to the left. */
 341                 }
 342         }
 343
 344         /* Someone asked us to delete the range, not insert it. */
 345         if (UNBOUNDP(val))
 346                 return;
 347
 348         /* Now insert the new entry, maybe at the end. */
 349
 350         if (insert_me_here < 0)
 351                 insert_me_here = i;
 352
 353         {
 354                 struct range_table_entry insert_me;
 355
 356                 insert_me.first = first;
 357                 insert_me.last = last;
 358                 insert_me.val = val;
 359
 360                 Dynarr_insert_many(rt->entries, &insert_me, 1, insert_me_here);
 361         }
 362
 363         /* Now see if we can combine this entry with adjacent ones just
 364            before or after. */
 365
 366         if (insert_me_here > 0) {
 367                 struct range_table_entry *entry = Dynarr_atp(rt->entries,
 368                                                              insert_me_here -
 369                                                              1);
 370                 if (EQ(val, entry->val) && entry->last == first - 1) {
 371                         entry->last = last;
 372                         Dynarr_delete_many(rt->entries, insert_me_here, 1);
 373                         insert_me_here--;
 374                         /* We have morphed into a larger range.  Update our records
 375                            in case we also combine with the one after. */
 376                         first = entry->first;
 377                 }
 378         }
 379
 380         if (insert_me_here < Dynarr_length(rt->entries) - 1) {
 381                 struct range_table_entry *entry = Dynarr_atp(rt->entries,
 382                                                              insert_me_here +
 383                                                              1);
 384                 if (EQ(val, entry->val) && entry->first == last + 1) {
 385                         entry->first = first;
 386                         Dynarr_delete_many(rt->entries, insert_me_here, 1);
 387                 }
 388         }
 389 }
 390
 391 DEFUN("put-range-table", Fput_range_table, 4, 4, 0,     /*
 392 Set the value for range (START, END) to be VALUE in RANGE-TABLE.
 393 */
 394       (start, end, value, range_table))
 395 {
 396         EMACS_INT first, last;
 397
 398         CHECK_RANGE_TABLE(range_table);
 399         CHECK_INT_COERCE_CHAR(start);
 400         first = XINT(start);
 401         CHECK_INT_COERCE_CHAR(end);
 402         last = XINT(end);
 403         if (first > last)
 404                 signal_simple_error_2("start must be <= end", start, end);
 405
 406         put_range_table(range_table, first, last, value);
 407         verify_range_table(XRANGE_TABLE(range_table));
 408         return Qnil;
 409 }
 410
 411 DEFUN("remove-range-table", Fremove_range_table, 3, 3, 0,       /*
 412 Remove the value for range (START, END) in RANGE-TABLE.
 413 */
 414       (start, end, range_table))
 415 {
 416         return Fput_range_table(start, end, Qunbound, range_table);
 417 }
 418
 419 DEFUN("clear-range-table", Fclear_range_table, 1, 1, 0, /*
 420 Flush RANGE-TABLE.
 421 */
 422       (range_table))
 423 {
 424         CHECK_RANGE_TABLE(range_table);
 425         Dynarr_reset(XRANGE_TABLE(range_table)->entries);
 426         return Qnil;
 427 }
 428
 429 DEFUN("map-range-table", Fmap_range_table, 2, 2, 0,     /*
 430 Map FUNCTION over entries in RANGE-TABLE, calling it with three args,
 431 the beginning and end of the range and the corresponding value.
 432
 433 Results are guaranteed to be correct (i.e. each entry processed
 434 exactly once) if FUNCTION modifies or deletes the current entry
 435 \(i.e. passes the current range to `put-range-table' or
 436 `remove-range-table'), but not otherwise.
 437 */
 438       (function, range_table))
 439 {
 440         Lisp_Range_Table *rt;
 441         int i;
 442
 443         CHECK_RANGE_TABLE(range_table);
 444         CHECK_FUNCTION(function);
 445
 446         rt = XRANGE_TABLE(range_table);
 447
 448         /* Do not "optimize" by pulling out the length computation below!
 449            FUNCTION may have changed the table. */
 450         for (i = 0; i < Dynarr_length(rt->entries); i++) {
 451                 struct range_table_entry *entry = Dynarr_atp(rt->entries, i);
 452                 EMACS_INT first, last;
 453                 Lisp_Object args[4];
 454                 int oldlen;
 455
 456               again:
 457                 first = entry->first;
 458                 last = entry->last;
 459                 oldlen = Dynarr_length(rt->entries);
 460                 args[0] = function;
 461                 args[1] = make_int(first);
 462                 args[2] = make_int(last);
 463                 args[3] = entry->val;
 464                 Ffuncall(countof(args), args);
 465                 /* Has FUNCTION removed the entry? */
 466                 if (oldlen > Dynarr_length(rt->entries)
 467                     && i < Dynarr_length(rt->entries)
 468                     && (first != entry->first || last != entry->last))
 469                         goto again;
 470         }
 471
 472         return Qnil;
 473 }
 474 \f
 475 /************************************************************************/
 476 /*                         Range table read syntax                      */
 477 /************************************************************************/
 478
 479 static int
 480 rangetab_data_validate(Lisp_Object keyword, Lisp_Object value,
 481                        Error_behavior errb)
 482 {
 483         Lisp_Object rest;
 484
 485         /* #### should deal with errb */
 486         EXTERNAL_LIST_LOOP(rest, value) {
 487                 Lisp_Object range = XCAR(rest);
 488                 rest = XCDR(rest);
 489                 if (!CONSP(rest))
 490                         signal_simple_error("Invalid list format", value);
 491                 if (!INTP(range) && !CHARP(range)
 492                     && !(CONSP(range) && CONSP(XCDR(range))
 493                          && NILP(XCDR(XCDR(range)))
 494                          && (INTP(XCAR(range)) || CHARP(XCAR(range)))
 495                          && (INTP(XCAR(XCDR(range)))
 496                              || CHARP(XCAR(XCDR(range))))))
 497                         signal_simple_error("Invalid range format", range);
 498         }
 499
 500         return 1;
 501 }
 502
 503 static Lisp_Object rangetab_instantiate(Lisp_Object data)
 504 {
 505         Lisp_Object rangetab = Fmake_range_table();
 506
 507         if (!NILP(data)) {
 508                 data = Fcar(Fcdr(data));        /* skip over 'data keyword */
 509                 while (!NILP(data)) {
 510                         Lisp_Object range = Fcar(data);
 511                         Lisp_Object val = Fcar(Fcdr(data));
 512
 513                         data = Fcdr(Fcdr(data));
 514                         if (CONSP(range))
 515                                 Fput_range_table(Fcar(range), Fcar(Fcdr(range)),
 516                                                  val, rangetab);
 517                         else
 518                                 Fput_range_table(range, range, val, rangetab);
 519                 }
 520         }
 521
 522         return rangetab;
 523 }
 524 \f
 525 /************************************************************************/
 526 /*                         Unified range tables                         */
 527 /************************************************************************/
 528
 529 /* A "unified range table" is a format for storing range tables
 530    as contiguous blocks of memory.  This is used by the regexp
 531    code, which needs to use range tables to properly handle []
 532    constructs in the presence of extended characters but wants to
 533    store an entire compiled pattern as a contiguous block of memory.
 534
 535    Unified range tables are designed so that they can be placed
 536    at an arbitrary (possibly mis-aligned) place in memory.
 537    (Dealing with alignment is a pain in the ass.)
 538
 539    WARNING: No provisions for garbage collection are currently made.
 540    This means that there must not be any Lisp objects in a unified
 541    range table that need to be marked for garbage collection.
 542    Good candidates for objects that can go into a range table are
 543
 544    -- numbers and characters (do not need to be marked)
 545    -- nil, t (marked elsewhere)
 546    -- charsets and coding systems (automatically marked because
 547                                    they are in a marked list,
 548                                    and can't be removed)
 549
 550    Good but slightly less so:
 551
 552    -- symbols (could be uninterned, but that is not likely)
 553
 554    Somewhat less good:
 555
 556    -- buffers, frames, devices (could get deleted)
 557
 558    It is expected that you work with range tables in the normal
 559    format and then convert to unified format when you are done
 560    making modifications.  As such, no functions are provided
 561    for modifying a unified range table.  The only operations
 562    you can do to unified range tables are
 563
 564    -- look up a value
 565    -- retrieve all the ranges in an iterative fashion
 566
 567 */
 568
 569 /* The format of a unified range table is as follows:
 570
 571    -- The first byte contains the number of bytes to skip to find the
 572       actual start of the table.  This deals with alignment constraints,
 573       since the table might want to go at any arbitrary place in memory.
 574    -- The next three bytes contain the number of bytes to skip (from the
 575       *first* byte) to find the stuff after the table.  It's stored in
 576       little-endian format because that's how God intended things.  We don't
 577       necessarily start the stuff at the very end of the table because
 578       we want to have at least ALIGNOF (EMACS_INT) extra space in case
 579       we have to move the range table around. (It appears that some
 580       architectures don't maintain alignment when reallocing.)
 581    -- At the prescribed offset is a struct unified_range_table, containing
 582       some number of `struct range_table_entry' entries. */
 583
 584 struct unified_range_table {
 585         int nentries;
 586         struct range_table_entry first;
 587 };
 588
 589 /* Return size in bytes needed to store the data in a range table. */
 590
 591 int unified_range_table_bytes_needed(Lisp_Object rangetab)
 592 {
 593         return (sizeof(struct range_table_entry) *
 594                 (Dynarr_length(XRANGE_TABLE(rangetab)->entries) - 1) +
 595                 sizeof(struct unified_range_table) +
 596                 /* ALIGNOF a struct may be too big. */
 597                 /* We have four bytes for the size numbers, and an extra
 598                    four or eight bytes for making sure we get the alignment
 599                    OK. */
 600                 ALIGNOF(EMACS_INT) + 4);
 601 }
 602
 603 /* Convert a range table into unified format and store in DEST,
 604    which must be able to hold the number of bytes returned by
 605    range_table_bytes_needed(). */
 606
 607 void unified_range_table_copy_data(Lisp_Object rangetab, void *dest)
 608 {
 609         /* We cast to the above structure rather than just casting to
 610            char * and adding sizeof(int), because that will lead to
 611            mis-aligned data on the Alpha machines. */
 612         struct unified_range_table *un;
 613         range_table_entry_dynarr *rted = XRANGE_TABLE(rangetab)->entries;
 614         int total_needed = unified_range_table_bytes_needed(rangetab);
 615         void *new_dest = ALIGN_PTR((char *)dest + 4, ALIGNOF(EMACS_INT));
 616
 617         *(char *)dest = (char)((char *)new_dest - (char *)dest);
 618         *((unsigned char *)dest + 1) = total_needed & 0xFF;
 619         total_needed >>= 8;
 620         *((unsigned char *)dest + 2) = total_needed & 0xFF;
 621         total_needed >>= 8;
 622         *((unsigned char *)dest + 3) = total_needed & 0xFF;
 623         un = (struct unified_range_table *)new_dest;
 624         un->nentries = Dynarr_length(rted);
 625         memcpy(&un->first, Dynarr_atp(rted, 0),
 626                sizeof(struct range_table_entry) * Dynarr_length(rted));
 627 }
 628
 629 /* Return number of bytes actually used by a unified range table. */
 630
 631 int unified_range_table_bytes_used(const void *unrangetab)
 632 {
 633         return ((*((const unsigned char*)unrangetab + 1))
 634                 + ((*((const unsigned char*)unrangetab + 2)) << 8)
 635                 + ((*((const unsigned char*)unrangetab + 3)) << 16));
 636 }
 637
 638 /* Make sure the table is aligned, and move it around if it's not. */
 639 static void
 640 align_the_damn_table(void *unrangetab)
 641 {
 642         const void *cur_dest = (char*)unrangetab + *(char*)unrangetab;
 643 #if SXE_LONGBITS == 64
 644         if ((((long)cur_dest) & 7) != 0)
 645 #else
 646         if ((((int)cur_dest) & 3) != 0)
 647 #endif
 648         {
 649                 int count = (unified_range_table_bytes_used(unrangetab) - 4
 650                              - ALIGNOF(EMACS_INT));
 651                 /* Find the proper location, just like above. */
 652                 void *new_dest = ALIGN_PTR((char*)unrangetab + 4,
 653                                            ALIGNOF(EMACS_INT));
 654                 /* memmove() works in the presence of overlapping data. */
 655                 memmove(new_dest, cur_dest, count);
 656                 *(char*)unrangetab =
 657                         (char)((char*)new_dest - (char*)unrangetab);
 658         }
 659 }
 660
 661 /* Look up a value in a unified range table. */
 662
 663 Lisp_Object
 664 unified_range_table_lookup(void *unrangetab, EMACS_INT pos,
 665                            Lisp_Object default_)
 666 {
 667         void *new_dest;
 668         struct unified_range_table *un;
 669
 670         align_the_damn_table(unrangetab);
 671         new_dest = (char *)unrangetab + *(char *)unrangetab;
 672         un = (struct unified_range_table *)new_dest;
 673
 674         return get_range_table(pos, un->nentries, &un->first, default_);
 675 }
 676
 677 /* Return number of entries in a unified range table. */
 678
 679 int
 680 unified_range_table_nentries(void *unrangetab)
 681 {
 682         void *new_dest;
 683         struct unified_range_table *un;
 684
 685         align_the_damn_table(unrangetab);
 686         new_dest = (char *)unrangetab + *(char *)unrangetab;
 687         un = (struct unified_range_table *)new_dest;
 688         return un->nentries;
 689 }
 690
 691 /* Return the OFFSETth range (counting from 0) in UNRANGETAB. */
 692 void
 693 unified_range_table_get_range(void *unrangetab, int offset,
 694                               EMACS_INT * min, EMACS_INT * max,
 695                               Lisp_Object * val)
 696 {
 697         void *new_dest;
 698         struct unified_range_table *un;
 699         struct range_table_entry *tab;
 700
 701         align_the_damn_table(unrangetab);
 702         new_dest = (char *)unrangetab + *(char *)unrangetab;
 703         un = (struct unified_range_table *)new_dest;
 704
 705         assert(offset >= 0 && offset < un->nentries);
 706         tab = (&un->first) + offset;
 707         *min = tab->first;
 708         *max = tab->last;
 709         *val = tab->val;
 710 }
 711 \f
 712 /************************************************************************/
 713 /*                            Initialization                            */
 714 /************************************************************************/
 715
 716 void syms_of_rangetab(void)
 717 {
 718         INIT_LRECORD_IMPLEMENTATION(range_table);
 719
 720         defsymbol(&Qrange_tablep, "range-table-p");
 721         defsymbol(&Qrange_table, "range-table");
 722
 723         DEFSUBR(Frange_table_p);
 724         DEFSUBR(Fmake_range_table);
 725         DEFSUBR(Fcopy_range_table);
 726         DEFSUBR(Fget_range_table);
 727         DEFSUBR(Fput_range_table);
 728         DEFSUBR(Fremove_range_table);
 729         DEFSUBR(Fclear_range_table);
 730         DEFSUBR(Fmap_range_table);
 731 }
 732
 733 void structure_type_create_rangetab(void)
 734 {
 735         struct structure_type *st;
 736
 737         st = define_structure_type(Qrange_table, 0, rangetab_instantiate);
 738
 739         define_structure_type_keyword(st, Qdata, rangetab_data_validate);
 740 }