2 * Copyright (c) 1993-1994 by Xerox Corporation. All rights reserved.
4 * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED
5 * OR IMPLIED. ANY USE IS AT YOUR OWN RISK.
7 * Permission is hereby granted to use or copy this program
8 * for any purpose, provided the above notices are retained on all copies.
9 * Permission to modify the code and to distribute modified code is granted,
10 * provided the above notices are retained, and a notice that the code was
11 * modified is included with the above copyright notice.
13 * Author: Hans-J. Boehm (boehm@parc.xerox.com)
15 /* Boehm, October 3, 1994 5:19 pm PDT */
22 /* An implementation of the cord primitives. These are the only */
23 /* Functions that understand the representation. We perform only */
24 /* minimal checks on arguments to these functions. Out of bounds */
25 /* arguments to the iteration functions may result in client functions */
26 /* invoked on garbage data. In most cases, client functions should be */
27 /* programmed defensively enough that this does not result in memory */
30 typedef void (* oom_fn
)(void);
32 oom_fn CORD_oom_fn
= (oom_fn
) 0;
34 # define OUT_OF_MEMORY { if (CORD_oom_fn != (oom_fn) 0) (*CORD_oom_fn)(); \
35 ABORT("Out of memory\n"); }
36 # define ABORT(msg) { fprintf(stderr, "%s\n", msg); abort(); }
38 typedef unsigned long word
;
41 struct Concatenation
{
44 char depth
; /* concatenation nesting depth. */
45 unsigned char left_len
;
46 /* Length of left child if it is sufficiently */
47 /* short; 0 otherwise. */
48 # define MAX_LEFT_LEN 255
50 CORD left
; /* length(left) > 0 */
51 CORD right
; /* length(right) > 0 */
56 char depth
; /* always 0 */
57 char left_len
; /* always 0 */
76 /* Substring nodes are a special case of function nodes. */
77 /* The client_data field is known to point to a substr_args */
78 /* structure, and the function is either CORD_apply_access_fn */
79 /* or CORD_index_access_fn. */
81 /* The following may be applied only to function and concatenation nodes: */
82 #define IS_CONCATENATION(s) (((CordRep *)s)->generic.header == CONCAT_HDR)
84 #define IS_FUNCTION(s) ((((CordRep *)s)->generic.header & FN_HDR) != 0)
86 #define IS_SUBSTR(s) (((CordRep *)s)->generic.header == SUBSTR_HDR)
88 #define LEN(s) (((CordRep *)s) -> generic.len)
89 #define DEPTH(s) (((CordRep *)s) -> generic.depth)
90 #define GEN_LEN(s) (CORD_IS_STRING(s) ? strlen(s) : LEN(s))
92 #define LEFT_LEN(c) ((c) -> left_len != 0? \
94 : (CORD_IS_STRING((c) -> left) ? \
95 (c) -> len - GEN_LEN((c) -> right) \
98 #define SHORT_LIMIT (sizeof(CordRep) - 1)
99 /* Cords shorter than this are C strings */
102 /* Dump the internal representation of x to stdout, with initial */
103 /* indentation level n. */
104 void CORD_dump_inner(CORD x
, unsigned n
)
108 for (i
= 0; i
< (size_t)n
; i
++) {
112 fputs("NIL\n", stdout
);
113 } else if (CORD_IS_STRING(x
)) {
114 for (i
= 0; i
<= SHORT_LIMIT
; i
++) {
115 if (x
[i
] == '\0') break;
118 if (x
[i
] != '\0') fputs("...", stdout
);
120 } else if (IS_CONCATENATION(x
)) {
121 register struct Concatenation
* conc
=
122 &(((CordRep
*)x
) -> concatenation
);
123 printf("Concatenation: %p (len: %d, depth: %d)\n",
124 x
, (int)(conc
-> len
), (int)(conc
-> depth
));
125 CORD_dump_inner(conc
-> left
, n
+1);
126 CORD_dump_inner(conc
-> right
, n
+1);
127 } else /* function */{
128 register struct Function
* func
=
129 &(((CordRep
*)x
) -> function
);
130 if (IS_SUBSTR(x
)) printf("(Substring) ");
131 printf("Function: %p (len: %d): ", x
, (int)(func
-> len
));
132 for (i
= 0; i
< 20 && i
< func
-> len
; i
++) {
133 putchar((*(func
-> fn
))(i
, func
-> client_data
));
135 if (i
< func
-> len
) fputs("...", stdout
);
140 /* Dump the internal representation of x to stdout */
141 void CORD_dump(CORD x
)
143 CORD_dump_inner(x
, 0);
147 CORD
CORD_cat_char_star(CORD x
, const char * y
, size_t leny
)
149 register size_t result_len
;
150 register size_t lenx
;
153 if (x
== CORD_EMPTY
) return(y
);
154 if (leny
== 0) return(x
);
155 if (CORD_IS_STRING(x
)) {
157 result_len
= lenx
+ leny
;
158 if (result_len
<= SHORT_LIMIT
) {
159 register char * result
= GC_MALLOC_ATOMIC(result_len
+1);
161 if (result
== 0) OUT_OF_MEMORY
;
162 memcpy(result
, x
, lenx
);
163 memcpy(result
+ lenx
, y
, leny
);
164 result
[result_len
] = '\0';
165 return((CORD
) result
);
172 register char * new_right
;
173 register size_t right_len
;
177 if (leny
<= SHORT_LIMIT
/2
178 && IS_CONCATENATION(x
)
179 && CORD_IS_STRING(right
= ((CordRep
*)x
) -> concatenation
.right
)) {
180 /* Merge y into right part of x. */
181 if (!CORD_IS_STRING(left
= ((CordRep
*)x
) -> concatenation
.left
)) {
182 right_len
= lenx
- LEN(left
);
183 } else if (((CordRep
*)x
) -> concatenation
.left_len
!= 0) {
184 right_len
= lenx
- ((CordRep
*)x
) -> concatenation
.left_len
;
186 right_len
= strlen(right
);
188 result_len
= right_len
+ leny
; /* length of new_right */
189 if (result_len
<= SHORT_LIMIT
) {
190 new_right
= GC_MALLOC_ATOMIC(result_len
+ 1);
191 memcpy(new_right
, right
, right_len
);
192 memcpy(new_right
+ right_len
, y
, leny
);
193 new_right
[result_len
] = '\0';
198 /* Now fall through to concatenate the two pieces: */
200 if (CORD_IS_STRING(x
)) {
203 depth
= DEPTH(x
) + 1;
206 depth
= DEPTH(x
) + 1;
208 result_len
= lenx
+ leny
;
211 /* The general case; lenx, result_len is known: */
212 register struct Concatenation
* result
;
214 result
= GC_NEW(struct Concatenation
);
215 if (result
== 0) OUT_OF_MEMORY
;
216 result
->header
= CONCAT_HDR
;
217 result
->depth
= depth
;
218 if (lenx
<= MAX_LEFT_LEN
) result
->left_len
= lenx
;
219 result
->len
= result_len
;
222 if (depth
> MAX_DEPTH
) {
223 return(CORD_balance((CORD
)result
));
225 return((CORD
) result
);
231 CORD
CORD_cat(CORD x
, CORD y
)
233 register size_t result_len
;
235 register size_t lenx
;
237 if (x
== CORD_EMPTY
) return(y
);
238 if (y
== CORD_EMPTY
) return(x
);
239 if (CORD_IS_STRING(y
)) {
240 return(CORD_cat_char_star(x
, y
, strlen(y
)));
241 } else if (CORD_IS_STRING(x
)) {
243 depth
= DEPTH(y
) + 1;
245 register int depthy
= DEPTH(y
);
248 depth
= DEPTH(x
) + 1;
249 if (depthy
>= depth
) depth
= depthy
+ 1;
251 result_len
= lenx
+ LEN(y
);
253 register struct Concatenation
* result
;
255 result
= GC_NEW(struct Concatenation
);
256 if (result
== 0) OUT_OF_MEMORY
;
257 result
->header
= CONCAT_HDR
;
258 result
->depth
= depth
;
259 if (lenx
<= MAX_LEFT_LEN
) result
->left_len
= lenx
;
260 result
->len
= result_len
;
263 return((CORD
) result
);
269 CORD
CORD_from_fn(CORD_fn fn
, void * client_data
, size_t len
)
271 if (len
<= 0) return(0);
272 if (len
<= SHORT_LIMIT
) {
273 register char * result
;
275 char buf
[SHORT_LIMIT
+1];
278 for (i
= 0; i
< len
; i
++) {
279 c
= (*fn
)(i
, client_data
);
280 if (c
== '\0') goto gen_case
;
284 result
= GC_MALLOC_ATOMIC(len
+1);
285 if (result
== 0) OUT_OF_MEMORY
;
288 return((CORD
) result
);
292 register struct Function
* result
;
294 result
= GC_NEW(struct Function
);
295 if (result
== 0) OUT_OF_MEMORY
;
296 result
->header
= FN_HDR
;
297 /* depth is already 0 */
300 result
->client_data
= client_data
;
301 return((CORD
) result
);
305 size_t CORD_len(CORD x
)
319 char CORD_index_access_fn(size_t i
, void * client_data
)
321 register struct substr_args
*descr
= (struct substr_args
*)client_data
;
323 return(((char *)(descr
->sa_cord
))[i
+ descr
->sa_index
]);
326 char CORD_apply_access_fn(size_t i
, void * client_data
)
328 register struct substr_args
*descr
= (struct substr_args
*)client_data
;
329 register struct Function
* fn_cord
= &(descr
->sa_cord
->function
);
331 return((*(fn_cord
->fn
))(i
+ descr
->sa_index
, fn_cord
->client_data
));
334 /* A version of CORD_substr that simply returns a function node, thus */
335 /* postponing its work. The fourth argument is a function that may */
336 /* be used for efficient access to the ith character. */
337 /* Assumes i >= 0 and i + n < length(x). */
338 CORD
CORD_substr_closure(CORD x
, size_t i
, size_t n
, CORD_fn f
)
340 register struct substr_args
* sa
= GC_NEW(struct substr_args
);
343 if (sa
== 0) OUT_OF_MEMORY
;
344 sa
->sa_cord
= (CordRep
*)x
;
346 result
= CORD_from_fn(f
, (void *)sa
, n
);
347 ((CordRep
*)result
) -> function
.header
= SUBSTR_HDR
;
351 # define SUBSTR_LIMIT (10 * SHORT_LIMIT)
352 /* Substrings of function nodes and flat strings shorter than */
353 /* this are flat strings. Othewise we use a functional */
354 /* representation, which is significantly slower to access. */
356 /* A version of CORD_substr that assumes i >= 0, n > 0, and i + n < length(x).*/
357 CORD
CORD_substr_checked(CORD x
, size_t i
, size_t n
)
359 if (CORD_IS_STRING(x
)) {
360 if (n
> SUBSTR_LIMIT
) {
361 return(CORD_substr_closure(x
, i
, n
, CORD_index_access_fn
));
363 register char * result
= GC_MALLOC_ATOMIC(n
+1);
365 if (result
== 0) OUT_OF_MEMORY
;
366 strncpy(result
, x
+i
, n
);
370 } else if (IS_CONCATENATION(x
)) {
371 register struct Concatenation
* conc
372 = &(((CordRep
*)x
) -> concatenation
);
373 register size_t left_len
;
374 register size_t right_len
;
376 left_len
= LEFT_LEN(conc
);
377 right_len
= conc
-> len
- left_len
;
379 if (n
== right_len
) return(conc
-> right
);
380 return(CORD_substr_checked(conc
-> right
, i
- left_len
, n
));
381 } else if (i
+n
<= left_len
) {
382 if (n
== left_len
) return(conc
-> left
);
383 return(CORD_substr_checked(conc
-> left
, i
, n
));
385 /* Need at least one character from each side. */
386 register CORD left_part
;
387 register CORD right_part
;
388 register size_t left_part_len
= left_len
- i
;
391 left_part
= conc
-> left
;
393 left_part
= CORD_substr_checked(conc
-> left
, i
, left_part_len
);
395 if (i
+ n
== right_len
+ left_len
) {
396 right_part
= conc
-> right
;
398 right_part
= CORD_substr_checked(conc
-> right
, 0,
401 return(CORD_cat(left_part
, right_part
));
403 } else /* function */ {
404 if (n
> SUBSTR_LIMIT
) {
406 /* Avoid nesting substring nodes. */
407 register struct Function
* f
= &(((CordRep
*)x
) -> function
);
408 register struct substr_args
*descr
=
409 (struct substr_args
*)(f
-> client_data
);
411 return(CORD_substr_closure((CORD
)descr
->sa_cord
,
415 return(CORD_substr_closure(x
, i
, n
, CORD_apply_access_fn
));
419 register struct Function
* f
= &(((CordRep
*)x
) -> function
);
420 char buf
[SUBSTR_LIMIT
+1];
421 register char * p
= buf
;
424 register int lim
= i
+ n
;
426 for (j
= i
; j
< lim
; j
++) {
427 c
= (*(f
-> fn
))(j
, f
-> client_data
);
429 return(CORD_substr_closure(x
, i
, n
, CORD_apply_access_fn
));
434 result
= GC_MALLOC_ATOMIC(n
+1);
435 if (result
== 0) OUT_OF_MEMORY
;
442 CORD
CORD_substr(CORD x
, size_t i
, size_t n
)
444 register size_t len
= CORD_len(x
);
446 if (i
>= len
|| n
<= 0) return(0);
447 /* n < 0 is impossible in a correct C implementation, but */
448 /* quite possible under SunOS 4.X. */
449 if (i
+ n
> len
) n
= len
- i
;
451 if (i
< 0) ABORT("CORD_substr: second arg. negative");
452 /* Possible only if both client and C implementation are buggy. */
453 /* But empirically this happens frequently. */
455 return(CORD_substr_checked(x
, i
, n
));
458 /* See cord.h for definition. We assume i is in range. */
459 int CORD_iter5(CORD x
, size_t i
, CORD_iter_fn f1
,
460 CORD_batched_iter_fn f2
, void * client_data
)
462 if (x
== 0) return(0);
463 if (CORD_IS_STRING(x
)) {
464 register const char *p
= x
+i
;
466 if (*p
== '\0') ABORT("2nd arg to CORD_iter5 too big");
467 if (f2
!= CORD_NO_FN
) {
468 return((*f2
)(p
, client_data
));
471 if ((*f1
)(*p
, client_data
)) return(1);
476 } else if (IS_CONCATENATION(x
)) {
477 register struct Concatenation
* conc
478 = &(((CordRep
*)x
) -> concatenation
);
482 register size_t left_len
= LEFT_LEN(conc
);
485 return(CORD_iter5(conc
-> right
, i
- left_len
, f1
, f2
,
489 if (CORD_iter5(conc
-> left
, i
, f1
, f2
, client_data
)) {
492 return(CORD_iter5(conc
-> right
, 0, f1
, f2
, client_data
));
493 } else /* function */ {
494 register struct Function
* f
= &(((CordRep
*)x
) -> function
);
496 register size_t lim
= f
-> len
;
498 for (j
= i
; j
< lim
; j
++) {
499 if ((*f1
)((*(f
-> fn
))(j
, f
-> client_data
), client_data
)) {
508 int CORD_iter(CORD x
, CORD_iter_fn f1
, void * client_data
)
510 return(CORD_iter5(x
, 0, f1
, CORD_NO_FN
, client_data
));
513 int CORD_riter4(CORD x
, size_t i
, CORD_iter_fn f1
, void * client_data
)
515 if (x
== 0) return(0);
516 if (CORD_IS_STRING(x
)) {
517 register const char *p
= x
+ i
;
522 if (c
== '\0') ABORT("2nd arg to CORD_riter4 too big");
523 if ((*f1
)(c
, client_data
)) return(1);
528 } else if (IS_CONCATENATION(x
)) {
529 register struct Concatenation
* conc
530 = &(((CordRep
*)x
) -> concatenation
);
531 register CORD left_part
= conc
-> left
;
532 register size_t left_len
;
534 left_len
= LEFT_LEN(conc
);
536 if (CORD_riter4(conc
-> right
, i
- left_len
, f1
, client_data
)) {
539 return(CORD_riter4(left_part
, left_len
- 1, f1
, client_data
));
541 return(CORD_riter4(left_part
, i
, f1
, client_data
));
543 } else /* function */ {
544 register struct Function
* f
= &(((CordRep
*)x
) -> function
);
548 if ((*f1
)((*(f
-> fn
))(j
, f
-> client_data
), client_data
)) {
551 if (j
== 0) return(0);
556 int CORD_riter(CORD x
, CORD_iter_fn f1
, void * client_data
)
558 return(CORD_riter4(x
, CORD_len(x
) - 1, f1
, client_data
));
562 * The following functions are concerned with balancing cords.
564 * Scan the cord from left to right, keeping the cord scanned so far
565 * as a forest of balanced trees of exponentialy decreasing length.
566 * When a new subtree needs to be added to the forest, we concatenate all
567 * shorter ones to the new tree in the appropriate order, and then insert
568 * the result into the forest.
569 * Crucial invariants:
570 * 1. The concatenation of the forest (in decreasing order) with the
571 * unscanned part of the rope is equal to the rope being balanced.
572 * 2. All trees in the forest are balanced.
573 * 3. forest[i] has depth at most i.
578 size_t len
; /* Actual length of c */
581 static size_t min_len
[ MAX_DEPTH
];
583 static int min_len_init
= 0;
587 typedef ForestElement Forest
[ MAX_DEPTH
];
588 /* forest[i].len >= fib(i+1) */
589 /* The string is the concatenation */
590 /* of the forest in order of DECREASING */
593 void CORD_init_min_len()
596 register size_t last
, previous
, current
;
598 min_len
[0] = previous
= 1;
599 min_len
[1] = last
= 2;
600 for (i
= 2; i
< MAX_DEPTH
; i
++) {
601 current
= last
+ previous
;
602 if (current
< last
) /* overflow */ current
= last
;
603 min_len
[i
] = current
;
607 CORD_max_len
= last
- 1;
612 void CORD_init_forest(ForestElement
* forest
, size_t max_len
)
616 for (i
= 0; i
< MAX_DEPTH
; i
++) {
618 if (min_len
[i
] > max_len
) return;
620 ABORT("Cord too long");
623 /* Add a leaf to the appropriate level in the forest, cleaning */
624 /* out lower levels as necessary. */
625 /* Also works if x is a balanced tree of concatenations; however */
626 /* in this case an extra concatenation node may be inserted above x; */
627 /* This node should not be counted in the statement of the invariants. */
628 void CORD_add_forest(ForestElement
* forest
, CORD x
, size_t len
)
631 register CORD sum
= CORD_EMPTY
;
632 register size_t sum_len
= 0;
634 while (len
> min_len
[i
+ 1]) {
635 if (forest
[i
].c
!= 0) {
636 sum
= CORD_cat(forest
[i
].c
, sum
);
637 sum_len
+= forest
[i
].len
;
642 /* Sum has depth at most 1 greter than what would be required */
644 sum
= CORD_cat(sum
, x
);
646 /* If x was a leaf, then sum is now balanced. To see this */
647 /* consider the two cases in which forest[i-1] either is or is */
649 while (sum_len
>= min_len
[i
]) {
650 if (forest
[i
].c
!= 0) {
651 sum
= CORD_cat(forest
[i
].c
, sum
);
652 sum_len
+= forest
[i
].len
;
653 /* This is again balanced, since sum was balanced, and has */
654 /* allowable depth that differs from i by at most 1. */
661 forest
[i
].len
= sum_len
;
664 CORD
CORD_concat_forest(ForestElement
* forest
, size_t expected_len
)
670 while (sum_len
!= expected_len
) {
671 if (forest
[i
].c
!= 0) {
672 sum
= CORD_cat(forest
[i
].c
, sum
);
673 sum_len
+= forest
[i
].len
;
680 /* Insert the frontier of x into forest. Balanced subtrees are */
681 /* treated as leaves. This potentially adds one to the depth */
682 /* of the final tree. */
683 void CORD_balance_insert(CORD x
, size_t len
, ForestElement
* forest
)
687 if (CORD_IS_STRING(x
)) {
688 CORD_add_forest(forest
, x
, len
);
689 } else if (IS_CONCATENATION(x
)
690 && ((depth
= DEPTH(x
)) >= MAX_DEPTH
691 || len
< min_len
[depth
])) {
692 register struct Concatenation
* conc
693 = &(((CordRep
*)x
) -> concatenation
);
694 size_t left_len
= LEFT_LEN(conc
);
696 CORD_balance_insert(conc
-> left
, left_len
, forest
);
697 CORD_balance_insert(conc
-> right
, len
- left_len
, forest
);
698 } else /* function or balanced */ {
699 CORD_add_forest(forest
, x
, len
);
704 CORD
CORD_balance(CORD x
)
709 if (x
== 0) return(0);
710 if (CORD_IS_STRING(x
)) return(x
);
711 if (!min_len_init
) CORD_init_min_len();
713 CORD_init_forest(forest
, len
);
714 CORD_balance_insert(x
, len
, forest
);
715 return(CORD_concat_forest(forest
, len
));
719 /* Position primitives */
721 /* Private routines to deal with the hard cases only: */
723 /* P contains a prefix of the path to cur_pos. Extend it to a full */
724 /* path and set up leaf info. */
725 /* Return 0 if past the end of cord, 1 o.w. */
726 void CORD__extend_path(register CORD_pos p
)
728 register struct CORD_pe
* current_pe
= &(p
[0].path
[p
[0].path_len
]);
729 register CORD top
= current_pe
-> pe_cord
;
730 register size_t pos
= p
[0].cur_pos
;
731 register size_t top_pos
= current_pe
-> pe_start_pos
;
732 register size_t top_len
= GEN_LEN(top
);
734 /* Fill in the rest of the path. */
735 while(!CORD_IS_STRING(top
) && IS_CONCATENATION(top
)) {
736 register struct Concatenation
* conc
=
737 &(((CordRep
*)top
) -> concatenation
);
738 register size_t left_len
;
740 left_len
= LEFT_LEN(conc
);
742 if (pos
>= top_pos
+ left_len
) {
743 current_pe
-> pe_cord
= top
= conc
-> right
;
744 current_pe
-> pe_start_pos
= top_pos
= top_pos
+ left_len
;
747 current_pe
-> pe_cord
= top
= conc
-> left
;
748 current_pe
-> pe_start_pos
= top_pos
;
753 /* Fill in leaf description for fast access. */
754 if (CORD_IS_STRING(top
)) {
756 p
[0].cur_start
= top_pos
;
757 p
[0].cur_end
= top_pos
+ top_len
;
761 if (pos
>= top_pos
+ top_len
) p
[0].path_len
= CORD_POS_INVALID
;
764 char CORD__pos_fetch(register CORD_pos p
)
766 /* Leaf is a function node */
767 struct CORD_pe
* pe
= &((p
)[0].path
[(p
)[0].path_len
]);
768 CORD leaf
= pe
-> pe_cord
;
769 register struct Function
* f
= &(((CordRep
*)leaf
) -> function
);
771 if (!IS_FUNCTION(leaf
)) ABORT("CORD_pos_fetch: bad leaf");
772 return ((*(f
-> fn
))(p
[0].cur_pos
- pe
-> pe_start_pos
, f
-> client_data
));
775 void CORD__next(register CORD_pos p
)
777 register size_t cur_pos
= p
[0].cur_pos
+ 1;
778 register struct CORD_pe
* current_pe
= &((p
)[0].path
[(p
)[0].path_len
]);
779 register CORD leaf
= current_pe
-> pe_cord
;
781 /* Leaf is not a string or we're at end of leaf */
782 p
[0].cur_pos
= cur_pos
;
783 if (!CORD_IS_STRING(leaf
)) {
785 register struct Function
* f
= &(((CordRep
*)leaf
) -> function
);
786 register size_t start_pos
= current_pe
-> pe_start_pos
;
787 register size_t end_pos
= start_pos
+ f
-> len
;
789 if (cur_pos
< end_pos
) {
790 /* Fill cache and return. */
792 register size_t limit
= cur_pos
+ FUNCTION_BUF_SZ
;
793 register CORD_fn fn
= f
-> fn
;
794 register void * client_data
= f
-> client_data
;
796 if (limit
> end_pos
) {
799 for (i
= cur_pos
; i
< limit
; i
++) {
800 p
[0].function_buf
[i
- cur_pos
] =
801 (*fn
)(i
- start_pos
, client_data
);
803 p
[0].cur_start
= cur_pos
;
804 p
[0].cur_leaf
= p
[0].function_buf
;
805 p
[0].cur_end
= limit
;
810 /* Pop the stack until we find two concatenation nodes with the */
811 /* same start position: this implies we were in left part. */
813 while (p
[0].path_len
> 0
814 && current_pe
[0].pe_start_pos
!= current_pe
[-1].pe_start_pos
) {
818 if (p
[0].path_len
== 0) {
819 p
[0].path_len
= CORD_POS_INVALID
;
824 CORD__extend_path(p
);
827 void CORD__prev(register CORD_pos p
)
829 register struct CORD_pe
* pe
= &(p
[0].path
[p
[0].path_len
]);
831 if (p
[0].cur_pos
== 0) {
832 p
[0].path_len
= CORD_POS_INVALID
;
836 if (p
[0].cur_pos
>= pe
-> pe_start_pos
) return;
838 /* Beginning of leaf */
840 /* Pop the stack until we find two concatenation nodes with the */
841 /* different start position: this implies we were in right part. */
843 register struct CORD_pe
* current_pe
= &((p
)[0].path
[(p
)[0].path_len
]);
845 while (p
[0].path_len
> 0
846 && current_pe
[0].pe_start_pos
== current_pe
[-1].pe_start_pos
) {
852 CORD__extend_path(p
);
855 #undef CORD_pos_fetch
858 #undef CORD_pos_to_index
859 #undef CORD_pos_to_cord
860 #undef CORD_pos_valid
862 char CORD_pos_fetch(register CORD_pos p
)
864 if (p
[0].cur_start
<= p
[0].cur_pos
&& p
[0].cur_pos
< p
[0].cur_end
) {
865 return(p
[0].cur_leaf
[p
[0].cur_pos
- p
[0].cur_start
]);
867 return(CORD__pos_fetch(p
));
871 void CORD_next(CORD_pos p
)
873 if (p
[0].cur_pos
< p
[0].cur_end
- 1) {
880 void CORD_prev(CORD_pos p
)
882 if (p
[0].cur_end
!= 0 && p
[0].cur_pos
> p
[0].cur_start
) {
889 size_t CORD_pos_to_index(CORD_pos p
)
891 return(p
[0].cur_pos
);
894 CORD
CORD_pos_to_cord(CORD_pos p
)
896 return(p
[0].path
[0].pe_cord
);
899 int CORD_pos_valid(CORD_pos p
)
901 return(p
[0].path_len
!= CORD_POS_INVALID
);
904 void CORD_set_pos(CORD_pos p
, CORD x
, size_t i
)
906 if (x
== CORD_EMPTY
) {
907 p
[0].path_len
= CORD_POS_INVALID
;
910 p
[0].path
[0].pe_cord
= x
;
911 p
[0].path
[0].pe_start_pos
= 0;
914 CORD__extend_path(p
);