UNIXworkcode

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