source/rangeset.c

   1 /* $Id: rangeset.c,v 1.6 2003/05/09 17:43:47 edg Exp $ */
   2 /*******************************************************************************
   3 *                                                                              *
   4 * rangeset.c     -- Nirvana Editor rangest functions                           *
   5 *                                                                              *
   6 * Copyright (C) 1999 Mark Edel                                                 *
   7 *                                                                              *
   8 * This is free software; you can redistribute it and/or modify it under the    *
   9 * terms of the GNU General Public License as published by the Free Software    *
  10 * Foundation; either version 2 of the License, or (at your option) any later   *
  11 * version.                                                                     *
  12 *                                                                              *
  13 * This software is distributed in the hope that it will be useful, but WITHOUT *
  14 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or        *
  15 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License        *
  16 * for more details.                                                            *
  17 *                                                                              *
  18 * You should have received a copy of the GNU General Public License along with *
  19 * software; if not, write to the Free Software Foundation, Inc., 59 Temple     *
  20 * Place, Suite 330, Boston, MA  02111-1307 USA                                 *
  21 *                                                                              *
  22 * Nirvana Text Editor                                                          *
  23 * Sep 26, 2002                                                                 *
  24 *                                                                              *
  25 * Written by Tony Balinski with contributions from Andrew Hood                 *
  26 *                                                                              *
  27 * Modifications:                                                               *
  28 *                                                                              *
  29 *                                                                              *
  30 *******************************************************************************/
  31 #ifdef HAVE_CONFIG_H
  32 #include "../config.h"
  33 #endif
  34
  35 #include "textBuf.h"
  36 #include "textDisp.h"
  37 #include "rangeset.h"
  38
  39 #include <stdio.h>
  40 #include <stdlib.h>
  41 #include <string.h>
  42 #include <ctype.h>
  43
  44 #ifdef HAVE_DEBUG_H
  45 #include "../debug.h"
  46 #endif
  47
  48 /* -------------------------------------------------------------------------- */
  49
  50 struct _Range {
  51     int start, end;                     /* range from [start-]end */
  52 };
  53
  54 typedef Rangeset *RangesetUpdateFn(Rangeset *p, int pos, int ins, int del);
  55
  56 struct _Rangeset {
  57     RangesetUpdateFn *update_fn;        /* modification update function */
  58     char *update_name;                  /* update function name */
  59     int maxpos;                         /* text buffer maxpos */
  60     int last_index;                     /* a place to start looking */
  61     int n_ranges;                       /* how many ranges in ranges */
  62     Range *ranges;                      /* the ranges table */
  63     unsigned char label;                /* a number 1-63 */
  64
  65     int color_set;                      /* 0: unset; 1: set; -1: invalid */
  66     char *color_name;                   /* the name of an assigned color */
  67     Pixel color;                        /* the value of a particular color */
  68     textBuffer *buf;                    /* the text buffer of the rangeset */
  69 };
  70
  71 struct _RangesetTable {
  72     int n_set;                          /* how many sets are active */
  73     textBuffer *buf;                    /* the text buffer of the rangeset */
  74     Rangeset set[N_RANGESETS];          /* the rangeset table */
  75     unsigned char order[N_RANGESETS];   /* inds of set[]s ordered by depth */
  76     unsigned char active[N_RANGESETS];  /* entry true if corresp. set active */
  77     unsigned char depth[N_RANGESETS];   /* depth[i]: pos of set[i] in order[] */
  78     unsigned char list[N_RANGESETS + 1];/* string of labels in depth order */
  79 };
  80
  81 /* -------------------------------------------------------------------------- */
  82
  83 #define SWAPval(T,a,b) { T t; t = *(a); *(a) = *(b); *(b) = t; }
  84
  85 static unsigned char rangeset_labels[N_RANGESETS + 1] = {
  86       58, 10, 15,  1, 27, 52, 14,  3, 61, 13, 31, 30, 45, 28, 41, 55,
  87       33, 20, 62, 34, 42, 18, 57, 47, 24, 49, 19, 50, 25, 38, 40,  2,
  88       21, 39, 59, 22, 60,  4,  6, 16, 29, 37, 48, 46, 54, 43, 32, 56,
  89       51,  7,  9, 63,  5,  8, 36, 44, 26, 11, 23, 17, 53, 35, 12, 0
  90    };
  91
  92 /* -------------------------------------------------------------------------- */
  93
  94 static RangesetUpdateFn rangesetInsDelMaintain;
  95 static RangesetUpdateFn rangesetInclMaintain;
  96 static RangesetUpdateFn rangesetDelInsMaintain;
  97 static RangesetUpdateFn rangesetExclMaintain;
  98 static RangesetUpdateFn rangesetBreakMaintain;
  99
 100 #define DEFAULT_UPDATE_FN_NAME  "maintain"
 101
 102 static struct {
 103     char *name;
 104     RangesetUpdateFn *update_fn;
 105 } RangesetUpdateMap[] = {
 106     {DEFAULT_UPDATE_FN_NAME,    rangesetInsDelMaintain},
 107     {"ins_del",                 rangesetInsDelMaintain},
 108     {"include",                 rangesetInclMaintain},
 109     {"del_ins",                 rangesetDelInsMaintain},
 110     {"exclude",                 rangesetExclMaintain},
 111     {"break",                   rangesetBreakMaintain},
 112     {(char *)0,                 (RangesetUpdateFn *)0}
 113 };
 114
 115 /* -------------------------------------------------------------------------- */
 116
 117 static Range *RangesNew(int n)
 118 {
 119     Range *newRanges;
 120
 121     if (n != 0) {
 122         /* We use a blocked allocation scheme here, with a block size of factor.
 123            Only allocations of multiples of factor will be allowed.
 124            Be sure to allocate at least one more than we really need, and
 125            round up to next higher multiple of factor, ie
 126                 n = (((n + 1) + factor - 1) / factor) * factor
 127            If we choose factor = (1 << factor_bits), we can use shifts
 128            instead of multiply/divide, ie
 129                 n = ((n + (1 << factor_bits)) >> factor_bits) << factor_bits
 130            or
 131                 n = (1 + (n >> factor_bits)) << factor_bits
 132            Since the shifts just strip the end 1 bits, we can even get away
 133            with
 134                 n = ((1 << factor_bits) + n) & (~0 << factor_bits);
 135            Finally, we decide on factor_bits according to the size of n:
 136            if n >= 256, we probably want less reallocation on growth than
 137            otherwise; choose some arbitrary values thus:
 138                 factor_bits = (n >= 256) ? 6 : 4
 139            so
 140                 n = (n >= 256) ? (n + (1<<6)) & (~0<<6) : (n + (1<<4)) & (~0<<4)
 141            or
 142                 n = (n >= 256) ? ((n + 64) & ~63) : ((n + 16) & ~15)
 143          */
 144         n = (n >= 256) ? ((n + 64) & ~63) : ((n + 16) & ~15);
 145         newRanges = (Range *)XtMalloc(n * sizeof (Range));
 146         return newRanges;
 147     }
 148
 149     return NULL;
 150 }
 151
 152 /* -------------------------------------------------------------------------- */
 153
 154 static Range* RangesRealloc(Range* ranges, int n)
 155 {
 156     int size;
 157     Range* newRanges;
 158
 159     if (n > 0)
 160     {
 161         /* see RangesNew() for comments */
 162         n = (n >= 256) ? ((n + 64) & ~63) : ((n + 16) & ~15);
 163         size = n * sizeof (Range);
 164         newRanges = (Range*) (ranges != NULL
 165                 ? XtRealloc((char *)ranges, size)
 166                 : XtMalloc(size));
 167         return newRanges;
 168     } else if (ranges != NULL)
 169     {
 170         XtFree((char*) ranges);
 171     }
 172
 173     return NULL;
 174 }
 175
 176 /* -------------------------------------------------------------------------- */
 177
 178 static Range *RangesFree(Range *ranges)
 179 {
 180     if (ranges != NULL)
 181         XtFree((char *)ranges);
 182
 183     return NULL;
 184 }
 185
 186 /* -------------------------------------------------------------------------- */
 187
 188 /*
 189 ** Refresh the given range on the screen. If the range indicated is null, we
 190 ** refresh the screen for the whole file.
 191 */
 192
 193 void RangesetRefreshRange(Rangeset *rangeset, int start, int end)
 194 {
 195     if (rangeset->buf != NULL)
 196         BufCheckDisplay(rangeset->buf, start, end);
 197 }
 198
 199 void RangesetRefreshAllRanges(Rangeset *rangeset)
 200 {
 201     int i;
 202
 203     for (i = 0; i < rangeset->n_ranges; i++)
 204         RangesetRefreshRange(rangeset, rangeset->ranges[i].start, rangeset->ranges[i].end);
 205 }
 206
 207 /* -------------------------------------------------------------------------- */
 208
 209 /*
 210 ** Remove all ranges from a range set.
 211 */
 212
 213 void RangesetEmpty(Rangeset *rangeset)
 214 {
 215     Range *ranges = rangeset->ranges;
 216     int start, end;
 217
 218     if (rangeset->color_name && rangeset->color_set > 0) {
 219         /* this range is colored: we need to clear it */
 220         rangeset->color_set = -1;
 221
 222         while (rangeset->n_ranges--) {
 223             start = ranges[rangeset->n_ranges].start;
 224             end = ranges[rangeset->n_ranges].end;
 225             RangesetRefreshRange(rangeset, start, end);
 226         }
 227     }
 228
 229     if (rangeset->color_name)
 230         XtFree(rangeset->color_name);
 231
 232     rangeset->color_name = (char *)0;
 233     rangeset->ranges = RangesFree(rangeset->ranges);
 234 }
 235
 236 /* -------------------------------------------------------------------------- */
 237
 238 /*
 239 ** Initialise a new range set.
 240 */
 241
 242 void RangesetInit(Rangeset *rangeset, unsigned char label, textBuffer *buf)
 243 {
 244     rangeset->label = label;                    /* a letter A-Z */
 245     rangeset->maxpos = 0;                       /* text buffer maxpos */
 246     rangeset->last_index = 0;                   /* a place to start looking */
 247     rangeset->n_ranges = 0;                     /* how many ranges in ranges */
 248     rangeset->ranges = (Range *)0;              /* the ranges table */
 249
 250     rangeset->color_name = (char *)0;
 251     rangeset->color_set = 0;
 252     rangeset->buf = buf;
 253
 254     rangeset->maxpos = buf->gapEnd - buf->gapStart + buf->length;
 255
 256     RangesetChangeModifyResponse(rangeset, DEFAULT_UPDATE_FN_NAME);
 257 }
 258
 259 /*
 260 ** Change a range set's modification behaviour. Returns true (non-zero)
 261 ** if the update function name was found, else false.
 262 */
 263
 264 int RangesetChangeModifyResponse(Rangeset *rangeset, char *name)
 265 {
 266     int i;
 267
 268     if (name == NULL)
 269         name = DEFAULT_UPDATE_FN_NAME;
 270
 271     for (i = 0; RangesetUpdateMap[i].name; i++)
 272         if (strcmp(RangesetUpdateMap[i].name, name) == 0) {
 273             rangeset->update_fn = RangesetUpdateMap[i].update_fn;
 274             rangeset->update_name = RangesetUpdateMap[i].name;
 275             return 1;
 276         }
 277
 278     return 0;
 279 }
 280
 281 /* -------------------------------------------------------------------------- */
 282
 283 /*
 284 ** Find the index of the first integer in table greater than or equal to pos.
 285 ** Fails with len (the total number of entries). The start index base can be
 286 ** chosen appropriately.
 287 */
 288
 289 static int at_or_before(int *table, int base, int len, int val)
 290 {
 291     int lo, mid=0, hi;
 292
 293     if (base >= len)
 294         return len;             /* not sure what this means! */
 295
 296     lo = base;                  /* first valid index */
 297     hi = len - 1;               /* last valid index */
 298
 299     while (lo <= hi) {
 300         mid = (lo + hi) / 2;
 301         if (val == table[mid])
 302             return mid;
 303         if (val < table[mid])
 304             hi = mid - 1;
 305         else
 306             lo = mid + 1;
 307     }
 308     /* if we get here, we didn't find val itself */
 309     if (val > table[mid])
 310         mid++;
 311
 312     return mid;
 313 }
 314
 315 static int weighted_at_or_before(int *table, int base, int len, int val)
 316 {
 317     int lo, mid=0, hi;
 318     int min, max;
 319
 320     if (base >= len)
 321         return len;             /* not sure what this means! */
 322
 323     lo = base;                  /* first valid index */
 324     hi = len - 1;               /* last valid index */
 325
 326     min = table[lo];            /* establish initial min/max */
 327     max = table[hi];
 328
 329     if (val <= min)             /* initial range checks */
 330         return lo;              /* needed to avoid out-of-range mid values */
 331     else if (val > max)
 332         return len;
 333     else if (val == max)
 334         return hi;
 335
 336     while (lo <= hi) {
 337         mid = lo + (hi - lo) * (max - val) / (max - min);
 338         /* we won't worry about min == max - values should be unique */
 339
 340         if (val == table[mid])
 341             return mid;
 342         if (val < table[mid]) {
 343             hi = mid - 1;
 344             max = table[mid];
 345         }
 346         else { /* val > table[mid] */
 347             lo = mid + 1;
 348             min = table[mid];
 349         }
 350     }
 351
 352     /* if we get here, we didn't find val itself */
 353     if (val > table[mid])
 354         return mid + 1;
 355
 356     return mid;
 357 }
 358
 359 /* -------------------------------------------------------------------------- */
 360
 361 /*
 362 ** Find out whether the position pos is included in one of the ranges of
 363 ** rangeset. Returns the containing range's index if true, -1 otherwise.
 364 ** Note: ranges are indexed from zero.
 365 */
 366
 367 int RangesetFindRangeNo(Rangeset *rangeset, int index, int *start, int *end)
 368 {
 369     if (!rangeset || index < 0 || rangeset->n_ranges <= index || !rangeset->ranges)
 370         return 0;
 371
 372     *start = rangeset->ranges[index].start;
 373     *end   = rangeset->ranges[index].end;
 374
 375     return 1;
 376 }
 377
 378 /*
 379 ** Find out whether the position pos is included in one of the ranges of
 380 ** rangeset. Returns the containing range's index if true, -1 otherwise.
 381 ** Note: ranges are indexed from zero.
 382 */
 383
 384 int RangesetFindRangeOfPos(Rangeset *rangeset, int pos, int incl_end)
 385 {
 386     int *ranges;
 387     int len, ind;
 388
 389     if (!rangeset || !rangeset->n_ranges || !rangeset->ranges)
 390         return -1;
 391
 392     ranges = (int *)rangeset->ranges;           /* { s1,e1, s2,e2, s3,e3,... } */
 393     len = rangeset->n_ranges * 2;
 394     ind = at_or_before(ranges, 0, len, pos);
 395
 396     if (ind == len)
 397         return -1;                      /* beyond end */
 398
 399     if (ind & 1) {                      /* ind odd: references an end marker */
 400         if (pos < ranges[ind] || (incl_end && pos == ranges[ind]))
 401             return ind / 2;             /* return the range index */
 402     }
 403     else {                              /* ind even: references start marker */
 404         if (pos == ranges[ind])
 405             return ind / 2;             /* return the range index */
 406     }
 407     return -1;                          /* not in any range */
 408 }
 409
 410 /*
 411 ** Find out whether the position pos is included in one of the ranges of
 412 ** rangeset. Returns the containing range's index if true, -1 otherwise.
 413 ** Essentially the same as the RangesetFindRangeOfPos() function, but uses the
 414 ** last_index member of the rangeset and weighted_at_or_before() for speedy
 415 ** lookup in refresh tasks. The rangeset is assumed to be valid, as is the
 416 ** position. We also don't allow checking of the endpoint.
 417 ** Returns the including range index, or -1 if not found.
 418 */
 419
 420 int RangesetCheckRangeOfPos(Rangeset *rangeset, int pos)
 421 {
 422     int *ranges;
 423     int len, index, last;
 424
 425     len = rangeset->n_ranges;
 426     if (len == 0)
 427         return -1;                      /* no ranges */
 428
 429     ranges = (int *)rangeset->ranges;           /* { s1,e1, s2,e2, s3,e3,... } */
 430     last = rangeset->last_index;
 431
 432     /* try to profit from the last lookup by using its index */
 433     if (last >= len || last < 0) {
 434         last = (len > 0) ? len - 1 : 0; /* make sure last is in range */
 435         rangeset->last_index = last;
 436     }
 437
 438     len *= 2;
 439     last *= 2;
 440
 441     if (pos >= ranges[last]) {          /* last even: this is a start */
 442         if (pos < ranges[last + 1])     /* checking an end here */
 443             return last / 2;            /* no need to change rangeset->last_index */
 444         else
 445             last += 2;                  /* not in this range: move on */
 446
 447         if (last == len)
 448             return -1;                  /* moved on too far */
 449
 450         /* find the entry in the upper portion of ranges */
 451         index = weighted_at_or_before(ranges, last, len, pos); /* search end only */
 452     }
 453     else if (last > 0) {
 454         index = weighted_at_or_before(ranges, 0, last, pos); /* search front only */
 455     }
 456     else
 457         index = 0;
 458
 459     rangeset->last_index = index / 2;
 460
 461     if (index == len)
 462         return -1;                      /* beyond end */
 463
 464     if (index & 1) {                    /* index odd: references an end marker */
 465         if (pos < ranges[index])
 466             return index / 2;           /* return the range index */
 467     }
 468     else {                              /* index even: references start marker */
 469         if (pos == ranges[index])
 470             return index / 2;           /* return the range index */
 471     }
 472     return -1;                          /* not in any range */
 473 }
 474
 475 /* -------------------------------------------------------------------------- */
 476
 477 /*
 478 ** Merge the ranges in rangeset plusSet into rangeset origSet.
 479 */
 480
 481 int RangesetAdd(Rangeset *origSet, Rangeset *plusSet)
 482 {
 483     Range *origRanges, *plusRanges, *newRanges, *oldRanges;
 484     int nOrigRanges, nPlusRanges;
 485     int isOld;
 486
 487     origRanges = origSet->ranges;
 488     nOrigRanges = origSet->n_ranges;
 489
 490     plusRanges = plusSet->ranges;
 491     nPlusRanges = plusSet->n_ranges;
 492
 493     if (nPlusRanges == 0)
 494         return nOrigRanges;     /* no ranges in plusSet - nothing to do */
 495
 496     newRanges = RangesNew(nOrigRanges + nPlusRanges);
 497
 498     if (nOrigRanges == 0) {
 499         /* no ranges in destination: just copy the ranges from the other set */
 500         memcpy(newRanges, plusRanges, nPlusRanges * sizeof (Range));
 501         RangesFree(origSet->ranges);
 502         origSet->ranges = newRanges;
 503         origSet->n_ranges = nPlusRanges;
 504         for (nOrigRanges = 0; nOrigRanges < nPlusRanges; nOrigRanges++) {
 505             RangesetRefreshRange(origSet, newRanges->start, newRanges->end);
 506             newRanges++;
 507         }
 508         return nPlusRanges;
 509     }
 510
 511     oldRanges = origRanges;
 512     origSet->ranges = newRanges;
 513     origSet->n_ranges = 0;
 514
 515     /* in the following we merrily swap the pointers/counters of the two input
 516        ranges (from origSet and plusSet) - don't worry, they're both consulted
 517        read-only - building the merged set in newRanges */
 518
 519     isOld = 1;          /* true if origRanges points to a range in oldRanges[] */
 520
 521     while (nOrigRanges > 0 || nPlusRanges > 0) {
 522         /* make the range with the lowest start value the origRanges range */
 523         if (nOrigRanges == 0 ||
 524               (nPlusRanges > 0 && origRanges->start > plusRanges->start)) {
 525             SWAPval(Range *, &origRanges, &plusRanges);
 526             SWAPval(int, &nOrigRanges, &nPlusRanges);
 527             isOld = !isOld;
 528         }
 529
 530         origSet->n_ranges++;            /* we're using a new result range */
 531
 532         *newRanges = *origRanges++;
 533         nOrigRanges--;
 534         if (!isOld)
 535             RangesetRefreshRange(origSet, newRanges->start, newRanges->end);
 536
 537         /* now we must cycle over plusRanges, merging in the overlapped ranges */
 538         while (nPlusRanges > 0 && newRanges->end >= plusRanges->start) {
 539             do {
 540                 if (newRanges->end < plusRanges->end) {
 541                     if (isOld)
 542                         RangesetRefreshRange(origSet, newRanges->end, plusRanges->end);
 543                     newRanges->end = plusRanges->end;
 544                 }
 545                 plusRanges++;
 546                 nPlusRanges--;
 547             } while (nPlusRanges > 0 && newRanges->end >= plusRanges->start);
 548
 549             /* by now, newRanges->end may have extended to overlap more ranges in origRanges,
 550                so swap and start again */
 551             SWAPval(Range *, &origRanges, &plusRanges);
 552             SWAPval(int, &nOrigRanges, &nPlusRanges);
 553             isOld = !isOld;
 554         }
 555
 556         /* OK: now *newRanges holds the result of merging all the first ranges from
 557            origRanges and plusRanges - now we have a break in contiguity, so move on to the
 558            next newRanges in the result */
 559         newRanges++;
 560     }
 561
 562     /* finally, forget the old rangeset values, and reallocate the new ones */
 563     RangesFree(oldRanges);
 564     origSet->ranges = RangesRealloc(origSet->ranges, origSet->n_ranges);
 565
 566     return origSet->n_ranges;
 567 }
 568
 569
 570 /* -------------------------------------------------------------------------- */
 571
 572 /*
 573 ** Subtract the ranges of minusSet from rangeset origSet.
 574 */
 575
 576 int RangesetRemove(Rangeset *origSet, Rangeset *minusSet)
 577 {
 578     Range *origRanges, *minusRanges, *newRanges, *oldRanges;
 579     int nOrigRanges, nMinusRanges;
 580
 581     origRanges = origSet->ranges;
 582     nOrigRanges = origSet->n_ranges;
 583
 584     minusRanges = minusSet->ranges;
 585     nMinusRanges = minusSet->n_ranges;
 586
 587     if (nOrigRanges == 0 || nMinusRanges == 0)
 588         return 0;               /* no ranges in origSet or minusSet - nothing to do */
 589
 590     /* we must provide more space: each range in minusSet might split a range in origSet */
 591     newRanges = RangesNew(origSet->n_ranges + minusSet->n_ranges);
 592
 593     oldRanges = origRanges;
 594     origSet->ranges = newRanges;
 595     origSet->n_ranges = 0;
 596
 597     /* consider each range in origRanges - we do not change any of minusRanges's data, but we
 598        may change origRanges's - it will be discarded at the end */
 599
 600     while (nOrigRanges > 0) {
 601         do {
 602             /* skip all minusRanges ranges strictly in front of *origRanges */
 603             while (nMinusRanges > 0 && minusRanges->end <= origRanges->start) {
 604                 minusRanges++;          /* *minusRanges in front of *origRanges: move onto next *minusRanges */
 605                 nMinusRanges--;
 606             }
 607
 608             if (nMinusRanges > 0) {
 609                 /* keep all origRanges ranges strictly in front of *minusRanges */
 610                 while (nOrigRanges > 0 && origRanges->end <= minusRanges->start) {
 611                     *newRanges++ = *origRanges++;   /* *minusRanges beyond *origRanges: save *origRanges in *newRanges */
 612                     nOrigRanges--;
 613                     origSet->n_ranges++;
 614                 }
 615             }
 616             else {
 617                 /* no more minusRanges ranges to remove - save the rest of origRanges */
 618                 while (nOrigRanges > 0) {
 619                     *newRanges++ = *origRanges++;
 620                     nOrigRanges--;
 621                     origSet->n_ranges++;
 622               }
 623             }
 624         } while (nMinusRanges > 0 && minusRanges->end <= origRanges->start); /* any more non-overlaps */
 625
 626         /* when we get here either we're done, or we have overlap */
 627         if (nOrigRanges > 0) {
 628             if (minusRanges->start <= origRanges->start) {
 629                 /* origRanges->start inside *minusRanges */
 630                 if (minusRanges->end < origRanges->end) {
 631                     RangesetRefreshRange(origSet, origRanges->start, minusRanges->end);
 632                     origRanges->start = minusRanges->end;  /* cut off front of original *origRanges */
 633                     minusRanges++;                  /* dealt with this *minusRanges: move on */
 634                     nMinusRanges--;
 635                 }
 636                 else {
 637                     /* all *origRanges inside *minusRanges */
 638                     RangesetRefreshRange(origSet, origRanges->start, origRanges->end);
 639                     origRanges++;                       /* all of *origRanges can be skipped */
 640                     nOrigRanges--;
 641                 }
 642             }
 643             else {
 644                 /* minusRanges->start inside *origRanges: save front, adjust or skip rest */
 645                 newRanges->start = origRanges->start;   /* save front of *origRanges in *newRanges */
 646                 newRanges->end = minusRanges->start;
 647                 newRanges++;
 648                 origSet->n_ranges++;
 649
 650                 if (minusRanges->end < origRanges->end) {
 651                     /* all *minusRanges inside *origRanges */
 652                     RangesetRefreshRange(origSet, minusRanges->start, minusRanges->end);
 653                     origRanges->start = minusRanges->end; /* cut front of *origRanges upto end *minusRanges */
 654                     minusRanges++;                 /* dealt with this *minusRanges: move on */
 655                     nMinusRanges--;
 656                 }
 657                 else {
 658                     /* minusRanges->end beyond *origRanges */
 659                     RangesetRefreshRange(origSet, minusRanges->start, origRanges->end);
 660                     origRanges++;                       /* skip rest of *origRanges */
 661                     nOrigRanges--;
 662                 }
 663             }
 664         }
 665     }
 666
 667     /* finally, forget the old rangeset values, and reallocate the new ones */
 668     RangesFree(oldRanges);
 669     origSet->ranges = RangesRealloc(origSet->ranges, origSet->n_ranges);
 670
 671     return origSet->n_ranges;
 672 }
 673
 674
 675 /* -------------------------------------------------------------------------- */
 676
 677 /*
 678 ** Get number of ranges in rangeset.
 679 */
 680
 681 int RangesetGetNRanges(Rangeset *rangeset)
 682 {
 683     return rangeset ? rangeset->n_ranges : 0;
 684 }
 685
 686
 687 /*
 688 ** Get information about rangeset.
 689 */
 690 void RangesetGetInfo(Rangeset *rangeset, int *defined, unsigned char *label,
 691         int *count, char **color, char **mode)
 692 {
 693     if (rangeset == NULL) {
 694         *defined = False;
 695         *label = 0;
 696         *count = 0;
 697         *color = "";
 698         *mode = "";
 699     }
 700     else {
 701         *defined = True;
 702         *label = rangeset->label;
 703         *count = rangeset->n_ranges;
 704         *color = rangeset->color_name ? rangeset->color_name : "";
 705         *mode = rangeset->update_name;
 706     }
 707 }
 708
 709 /* -------------------------------------------------------------------------- */
 710
 711 /*
 712 ** Set maxpos for rangeset rangeset.
 713 */
 714
 715 void RangesetSetMaxpos(Rangeset *rangeset, int maxpos)
 716 {
 717     if (rangeset)
 718         rangeset->maxpos = maxpos;
 719 }
 720
 721 /* -------------------------------------------------------------------------- */
 722
 723 static Rangeset *rangesetFixMaxpos(Rangeset *rangeset, int ins, int del)
 724 {
 725     rangeset->maxpos += ins - del;
 726     return rangeset;
 727 }
 728
 729 /* -------------------------------------------------------------------------- */
 730
 731 /*
 732 ** Allocate and initialise, or empty and free a ranges set table.
 733 */
 734
 735 RangesetTable *RangesetTableAlloc(textBuffer *buffer)
 736 {
 737     int i;
 738     RangesetTable *table = (RangesetTable *)XtMalloc(sizeof (RangesetTable));
 739
 740     if (!table)
 741         return table;
 742
 743     table->buf = buffer;
 744
 745     for (i = 0; i < N_RANGESETS; i++) {
 746         RangesetInit(&table->set[i], rangeset_labels[i], buffer);
 747         table->order[i] = (unsigned char)i;
 748         table->active[i] = 0;
 749         table->depth[i] = (unsigned char)i;
 750     }
 751
 752     table->n_set = 0;
 753     return table;
 754 }
 755
 756 RangesetTable *RangesetTableFree(RangesetTable *table)
 757 {
 758     int i;
 759
 760     for (i = 0; i < N_RANGESETS; i++)
 761         RangesetEmpty(&table->set[i]);
 762     if (table)
 763         XtFree((char *)table);
 764     return (RangesetTable *)0;
 765 }
 766
 767 /*
 768 ** Find a range set given its label in the table.
 769 */
 770
 771 int RangesetFindIndex(RangesetTable *table, unsigned char label, int must_be_active)
 772 {
 773     int i;
 774     unsigned char *p_label;
 775
 776     if(label == 0) {
 777        return -1;
 778     }
 779
 780     if (table != NULL) {
 781         p_label = (unsigned char*)strchr((char*)rangeset_labels, label);
 782         if (p_label) {
 783             i = p_label - rangeset_labels;
 784             if (!must_be_active || table->active[i])
 785                 return i;
 786         }
 787     }
 788
 789     return -1;
 790 }
 791
 792
 793 /*
 794 ** Assign the range set table list.
 795 */
 796
 797 static void RangesetTableListSet(RangesetTable *table)
 798 {
 799     int i;
 800
 801     for (i = 0; i < table->n_set; i++)
 802         table->list[i] = rangeset_labels[(int)table->order[i]];
 803     table->list[table->n_set] = '\0';
 804 }
 805
 806 /*
 807 ** Return true if label is a valid identifier for a range set.
 808 */
 809
 810 int RangesetLabelOK(int label)
 811 {
 812     return strchr((char*)rangeset_labels, (char)label) != NULL;
 813 }
 814
 815 /*
 816 ** Helper routines for managing the order and depth tables.
 817 */
 818
 819 static int activateRangeset(RangesetTable *table, int active)
 820 {
 821     int depth, i, j;
 822
 823     if (table->active[active])
 824         return 0;                       /* already active */
 825
 826     depth = table->depth[active];
 827
 828     /* we want to make the "active" set the most recent (lowest depth value):
 829        shuffle table->order[0..depth-1] to table->order[1..depth]
 830        readjust the entries in table->depth[] accordingly */
 831     for (i = depth; i > 0; i--) {
 832         j = table->order[i] = table->order[i - 1];
 833         table->depth[j] = i;
 834     }
 835     /* insert the new one: first in order, of depth 0 */
 836     table->order[0] = active;
 837     table->depth[active] = 0;
 838
 839     /* and finally... */
 840     table->active[active] = 1;
 841     table->n_set++;
 842
 843     RangesetTableListSet(table);
 844
 845     return 1;
 846 }
 847
 848 static int deactivateRangeset(RangesetTable *table, int active)
 849 {
 850     int depth, n, i, j;
 851
 852     if (!table->active[active])
 853         return 0;                       /* already inactive */
 854
 855     /* we want to start by swapping the deepest entry in order with active
 856        shuffle table->order[depth+1..n_set-1] to table->order[depth..n_set-2]
 857        readjust the entries in table->depth[] accordingly */
 858     depth = table->depth[active];
 859     n = table->n_set - 1;
 860
 861     for (i = depth; i < n; i++) {
 862         j = table->order[i] = table->order[i + 1];
 863         table->depth[j] = i;
 864     }
 865     /* reinsert the old one: at max (active) depth */
 866     table->order[n] = active;
 867     table->depth[active] = n;
 868
 869     /* and finally... */
 870     table->active[active] = 0;
 871     table->n_set--;
 872
 873     RangesetTableListSet(table);
 874
 875     return 1;
 876 }
 877
 878
 879 /*
 880 ** Return the number of rangesets that are inactive
 881 */
 882
 883 int nRangesetsAvailable(RangesetTable *table)
 884 {
 885     return(N_RANGESETS - table->n_set);
 886 }
 887
 888
 889 /*
 890 ** Create a new empty rangeset
 891 */
 892
 893 int RangesetCreate(RangesetTable *table)
 894 {
 895     unsigned char label;
 896     int setIndex;
 897
 898     size_t firstAvailableIndex = strspn((char*)rangeset_labels, (char*)table->list);
 899
 900     if(firstAvailableIndex >= sizeof(rangeset_labels))
 901         return '\0';
 902
 903     label = rangeset_labels[firstAvailableIndex];
 904
 905     setIndex = RangesetFindIndex(table, label, 0);
 906
 907     if (setIndex < 0)
 908         return '\0';
 909
 910     if (table->active[setIndex])
 911         return label;
 912
 913     if (activateRangeset(table, setIndex))
 914         RangesetInit(&table->set[setIndex],
 915              rangeset_labels[setIndex], table->buf);
 916
 917     return label;
 918 }
 919
 920 /*
 921 ** Forget the rangeset identified by label - clears it, renders it inactive.
 922 */
 923
 924 Rangeset *RangesetForget(RangesetTable *table, int label)
 925 {
 926     int set_ind = RangesetFindIndex(table, (unsigned char)label, 1);
 927
 928     if (set_ind < 0)
 929         return (Rangeset *)0;
 930
 931     if (deactivateRangeset(table, set_ind))
 932         RangesetEmpty(&table->set[set_ind]);
 933
 934     return &table->set[set_ind];
 935 }
 936
 937
 938
 939 /*
 940 ** Fetch the rangeset identified by label - initialise it if not active and
 941 ** make_active is true, and make it the most visible.
 942 */
 943
 944 Rangeset *RangesetFetch(RangesetTable *table, int label)
 945 {
 946     int rangesetIndex = RangesetFindIndex(table, (unsigned char)label, 0);
 947
 948     if (rangesetIndex < 0)
 949         return (Rangeset *)NULL;
 950
 951     if (table->active[rangesetIndex])
 952         return &table->set[rangesetIndex];
 953     else
 954         return (Rangeset *)NULL;
 955 }
 956
 957
 958 unsigned char *RangesetGetList(RangesetTable *table)
 959 {
 960     return table ? table->list : (unsigned char *)"";
 961 }
 962
 963
 964 /* -------------------------------------------------------------------------- */
 965
 966 void RangesetTableUpdatePos(RangesetTable *table, int pos, int ins, int del)
 967 {
 968     int i;
 969     Rangeset *p;
 970
 971     if (!table || (ins == 0 && del == 0))
 972         return;
 973
 974     for (i = 0; i < table->n_set; i++) {
 975         p = &table->set[(int)table->order[i]];
 976         p->update_fn(p, pos, ins, del);
 977     }
 978 }
 979
 980 void RangesetBufModifiedCB(int pos, int nInserted, int nDeleted, int nRestyled,
 981         char *deletedText, void *cbArg)
 982 {
 983     textBuffer *buf = (textBuffer *)cbArg;
 984
 985     RangesetTableUpdatePos(buf->rangesetTable, pos,
 986                            nInserted, nDeleted);
 987 }
 988
 989 /* -------------------------------------------------------------------------- */
 990
 991 /*
 992 ** Find the index of the first range in depth order which includes the position.
 993 ** Returns the index of the rangeset in the rangeset table + 1 if an including
 994 ** rangeset was found, 0 otherwise. If needs_color is true, "colorless" ranges
 995 ** will be skipped.
 996 */
 997
 998 int RangesetIndex1ofPos(RangesetTable *table, int pos, int needs_color)
 999 {
1000     int i;
1001     Rangeset *rangeset;
1002
1003     if (!table)
1004         return 0;
1005
1006     for (i = 0; i < table->n_set; i++) {
1007         rangeset = &table->set[(int)table->order[i]];
1008         if (RangesetCheckRangeOfPos(rangeset, pos) >= 0) {
1009             if (needs_color && rangeset->color_set >= 0 && rangeset->color_name)
1010                 return table->order[i] + 1;
1011         }
1012     }
1013     return 0;
1014 }
1015
1016 /* -------------------------------------------------------------------------- */
1017
1018 /*
1019 ** Assign a color name to a rangeset via the rangeset table.
1020 */
1021
1022 int RangesetAssignColorName(Rangeset *rangeset, char *color_name)
1023 {
1024     char *cp;
1025
1026     if (color_name && color_name[0] == '\0')
1027         color_name = (char *)0;                         /* "" invalid */
1028
1029     /* store new color name value */
1030     if (color_name) {
1031         cp = XtMalloc(strlen(color_name) + 1);
1032         strcpy(cp, color_name);
1033     }
1034     else
1035         cp = color_name;
1036
1037     /* free old color name value */
1038     if (rangeset->color_name)
1039         XtFree(rangeset->color_name);
1040
1041     rangeset->color_name = cp;
1042     rangeset->color_set = 0;
1043
1044     RangesetRefreshAllRanges(rangeset);
1045     return 1;
1046 }
1047
1048 /*
1049 ** Assign a color pixel value to a rangeset via the rangeset table. If ok is
1050 ** false, the color_set flag is set to an invalid (negative) value.
1051 */
1052
1053 int RangesetAssignColorPixel(Rangeset *rangeset, Pixel color, int ok)
1054 {
1055     rangeset->color_set = ok ? 1 : -1;
1056     rangeset->color = color;
1057     return 1;
1058 }
1059
1060
1061 /*
1062 ** Return the color name, if any.
1063 */
1064
1065 char *RangesetGetColorName(Rangeset *rangeset)
1066 {
1067     return rangeset->color_name;
1068 }
1069
1070 /*
1071 ** Return the color validity, if any, and the value in *color.
1072 */
1073
1074 int RangesetGetColorValid(Rangeset *rangeset, Pixel *color)
1075 {
1076     *color = rangeset->color;
1077     return rangeset->color_set;
1078 }
1079
1080 /*
1081 ** Return the color name, if any.
1082 */
1083
1084 char *RangesetTableGetColorName(RangesetTable *table, int index)
1085 {
1086     Rangeset *rangeset = &table->set[index];
1087     return rangeset->color_name;
1088 }
1089
1090 /*
1091 ** Return the color color validity, if any, and the value in *color.
1092 */
1093
1094 int RangesetTableGetColorValid(RangesetTable *table, int index, Pixel *color)
1095 {
1096     Rangeset *rangeset = &table->set[index];
1097     *color = rangeset->color;
1098     return rangeset->color_set;
1099 }
1100
1101 /*
1102 ** Assign a color pixel value to a rangeset via the rangeset table. If ok is
1103 ** false, the color_set flag is set to an invalid (negative) value.
1104 */
1105
1106 int RangesetTableAssignColorPixel(RangesetTable *table, int index, Pixel color,
1107         int ok)
1108 {
1109     Rangeset *rangeset = &table->set[index];
1110     rangeset->color_set = ok ? 1 : -1;
1111     rangeset->color = color;
1112     return 1;
1113 }
1114
1115 /* -------------------------------------------------------------------------- */
1116
1117 #define is_start(i)     !((i) & 1)      /* true if i is even */
1118 #define is_end(i)       ((i) & 1)       /* true if i is odd */
1119
1120 /*
1121 ** Find the index of the first entry in the range set's ranges table (viewed as
1122 ** an int array) whose value is equal to or greater than pos. As a side effect,
1123 ** update the lasi_index value of the range set. Return's the index value. This
1124 ** will be twice p->n_ranges if pos is beyond the end.
1125 */
1126
1127 static int rangesetWeightedAtOrBefore(Rangeset *rangeset, int pos)
1128 {
1129     int i, last, n, *rangeTable = (int *)rangeset->ranges;
1130
1131     n = rangeset->n_ranges;
1132     if (n == 0)
1133         return 0;
1134
1135     last = rangeset->last_index;
1136
1137     if (last >= n || last < 0)
1138         last = 0;
1139
1140     n *= 2;
1141     last *= 2;
1142
1143     if (pos >= rangeTable[last])                /* ranges[last_index].start */
1144         i = weighted_at_or_before(rangeTable, last, n, pos); /* search end only */
1145     else
1146         i = weighted_at_or_before(rangeTable, 0, last, pos); /* search front only */
1147
1148     rangeset->last_index = i / 2;
1149
1150     return i;
1151 }
1152
1153 /*
1154 ** Adjusts values in tab[] by an amount delta, perhaps moving them meanwhile.
1155 */
1156
1157 static int rangesetShuffleToFrom(int *rangeTable, int to, int from, int n, int delta)
1158 {
1159     int end, diff = from - to;
1160
1161     if (n <= 0)
1162         return 0;
1163
1164     if (delta != 0) {
1165         if (diff > 0) {                 /* shuffle entries down */
1166             for (end = to + n; to < end; to++)
1167                 rangeTable[to] = rangeTable[to + diff] + delta;
1168         }
1169         else if (diff < 0) {            /* shuffle entries up */
1170             for (end = to, to += n; --to >= end;)
1171                 rangeTable[to] = rangeTable[to + diff] + delta;
1172         }
1173         else {                          /* diff == 0: just run through */
1174             for (end = n; end--;)
1175                 rangeTable[to++] += delta;
1176         }
1177     }
1178     else {
1179         if (diff > 0) {                 /* shuffle entries down */
1180             for (end = to + n; to < end; to++)
1181                 rangeTable[to] = rangeTable[to + diff];
1182         }
1183         else if (diff < 0) {            /* shuffle entries up */
1184             for (end = to, to += n; --to >= end;)
1185                 rangeTable[to] = rangeTable[to + diff];
1186         }
1187         /* else diff == 0: nothing to do */
1188     }
1189
1190     return n;
1191 }
1192
1193 /*
1194 ** Functions to adjust a rangeset to include new text or remove old.
1195 ** *** NOTE: No redisplay: that's outside the responsability of these routines.
1196 */
1197
1198 /* "Insert/Delete": if the start point is in or at the end of a range
1199 ** (start < pos && pos <= end), any text inserted will extend that range.
1200 ** Insertions appear to occur before deletions. This will never add new ranges.
1201 */
1202
1203 static Rangeset *rangesetInsDelMaintain(Rangeset *rangeset, int pos, int ins, int del)
1204 {
1205     int i, j, n, *rangeTable = (int *)rangeset->ranges;
1206     int end_del, movement;
1207
1208     n = 2 * rangeset->n_ranges;
1209
1210     i = rangesetWeightedAtOrBefore(rangeset, pos);
1211
1212     if (i == n)
1213         return rangesetFixMaxpos(rangeset, ins, del);   /* all beyond the end */
1214
1215     end_del = pos + del;
1216     movement = ins - del;
1217
1218     /* the idea now is to determine the first range not concerned with the
1219        movement: its index will be j. For indices j to n-1, we will adjust
1220        position by movement only. (They may need shuffling up or down, depending
1221        on whether ranges have been deleted or created by the change.) */
1222     j = i;
1223     while (j < n && rangeTable[j] <= end_del)   /* skip j to first ind beyond changes */
1224         j++;
1225
1226     /* if j moved forward, we have deleted over rangeTable[i] - reduce it accordingly,
1227        accounting for inserts. */
1228     if (j > i)
1229         rangeTable[i] = pos + ins;
1230
1231     /* If i and j both index starts or ends, just copy all the rangeTable[] values down
1232        by j - i spaces, adjusting on the way. Otherwise, move beyond rangeTable[i]
1233        before doing this. */
1234
1235     if (is_start(i) != is_start(j))
1236         i++;
1237
1238     rangesetShuffleToFrom(rangeTable, i, j, n - j, movement);
1239
1240     n -= j - i;
1241     rangeset->n_ranges = n / 2;
1242     rangeset->ranges = RangesRealloc(rangeset->ranges, rangeset->n_ranges);
1243
1244     /* final adjustments */
1245     return rangesetFixMaxpos(rangeset, ins, del);
1246 }
1247
1248 /* "Inclusive": if the start point is in, at the start of, or at the end of a
1249 ** range (start <= pos && pos <= end), any text inserted will extend that range.
1250 ** Insertions appear to occur before deletions. This will never add new ranges.
1251 ** (Almost identical to rangesetInsDelMaintain().)
1252 */
1253
1254 static Rangeset *rangesetInclMaintain(Rangeset *rangeset, int pos, int ins, int del)
1255 {
1256     int i, j, n, *rangeTable = (int *)rangeset->ranges;
1257     int end_del, movement;
1258
1259     n = 2 * rangeset->n_ranges;
1260
1261     i = rangesetWeightedAtOrBefore(rangeset, pos);
1262
1263     if (i == n)
1264         return rangesetFixMaxpos(rangeset, ins, del);   /* all beyond the end */
1265
1266     /* if the insert occurs at the start of a range, the following lines will
1267        extend the range, leaving the start of the range at pos. */
1268
1269     if (is_start(i) && rangeTable[i] == pos && ins > 0)
1270         i++;
1271
1272     end_del = pos + del;
1273     movement = ins - del;
1274
1275     /* the idea now is to determine the first range not concerned with the
1276        movement: its index will be j. For indices j to n-1, we will adjust
1277        position by movement only. (They may need shuffling up or down, depending
1278        on whether ranges have been deleted or created by the change.) */
1279     j = i;
1280     while (j < n && rangeTable[j] <= end_del)   /* skip j to first ind beyond changes */
1281         j++;
1282
1283     /* if j moved forward, we have deleted over rangeTable[i] - reduce it accordingly,
1284        accounting for inserts. */
1285     if (j > i)
1286         rangeTable[i] = pos + ins;
1287
1288     /* If i and j both index starts or ends, just copy all the rangeTable[] values down
1289        by j - i spaces, adjusting on the way. Otherwise, move beyond rangeTable[i]
1290        before doing this. */
1291
1292     if (is_start(i) != is_start(j))
1293         i++;
1294
1295     rangesetShuffleToFrom(rangeTable, i, j, n - j, movement);
1296
1297     n -= j - i;
1298     rangeset->n_ranges = n / 2;
1299     rangeset->ranges = RangesRealloc(rangeset->ranges, rangeset->n_ranges);
1300
1301     /* final adjustments */
1302     return rangesetFixMaxpos(rangeset, ins, del);
1303 }
1304
1305 /* "Delete/Insert": if the start point is in a range (start < pos &&
1306 ** pos <= end), and the end of deletion is also in a range
1307 ** (start <= pos + del && pos + del < end) any text inserted will extend that
1308 ** range. Deletions appear to occur before insertions. This will never add new
1309 ** ranges.
1310 */
1311
1312 static Rangeset *rangesetDelInsMaintain(Rangeset *rangeset, int pos, int ins, int del)
1313 {
1314     int i, j, n, *rangeTable = (int *)rangeset->ranges;
1315     int end_del, movement;
1316
1317     n = 2 * rangeset->n_ranges;
1318
1319     i = rangesetWeightedAtOrBefore(rangeset, pos);
1320
1321     if (i == n)
1322         return rangesetFixMaxpos(rangeset, ins, del);   /* all beyond the end */
1323
1324     end_del = pos + del;
1325     movement = ins - del;
1326
1327     /* the idea now is to determine the first range not concerned with the
1328        movement: its index will be j. For indices j to n-1, we will adjust
1329        position by movement only. (They may need shuffling up or down, depending
1330        on whether ranges have been deleted or created by the change.) */
1331     j = i;
1332     while (j < n && rangeTable[j] <= end_del)   /* skip j to first ind beyond changes */
1333         j++;
1334
1335     /* if j moved forward, we have deleted over rangeTable[i] - reduce it accordingly,
1336        accounting for inserts. (Note: if rangeTable[j] is an end position, inserted
1337        text will belong to the range that rangeTable[j] closes; otherwise inserted
1338        text does not belong to a range.) */
1339     if (j > i)
1340         rangeTable[i] = (is_end(j)) ? pos + ins : pos;
1341
1342     /* If i and j both index starts or ends, just copy all the rangeTable[] values down
1343        by j - i spaces, adjusting on the way. Otherwise, move beyond rangeTable[i]
1344        before doing this. */
1345
1346     if (is_start(i) != is_start(j))
1347         i++;
1348
1349     rangesetShuffleToFrom(rangeTable, i, j, n - j, movement);
1350
1351     n -= j - i;
1352     rangeset->n_ranges = n / 2;
1353     rangeset->ranges = RangesRealloc(rangeset->ranges, rangeset->n_ranges);
1354
1355     /* final adjustments */
1356     return rangesetFixMaxpos(rangeset, ins, del);
1357 }
1358
1359 /* "Exclusive": if the start point is in, but not at the end of, a range
1360 ** (start < pos && pos < end), and the end of deletion is also in a range
1361 ** (start <= pos + del && pos + del < end) any text inserted will extend that
1362 ** range. Deletions appear to occur before insertions. This will never add new
1363 ** ranges. (Almost identical to rangesetDelInsMaintain().)
1364 */
1365
1366 static Rangeset *rangesetExclMaintain(Rangeset *rangeset, int pos, int ins, int del)
1367 {
1368     int i, j, n, *rangeTable = (int *)rangeset->ranges;
1369     int end_del, movement;
1370
1371     n = 2 * rangeset->n_ranges;
1372
1373     i = rangesetWeightedAtOrBefore(rangeset, pos);
1374
1375     if (i == n)
1376         return rangesetFixMaxpos(rangeset, ins, del);   /* all beyond the end */
1377
1378     /* if the insert occurs at the end of a range, the following lines will
1379        skip the range, leaving the end of the range at pos. */
1380
1381     if (is_end(i) && rangeTable[i] == pos && ins > 0)
1382         i++;
1383
1384     end_del = pos + del;
1385     movement = ins - del;
1386
1387     /* the idea now is to determine the first range not concerned with the
1388        movement: its index will be j. For indices j to n-1, we will adjust
1389        position by movement only. (They may need shuffling up or down, depending
1390        on whether ranges have been deleted or created by the change.) */
1391     j = i;
1392     while (j < n && rangeTable[j] <= end_del)   /* skip j to first ind beyond changes */
1393         j++;
1394
1395     /* if j moved forward, we have deleted over rangeTable[i] - reduce it accordingly,
1396        accounting for inserts. (Note: if rangeTable[j] is an end position, inserted
1397        text will belong to the range that rangeTable[j] closes; otherwise inserted
1398        text does not belong to a range.) */
1399     if (j > i)
1400         rangeTable[i] = (is_end(j)) ? pos + ins : pos;
1401
1402     /* If i and j both index starts or ends, just copy all the rangeTable[] values down
1403        by j - i spaces, adjusting on the way. Otherwise, move beyond rangeTable[i]
1404        before doing this. */
1405
1406     if (is_start(i) != is_start(j))
1407         i++;
1408
1409     rangesetShuffleToFrom(rangeTable, i, j, n - j, movement);
1410
1411     n -= j - i;
1412     rangeset->n_ranges = n / 2;
1413     rangeset->ranges = RangesRealloc(rangeset->ranges, rangeset->n_ranges);
1414
1415     /* final adjustments */
1416     return rangesetFixMaxpos(rangeset, ins, del);
1417 }
1418
1419 /* "Break": if the modification point pos is strictly inside a range, that range
1420 ** may be broken in two if the deletion point pos+del does not extend beyond the
1421 ** end. Inserted text is never included in the range.
1422 */
1423
1424 static Rangeset *rangesetBreakMaintain(Rangeset *rangeset, int pos, int ins, int del)
1425 {
1426     int i, j, n, *rangeTable = (int *)rangeset->ranges;
1427     int end_del, movement, need_gap;
1428
1429     n = 2 * rangeset->n_ranges;
1430
1431     i = rangesetWeightedAtOrBefore(rangeset, pos);
1432
1433     if (i == n)
1434         return rangesetFixMaxpos(rangeset, ins, del);   /* all beyond the end */
1435
1436     /* if the insert occurs at the end of a range, the following lines will
1437        skip the range, leaving the end of the range at pos. */
1438
1439     if (is_end(i) && rangeTable[i] == pos && ins > 0)
1440         i++;
1441
1442     end_del = pos + del;
1443     movement = ins - del;
1444
1445     /* the idea now is to determine the first range not concerned with the
1446        movement: its index will be j. For indices j to n-1, we will adjust
1447        position by movement only. (They may need shuffling up or down, depending
1448        on whether ranges have been deleted or created by the change.) */
1449     j = i;
1450     while (j < n && rangeTable[j] <= end_del)   /* skip j to first ind beyond changes */
1451         j++;
1452
1453     if (j > i)
1454         rangeTable[i] = pos;
1455
1456     /* do we need to insert a gap? yes if pos is in a range and ins > 0 */
1457
1458     /* The logic for the next statement: if i and j are both range ends, range
1459        boundaries indicated by index values between i and j (if any) have been
1460        "skipped". This means that rangeTable[i-1],rangeTable[j] is the current range. We will
1461        be inserting in that range, splitting it. */
1462
1463     need_gap = (is_end(i) && is_end(j) && ins > 0);
1464
1465     /* if we've got start-end or end-start, skip rangeTable[i] */
1466     if (is_start(i) != is_start(j)) {   /* one is start, other is end */
1467         if (is_start(i)) {
1468             if (rangeTable[i] == pos)
1469                 rangeTable[i] = pos + ins;      /* move the range start */
1470         }
1471         i++;                            /* skip to next index */
1472     }
1473
1474     /* values rangeTable[j] to rangeTable[n-1] must be adjusted by movement and placed in
1475        position. */
1476
1477     if (need_gap)
1478         i += 2;                         /* make space for the break */
1479
1480     /* adjust other position values: shuffle them up or down if necessary */
1481     rangesetShuffleToFrom(rangeTable, i, j, n - j, movement);
1482
1483     if (need_gap) {                     /* add the gap informations */
1484         rangeTable[i - 2] = pos;
1485         rangeTable[i - 1] = pos + ins;
1486     }
1487
1488     n -= j - i;
1489     rangeset->n_ranges = n / 2;
1490     rangeset->ranges = RangesRealloc(rangeset->ranges, rangeset->n_ranges);
1491
1492     /* final adjustments */
1493     return rangesetFixMaxpos(rangeset, ins, del);
1494 }
1495
1496 /* -------------------------------------------------------------------------- */
1497
1498 /*
1499 ** Invert the rangeset (replace it with its complement in the range 0-maxpos).
1500 ** Returns the number of ranges if successful, -1 otherwise. Never adds more
1501 ** than one range.
1502 */
1503
1504 int RangesetInverse(Rangeset *rangeset)
1505 {
1506     int *rangeTable;
1507     int n, has_zero, has_end;
1508
1509     if (!rangeset)
1510         return -1;
1511
1512     rangeTable = (int *)rangeset->ranges;
1513
1514     if (rangeset->n_ranges == 0) {
1515         rangeTable[0] = 0;
1516         rangeTable[1] = rangeset->maxpos;
1517         n = 2;
1518     }
1519     else {
1520         n = rangeset->n_ranges * 2;
1521
1522         /* find out what we have */
1523         has_zero = (rangeTable[0] == 0);
1524         has_end = (rangeTable[n - 1] == rangeset->maxpos);
1525
1526         /* fill the entry "beyond the end" with the buffer's length */
1527         rangeTable[n + 1] = rangeTable[n] = rangeset->maxpos;
1528
1529         if (has_zero) {
1530           /* shuffle down by one */
1531           rangesetShuffleToFrom(rangeTable, 0, 1, n, 0);
1532           n -= 1;
1533         }
1534         else {
1535           /* shuffle up by one */
1536           rangesetShuffleToFrom(rangeTable, 1, 0, n, 0);
1537           rangeTable[0] = 0;
1538           n += 1;
1539         }
1540         if (has_end)
1541           n -= 1;
1542         else
1543           n += 1;
1544     }
1545
1546     rangeset->n_ranges = n / 2;
1547     rangeset->ranges = RangesRealloc((Range *)rangeTable, rangeset->n_ranges);
1548
1549     RangesetRefreshRange(rangeset, 0, rangeset->maxpos);
1550     return rangeset->n_ranges;
1551 }
1552
1553 /* -------------------------------------------------------------------------- */
1554
1555 /*
1556 ** Add the range indicated by the positions start and end. Returns the
1557 ** new number of ranges in the set.
1558 */
1559
1560 int RangesetAddBetween(Rangeset *rangeset, int start, int end)
1561 {
1562     int i, j, n, *rangeTable = (int *)rangeset->ranges;
1563
1564     if (start > end) {
1565         i = start;        /* quietly sort the positions */
1566         start = end;
1567         end = i;
1568     }
1569     else if (start == end) {
1570         return rangeset->n_ranges; /* no-op - empty range == no range */
1571     }
1572
1573     n = 2 * rangeset->n_ranges;
1574
1575     if (n == 0) {                       /* make sure we have space */
1576         rangeset->ranges = RangesNew(1);
1577         rangeTable = (int *)rangeset->ranges;
1578         i = 0;
1579     }
1580     else
1581         i = rangesetWeightedAtOrBefore(rangeset, start);
1582
1583     if (i == n) {                       /* beyond last range: just add it */
1584         rangeTable[n] = start;
1585         rangeTable[n + 1] = end;
1586         rangeset->n_ranges++;
1587         rangeset->ranges = RangesRealloc(rangeset->ranges, rangeset->n_ranges);
1588
1589         RangesetRefreshRange(rangeset, start, end);
1590         return rangeset->n_ranges;
1591     }
1592
1593     j = i;
1594     while (j < n && rangeTable[j] <= end)       /* skip j to first ind beyond changes */
1595         j++;
1596
1597     if (i == j) {
1598         if (is_start(i)) {
1599             /* is_start(i): need to make a gap in range rangeTable[i-1], rangeTable[i] */
1600             rangesetShuffleToFrom(rangeTable, i + 2, i, n - i, 0);      /* shuffle up */
1601             rangeTable[i] = start;              /* load up new range's limits */
1602             rangeTable[i + 1] = end;
1603             rangeset->n_ranges++;               /* we've just created a new range */
1604             rangeset->ranges = RangesRealloc(rangeset->ranges, rangeset->n_ranges);
1605         }
1606         else {
1607             return rangeset->n_ranges;          /* no change */
1608         }
1609     }
1610     else {
1611         /* we'll be shuffling down */
1612         if (is_start(i))
1613             rangeTable[i++] = start;
1614         if (is_start(j))
1615              rangeTable[--j] = end;
1616         if (i < j)
1617             rangesetShuffleToFrom(rangeTable, i, j, n - j, 0);
1618         n -= j - i;
1619         rangeset->n_ranges = n / 2;
1620         rangeset->ranges = RangesRealloc(rangeset->ranges, rangeset->n_ranges);
1621     }
1622
1623     RangesetRefreshRange(rangeset, start, end);
1624     return rangeset->n_ranges;
1625 }
1626
1627
1628 /*
1629 ** Remove the range indicated by the positions start and end. Returns the
1630 ** new number of ranges in the set.
1631 */
1632
1633 int RangesetRemoveBetween(Rangeset *rangeset, int start, int end)
1634 {
1635     int i, j, n, *rangeTable = (int *)rangeset->ranges;
1636
1637     if (start > end) {
1638         i = start;        /* quietly sort the positions */
1639         start = end;
1640         end = i;
1641     }
1642     else if (start == end) {
1643         return rangeset->n_ranges; /* no-op - empty range == no range */
1644     }
1645
1646     n = 2 * rangeset->n_ranges;
1647
1648     i = rangesetWeightedAtOrBefore(rangeset, start);
1649
1650     if (i == n)
1651         return rangeset->n_ranges;              /* beyond last range */
1652
1653     j = i;
1654     while (j < n && rangeTable[j] <= end)       /* skip j to first ind beyond changes */
1655         j++;
1656
1657     if (i == j) {
1658         /* removal occurs in front of rangeTable[i] */
1659         if (is_start(i))
1660             return rangeset->n_ranges;          /* no change */
1661         else {
1662             /* is_end(i): need to make a gap in range rangeTable[i-1], rangeTable[i] */
1663             i--;                        /* start of current range */
1664             rangesetShuffleToFrom(rangeTable, i + 2, i, n - i, 0); /* shuffle up */
1665             rangeTable[i + 1] = start;          /* change end of current range */
1666             rangeTable[i + 2] = end;            /* change start of new range */
1667             rangeset->n_ranges++;               /* we've just created a new range */
1668             rangeset->ranges = RangesRealloc(rangeset->ranges, rangeset->n_ranges);
1669         }
1670     }
1671     else {
1672         /* removal occurs in front of rangeTable[j]: we'll be shuffling down */
1673         if (is_end(i))
1674             rangeTable[i++] = start;
1675         if (is_end(j))
1676              rangeTable[--j] = end;
1677         if (i < j)
1678             rangesetShuffleToFrom(rangeTable, i, j, n - j, 0);
1679         n -= j - i;
1680         rangeset->n_ranges = n / 2;
1681         rangeset->ranges = RangesRealloc(rangeset->ranges, rangeset->n_ranges);
1682     }
1683
1684     RangesetRefreshRange(rangeset, start, end);
1685     return rangeset->n_ranges;
1686 }
1687
1688 /* -------------------------------------------------------------------------- */
1689