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 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
RangesNew(int n)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
RangesRealloc(Range * ranges,int n)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
RangesFree(Range * ranges)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
RangesetRefreshRange(Rangeset * rangeset,int start,int end)191 void RangesetRefreshRange(Rangeset *rangeset, int start, int end)
192 {
193 if (rangeset->buf != NULL)
194 BufCheckDisplay(rangeset->buf, start, end);
195 }
196
rangesetRefreshAllRanges(Rangeset * rangeset)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
RangesetEmpty(Rangeset * rangeset)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
RangesetInit(Rangeset * rangeset,int label,textBuffer * buf)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
RangesetChangeModifyResponse(Rangeset * rangeset,char * name)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
at_or_before(int * table,int base,int len,int val)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
weighted_at_or_before(int * table,int base,int len,int val)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
RangesetFindRangeNo(Rangeset * rangeset,int index,int * start,int * end)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
RangesetFindRangeOfPos(Rangeset * rangeset,int pos,int incl_end)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
RangesetCheckRangeOfPos(Rangeset * rangeset,int pos)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
RangesetAdd(Rangeset * origSet,Rangeset * plusSet)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
RangesetRemove(Rangeset * origSet,Rangeset * minusSet)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
RangesetGetNRanges(Rangeset * rangeset)684 int RangesetGetNRanges(Rangeset *rangeset)
685 {
686 return rangeset ? rangeset->n_ranges : 0;
687 }
688
689
690 /*
691 ** Get information about rangeset.
692 */
RangesetGetInfo(Rangeset * rangeset,int * defined,int * label,int * count,char ** color,char ** name,char ** mode)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
rangesetFixMaxpos(Rangeset * rangeset,int ins,int del)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
RangesetTableAlloc(textBuffer * buffer)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
RangesetTableFree(RangesetTable * table)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 */
rangesetClone(Rangeset * destRangeset,Rangeset * srcRangeset)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 */
RangesetTableClone(RangesetTable * srcTable,textBuffer * destBuffer)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
RangesetFindIndex(RangesetTable * table,int label,int must_be_active)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
RangesetTableListSet(RangesetTable * table)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
RangesetLabelOK(int label)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
activateRangeset(RangesetTable * table,int active)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
deactivateRangeset(RangesetTable * table,int active)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
nRangesetsAvailable(RangesetTable * table)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
RangesetCreate(RangesetTable * table)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
RangesetForget(RangesetTable * table,int label)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
RangesetFetch(RangesetTable * table,int label)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
RangesetGetList(RangesetTable * table)1020 unsigned char *RangesetGetList(RangesetTable *table)
1021 {
1022 return table ? table->list : (unsigned char *)"";
1023 }
1024
1025
1026 /* -------------------------------------------------------------------------- */
1027
RangesetTableUpdatePos(RangesetTable * table,int pos,int ins,int del)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
RangesetBufModifiedCB(int pos,int nInserted,int nDeleted,int nRestyled,const char * deletedText,void * cbArg)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
RangesetIndex1ofPos(RangesetTable * table,int pos,int needs_color)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
RangesetAssignColorName(Rangeset * rangeset,char * color_name)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
RangesetAssignName(Rangeset * rangeset,char * name)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
RangesetAssignColorPixel(Rangeset * rangeset,Pixel color,int ok)1142 int RangesetAssignColorPixel(Rangeset *rangeset, Pixel 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
RangesetGetName(Rangeset * rangeset)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
RangesetGetColorValid(Rangeset * rangeset,Pixel * color)1163 int RangesetGetColorValid(Rangeset *rangeset, Pixel *color)
1164 {
1165 *color = rangeset->color;
1166 return rangeset->color_set;
1167 }
1168
1169 /*
1170 ** Return the color name, if any.
1171 */
1172
RangesetTableGetColorName(RangesetTable * table,int index)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
RangesetTableGetColorValid(RangesetTable * table,int index,Pixel * color)1183 int RangesetTableGetColorValid(RangesetTable *table, int index, Pixel *color)
1184 {
1185 Rangeset *rangeset = &table->set[index];
1186 *color = rangeset->color;
1187 return rangeset->color_set;
1188 }
1189
1190 /*
1191 ** Assign a color pixel value to a rangeset via the rangeset table. If ok is
1192 ** false, the color_set flag is set to an invalid (negative) value.
1193 */
1194
RangesetTableAssignColorPixel(RangesetTable * table,int index,Pixel color,int ok)1195 int RangesetTableAssignColorPixel(RangesetTable *table, int index, Pixel color,
1196 int ok)
1197 {
1198 Rangeset *rangeset = &table->set[index];
1199 rangeset->color_set = ok ? 1 : -1;
1200 rangeset->color = color;
1201 return 1;
1202 }
1203
1204 /* -------------------------------------------------------------------------- */
1205
1206 #define is_start(i) !((i) & 1) /* true if i is even */
1207 #define is_end(i) ((i) & 1) /* true if i is odd */
1208
1209 /*
1210 ** Find the index of the first entry in the range set's ranges table (viewed as
1211 ** an int array) whose value is equal to or greater than pos. As a side effect,
1212 ** update the lasi_index value of the range set. Return's the index value. This
1213 ** will be twice p->n_ranges if pos is beyond the end.
1214 */
1215
rangesetWeightedAtOrBefore(Rangeset * rangeset,int pos)1216 static int rangesetWeightedAtOrBefore(Rangeset *rangeset, int pos)
1217 {
1218 int i, last, n, *rangeTable = (int *)rangeset->ranges;
1219
1220 n = rangeset->n_ranges;
1221 if (n == 0)
1222 return 0;
1223
1224 last = rangeset->last_index;
1225
1226 if (last >= n || last < 0)
1227 last = 0;
1228
1229 n *= 2;
1230 last *= 2;
1231
1232 if (pos >= rangeTable[last]) /* ranges[last_index].start */
1233 i = weighted_at_or_before(rangeTable, last, n, pos); /* search end only */
1234 else
1235 i = weighted_at_or_before(rangeTable, 0, last, pos); /* search front only */
1236
1237 rangeset->last_index = i / 2;
1238
1239 return i;
1240 }
1241
1242 /*
1243 ** Adjusts values in tab[] by an amount delta, perhaps moving them meanwhile.
1244 */
1245
rangesetShuffleToFrom(int * rangeTable,int to,int from,int n,int delta)1246 static int rangesetShuffleToFrom(int *rangeTable, int to, int from, int n, int delta)
1247 {
1248 int end, diff = from - to;
1249
1250 if (n <= 0)
1251 return 0;
1252
1253 if (delta != 0) {
1254 if (diff > 0) { /* shuffle entries down */
1255 for (end = to + n; to < end; to++)
1256 rangeTable[to] = rangeTable[to + diff] + delta;
1257 }
1258 else if (diff < 0) { /* shuffle entries up */
1259 for (end = to, to += n; --to >= end;)
1260 rangeTable[to] = rangeTable[to + diff] + delta;
1261 }
1262 else { /* diff == 0: just run through */
1263 for (end = n; end--;)
1264 rangeTable[to++] += delta;
1265 }
1266 }
1267 else {
1268 if (diff > 0) { /* shuffle entries down */
1269 for (end = to + n; to < end; to++)
1270 rangeTable[to] = rangeTable[to + diff];
1271 }
1272 else if (diff < 0) { /* shuffle entries up */
1273 for (end = to, to += n; --to >= end;)
1274 rangeTable[to] = rangeTable[to + diff];
1275 }
1276 /* else diff == 0: nothing to do */
1277 }
1278
1279 return n;
1280 }
1281
1282 /*
1283 ** Functions to adjust a rangeset to include new text or remove old.
1284 ** *** NOTE: No redisplay: that's outside the responsability of these routines.
1285 */
1286
1287 /* "Insert/Delete": if the start point is in or at the end of a range
1288 ** (start < pos && pos <= end), any text inserted will extend that range.
1289 ** Insertions appear to occur before deletions. This will never add new ranges.
1290 */
1291
rangesetInsDelMaintain(Rangeset * rangeset,int pos,int ins,int del)1292 static Rangeset *rangesetInsDelMaintain(Rangeset *rangeset, int pos, int ins, int del)
1293 {
1294 int i, j, n, *rangeTable = (int *)rangeset->ranges;
1295 int end_del, movement;
1296
1297 n = 2 * rangeset->n_ranges;
1298
1299 i = rangesetWeightedAtOrBefore(rangeset, pos);
1300
1301 if (i == n)
1302 return rangesetFixMaxpos(rangeset, ins, del); /* all beyond the end */
1303
1304 end_del = pos + del;
1305 movement = ins - del;
1306
1307 /* the idea now is to determine the first range not concerned with the
1308 movement: its index will be j. For indices j to n-1, we will adjust
1309 position by movement only. (They may need shuffling up or down, depending
1310 on whether ranges have been deleted or created by the change.) */
1311 j = i;
1312 while (j < n && rangeTable[j] <= end_del) /* skip j to first ind beyond changes */
1313 j++;
1314
1315 /* if j moved forward, we have deleted over rangeTable[i] - reduce it accordingly,
1316 accounting for inserts. */
1317 if (j > i)
1318 rangeTable[i] = pos + ins;
1319
1320 /* If i and j both index starts or ends, just copy all the rangeTable[] values down
1321 by j - i spaces, adjusting on the way. Otherwise, move beyond rangeTable[i]
1322 before doing this. */
1323
1324 if (is_start(i) != is_start(j))
1325 i++;
1326
1327 rangesetShuffleToFrom(rangeTable, i, j, n - j, movement);
1328
1329 n -= j - i;
1330 rangeset->n_ranges = n / 2;
1331 rangeset->ranges = RangesRealloc(rangeset->ranges, rangeset->n_ranges);
1332
1333 /* final adjustments */
1334 return rangesetFixMaxpos(rangeset, ins, del);
1335 }
1336
1337 /* "Inclusive": if the start point is in, at the start of, or at the end of a
1338 ** range (start <= pos && pos <= end), any text inserted will extend that range.
1339 ** Insertions appear to occur before deletions. This will never add new ranges.
1340 ** (Almost identical to rangesetInsDelMaintain().)
1341 */
1342
rangesetInclMaintain(Rangeset * rangeset,int pos,int ins,int del)1343 static Rangeset *rangesetInclMaintain(Rangeset *rangeset, int pos, int ins, int del)
1344 {
1345 int i, j, n, *rangeTable = (int *)rangeset->ranges;
1346 int end_del, movement;
1347
1348 n = 2 * rangeset->n_ranges;
1349
1350 i = rangesetWeightedAtOrBefore(rangeset, pos);
1351
1352 if (i == n)
1353 return rangesetFixMaxpos(rangeset, ins, del); /* all beyond the end */
1354
1355 /* if the insert occurs at the start of a range, the following lines will
1356 extend the range, leaving the start of the range at pos. */
1357
1358 if (is_start(i) && rangeTable[i] == pos && ins > 0)
1359 i++;
1360
1361 end_del = pos + del;
1362 movement = ins - del;
1363
1364 /* the idea now is to determine the first range not concerned with the
1365 movement: its index will be j. For indices j to n-1, we will adjust
1366 position by movement only. (They may need shuffling up or down, depending
1367 on whether ranges have been deleted or created by the change.) */
1368 j = i;
1369 while (j < n && rangeTable[j] <= end_del) /* skip j to first ind beyond changes */
1370 j++;
1371
1372 /* if j moved forward, we have deleted over rangeTable[i] - reduce it accordingly,
1373 accounting for inserts. */
1374 if (j > i)
1375 rangeTable[i] = pos + ins;
1376
1377 /* If i and j both index starts or ends, just copy all the rangeTable[] values down
1378 by j - i spaces, adjusting on the way. Otherwise, move beyond rangeTable[i]
1379 before doing this. */
1380
1381 if (is_start(i) != is_start(j))
1382 i++;
1383
1384 rangesetShuffleToFrom(rangeTable, i, j, n - j, movement);
1385
1386 n -= j - i;
1387 rangeset->n_ranges = n / 2;
1388 rangeset->ranges = RangesRealloc(rangeset->ranges, rangeset->n_ranges);
1389
1390 /* final adjustments */
1391 return rangesetFixMaxpos(rangeset, ins, del);
1392 }
1393
1394 /* "Delete/Insert": if the start point is in a range (start < pos &&
1395 ** pos <= end), and the end of deletion is also in a range
1396 ** (start <= pos + del && pos + del < end) any text inserted will extend that
1397 ** range. Deletions appear to occur before insertions. This will never add new
1398 ** ranges.
1399 */
1400
rangesetDelInsMaintain(Rangeset * rangeset,int pos,int ins,int del)1401 static Rangeset *rangesetDelInsMaintain(Rangeset *rangeset, int pos, int ins, int del)
1402 {
1403 int i, j, n, *rangeTable = (int *)rangeset->ranges;
1404 int end_del, movement;
1405
1406 n = 2 * rangeset->n_ranges;
1407
1408 i = rangesetWeightedAtOrBefore(rangeset, pos);
1409
1410 if (i == n)
1411 return rangesetFixMaxpos(rangeset, ins, del); /* all beyond the end */
1412
1413 end_del = pos + del;
1414 movement = ins - del;
1415
1416 /* the idea now is to determine the first range not concerned with the
1417 movement: its index will be j. For indices j to n-1, we will adjust
1418 position by movement only. (They may need shuffling up or down, depending
1419 on whether ranges have been deleted or created by the change.) */
1420 j = i;
1421 while (j < n && rangeTable[j] <= end_del) /* skip j to first ind beyond changes */
1422 j++;
1423
1424 /* if j moved forward, we have deleted over rangeTable[i] - reduce it accordingly,
1425 accounting for inserts. (Note: if rangeTable[j] is an end position, inserted
1426 text will belong to the range that rangeTable[j] closes; otherwise inserted
1427 text does not belong to a range.) */
1428 if (j > i)
1429 rangeTable[i] = (is_end(j)) ? pos + ins : pos;
1430
1431 /* If i and j both index starts or ends, just copy all the rangeTable[] values down
1432 by j - i spaces, adjusting on the way. Otherwise, move beyond rangeTable[i]
1433 before doing this. */
1434
1435 if (is_start(i) != is_start(j))
1436 i++;
1437
1438 rangesetShuffleToFrom(rangeTable, i, j, n - j, movement);
1439
1440 n -= j - i;
1441 rangeset->n_ranges = n / 2;
1442 rangeset->ranges = RangesRealloc(rangeset->ranges, rangeset->n_ranges);
1443
1444 /* final adjustments */
1445 return rangesetFixMaxpos(rangeset, ins, del);
1446 }
1447
1448 /* "Exclusive": if the start point is in, but not at the end of, a range
1449 ** (start < pos && pos < end), and the end of deletion is also in a range
1450 ** (start <= pos + del && pos + del < end) any text inserted will extend that
1451 ** range. Deletions appear to occur before insertions. This will never add new
1452 ** ranges. (Almost identical to rangesetDelInsMaintain().)
1453 */
1454
rangesetExclMaintain(Rangeset * rangeset,int pos,int ins,int del)1455 static Rangeset *rangesetExclMaintain(Rangeset *rangeset, int pos, int ins, int del)
1456 {
1457 int i, j, n, *rangeTable = (int *)rangeset->ranges;
1458 int end_del, movement;
1459
1460 n = 2 * rangeset->n_ranges;
1461
1462 i = rangesetWeightedAtOrBefore(rangeset, pos);
1463
1464 if (i == n)
1465 return rangesetFixMaxpos(rangeset, ins, del); /* all beyond the end */
1466
1467 /* if the insert occurs at the end of a range, the following lines will
1468 skip the range, leaving the end of the range at pos. */
1469
1470 if (is_end(i) && rangeTable[i] == pos && ins > 0)
1471 i++;
1472
1473 end_del = pos + del;
1474 movement = ins - del;
1475
1476 /* the idea now is to determine the first range not concerned with the
1477 movement: its index will be j. For indices j to n-1, we will adjust
1478 position by movement only. (They may need shuffling up or down, depending
1479 on whether ranges have been deleted or created by the change.) */
1480 j = i;
1481 while (j < n && rangeTable[j] <= end_del) /* skip j to first ind beyond changes */
1482 j++;
1483
1484 /* if j moved forward, we have deleted over rangeTable[i] - reduce it accordingly,
1485 accounting for inserts. (Note: if rangeTable[j] is an end position, inserted
1486 text will belong to the range that rangeTable[j] closes; otherwise inserted
1487 text does not belong to a range.) */
1488 if (j > i)
1489 rangeTable[i] = (is_end(j)) ? pos + ins : pos;
1490
1491 /* If i and j both index starts or ends, just copy all the rangeTable[] values down
1492 by j - i spaces, adjusting on the way. Otherwise, move beyond rangeTable[i]
1493 before doing this. */
1494
1495 if (is_start(i) != is_start(j))
1496 i++;
1497
1498 rangesetShuffleToFrom(rangeTable, i, j, n - j, movement);
1499
1500 n -= j - i;
1501 rangeset->n_ranges = n / 2;
1502 rangeset->ranges = RangesRealloc(rangeset->ranges, rangeset->n_ranges);
1503
1504 /* final adjustments */
1505 return rangesetFixMaxpos(rangeset, ins, del);
1506 }
1507
1508 /* "Break": if the modification point pos is strictly inside a range, that range
1509 ** may be broken in two if the deletion point pos+del does not extend beyond the
1510 ** end. Inserted text is never included in the range.
1511 */
1512
rangesetBreakMaintain(Rangeset * rangeset,int pos,int ins,int del)1513 static Rangeset *rangesetBreakMaintain(Rangeset *rangeset, int pos, int ins, int del)
1514 {
1515 int i, j, n, *rangeTable = (int *)rangeset->ranges;
1516 int end_del, movement, need_gap;
1517
1518 n = 2 * rangeset->n_ranges;
1519
1520 i = rangesetWeightedAtOrBefore(rangeset, pos);
1521
1522 if (i == n)
1523 return rangesetFixMaxpos(rangeset, ins, del); /* all beyond the end */
1524
1525 /* if the insert occurs at the end of a range, the following lines will
1526 skip the range, leaving the end of the range at pos. */
1527
1528 if (is_end(i) && rangeTable[i] == pos && ins > 0)
1529 i++;
1530
1531 end_del = pos + del;
1532 movement = ins - del;
1533
1534 /* the idea now is to determine the first range not concerned with the
1535 movement: its index will be j. For indices j to n-1, we will adjust
1536 position by movement only. (They may need shuffling up or down, depending
1537 on whether ranges have been deleted or created by the change.) */
1538 j = i;
1539 while (j < n && rangeTable[j] <= end_del) /* skip j to first ind beyond changes */
1540 j++;
1541
1542 if (j > i)
1543 rangeTable[i] = pos;
1544
1545 /* do we need to insert a gap? yes if pos is in a range and ins > 0 */
1546
1547 /* The logic for the next statement: if i and j are both range ends, range
1548 boundaries indicated by index values between i and j (if any) have been
1549 "skipped". This means that rangeTable[i-1],rangeTable[j] is the current range. We will
1550 be inserting in that range, splitting it. */
1551
1552 need_gap = (is_end(i) && is_end(j) && ins > 0);
1553
1554 /* if we've got start-end or end-start, skip rangeTable[i] */
1555 if (is_start(i) != is_start(j)) { /* one is start, other is end */
1556 if (is_start(i)) {
1557 if (rangeTable[i] == pos)
1558 rangeTable[i] = pos + ins; /* move the range start */
1559 }
1560 i++; /* skip to next index */
1561 }
1562
1563 /* values rangeTable[j] to rangeTable[n-1] must be adjusted by movement and placed in
1564 position. */
1565
1566 if (need_gap)
1567 i += 2; /* make space for the break */
1568
1569 /* adjust other position values: shuffle them up or down if necessary */
1570 rangesetShuffleToFrom(rangeTable, i, j, n - j, movement);
1571
1572 if (need_gap) { /* add the gap informations */
1573 rangeTable[i - 2] = pos;
1574 rangeTable[i - 1] = pos + ins;
1575 }
1576
1577 n -= j - i;
1578 rangeset->n_ranges = n / 2;
1579 rangeset->ranges = RangesRealloc(rangeset->ranges, rangeset->n_ranges);
1580
1581 /* final adjustments */
1582 return rangesetFixMaxpos(rangeset, ins, del);
1583 }
1584
1585 /* -------------------------------------------------------------------------- */
1586
1587 /*
1588 ** Invert the rangeset (replace it with its complement in the range 0-maxpos).
1589 ** Returns the number of ranges if successful, -1 otherwise. Never adds more
1590 ** than one range.
1591 */
1592
RangesetInverse(Rangeset * rangeset)1593 int RangesetInverse(Rangeset *rangeset)
1594 {
1595 int *rangeTable;
1596 int n, has_zero, has_end;
1597
1598 if (!rangeset)
1599 return -1;
1600
1601 rangeTable = (int *)rangeset->ranges;
1602
1603 if (rangeset->n_ranges == 0) {
1604 if (!rangeTable) {
1605 rangeset->ranges = RangesNew(1);
1606 rangeTable = (int *)rangeset->ranges;
1607 }
1608 rangeTable[0] = 0;
1609 rangeTable[1] = rangeset->maxpos;
1610 n = 2;
1611 }
1612 else {
1613 n = rangeset->n_ranges * 2;
1614
1615 /* find out what we have */
1616 has_zero = (rangeTable[0] == 0);
1617 has_end = (rangeTable[n - 1] == rangeset->maxpos);
1618
1619 /* fill the entry "beyond the end" with the buffer's length */
1620 rangeTable[n + 1] = rangeTable[n] = rangeset->maxpos;
1621
1622 if (has_zero) {
1623 /* shuffle down by one */
1624 rangesetShuffleToFrom(rangeTable, 0, 1, n, 0);
1625 n -= 1;
1626 }
1627 else {
1628 /* shuffle up by one */
1629 rangesetShuffleToFrom(rangeTable, 1, 0, n, 0);
1630 rangeTable[0] = 0;
1631 n += 1;
1632 }
1633 if (has_end)
1634 n -= 1;
1635 else
1636 n += 1;
1637 }
1638
1639 rangeset->n_ranges = n / 2;
1640 rangeset->ranges = RangesRealloc((Range *)rangeTable, rangeset->n_ranges);
1641
1642 RangesetRefreshRange(rangeset, 0, rangeset->maxpos);
1643 return rangeset->n_ranges;
1644 }
1645
1646 /* -------------------------------------------------------------------------- */
1647
1648 /*
1649 ** Add the range indicated by the positions start and end. Returns the
1650 ** new number of ranges in the set.
1651 */
1652
RangesetAddBetween(Rangeset * rangeset,int start,int end)1653 int RangesetAddBetween(Rangeset *rangeset, int start, int end)
1654 {
1655 int i, j, n, *rangeTable = (int *)rangeset->ranges;
1656
1657 if (start > end) {
1658 i = start; /* quietly sort the positions */
1659 start = end;
1660 end = i;
1661 }
1662 else if (start == end) {
1663 return rangeset->n_ranges; /* no-op - empty range == no range */
1664 }
1665
1666 n = 2 * rangeset->n_ranges;
1667
1668 if (n == 0) { /* make sure we have space */
1669 rangeset->ranges = RangesNew(1);
1670 rangeTable = (int *)rangeset->ranges;
1671 i = 0;
1672 }
1673 else
1674 i = rangesetWeightedAtOrBefore(rangeset, start);
1675
1676 if (i == n) { /* beyond last range: just add it */
1677 rangeTable[n] = start;
1678 rangeTable[n + 1] = end;
1679 rangeset->n_ranges++;
1680 rangeset->ranges = RangesRealloc(rangeset->ranges, rangeset->n_ranges);
1681
1682 RangesetRefreshRange(rangeset, start, end);
1683 return rangeset->n_ranges;
1684 }
1685
1686 j = i;
1687 while (j < n && rangeTable[j] <= end) /* skip j to first ind beyond changes */
1688 j++;
1689
1690 if (i == j) {
1691 if (is_start(i)) {
1692 /* is_start(i): need to make a gap in range rangeTable[i-1], rangeTable[i] */
1693 rangesetShuffleToFrom(rangeTable, i + 2, i, n - i, 0); /* shuffle up */
1694 rangeTable[i] = start; /* load up new range's limits */
1695 rangeTable[i + 1] = end;
1696 rangeset->n_ranges++; /* we've just created a new range */
1697 rangeset->ranges = RangesRealloc(rangeset->ranges, rangeset->n_ranges);
1698 }
1699 else {
1700 return rangeset->n_ranges; /* no change */
1701 }
1702 }
1703 else {
1704 /* we'll be shuffling down */
1705 if (is_start(i))
1706 rangeTable[i++] = start;
1707 if (is_start(j))
1708 rangeTable[--j] = end;
1709 if (i < j)
1710 rangesetShuffleToFrom(rangeTable, i, j, n - j, 0);
1711 n -= j - i;
1712 rangeset->n_ranges = n / 2;
1713 rangeset->ranges = RangesRealloc(rangeset->ranges, rangeset->n_ranges);
1714 }
1715
1716 RangesetRefreshRange(rangeset, start, end);
1717 return rangeset->n_ranges;
1718 }
1719
1720
1721 /*
1722 ** Remove the range indicated by the positions start and end. Returns the
1723 ** new number of ranges in the set.
1724 */
1725
RangesetRemoveBetween(Rangeset * rangeset,int start,int end)1726 int RangesetRemoveBetween(Rangeset *rangeset, int start, int end)
1727 {
1728 int i, j, n, *rangeTable = (int *)rangeset->ranges;
1729
1730 if (start > end) {
1731 i = start; /* quietly sort the positions */
1732 start = end;
1733 end = i;
1734 }
1735 else if (start == end) {
1736 return rangeset->n_ranges; /* no-op - empty range == no range */
1737 }
1738
1739 n = 2 * rangeset->n_ranges;
1740
1741 i = rangesetWeightedAtOrBefore(rangeset, start);
1742
1743 if (i == n)
1744 return rangeset->n_ranges; /* beyond last range */
1745
1746 j = i;
1747 while (j < n && rangeTable[j] <= end) /* skip j to first ind beyond changes */
1748 j++;
1749
1750 if (i == j) {
1751 /* removal occurs in front of rangeTable[i] */
1752 if (is_start(i))
1753 return rangeset->n_ranges; /* no change */
1754 else {
1755 /* is_end(i): need to make a gap in range rangeTable[i-1], rangeTable[i] */
1756 i--; /* start of current range */
1757 rangesetShuffleToFrom(rangeTable, i + 2, i, n - i, 0); /* shuffle up */
1758 rangeTable[i + 1] = start; /* change end of current range */
1759 rangeTable[i + 2] = end; /* change start of new range */
1760 rangeset->n_ranges++; /* we've just created a new range */
1761 rangeset->ranges = RangesRealloc(rangeset->ranges, rangeset->n_ranges);
1762 }
1763 }
1764 else {
1765 /* removal occurs in front of rangeTable[j]: we'll be shuffling down */
1766 if (is_end(i))
1767 rangeTable[i++] = start;
1768 if (is_end(j))
1769 rangeTable[--j] = end;
1770 if (i < j)
1771 rangesetShuffleToFrom(rangeTable, i, j, n - j, 0);
1772 n -= j - i;
1773 rangeset->n_ranges = n / 2;
1774 rangeset->ranges = RangesRealloc(rangeset->ranges, rangeset->n_ranges);
1775 }
1776
1777 RangesetRefreshRange(rangeset, start, end);
1778 return rangeset->n_ranges;
1779 }
1780
1781 /* -------------------------------------------------------------------------- */
1782
1783