source/rangeset.c

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