Debian Codegraph @

gc/include/cord.h

raw
1 /*
2 * Copyright (c) 1993-1994 by Xerox Corporation. All rights reserved.
3 *
4 * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED
5 * OR IMPLIED. ANY USE IS AT YOUR OWN RISK.
6 *
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.
12 */
13
14 /*
15 * Cords are immutable character strings. A number of operations
16 * on long cords are much more efficient than their strings.h counterpart.
17 * In particular, concatenation takes constant time independent of the length
18 * of the arguments. (Cords are represented as trees, with internal
19 * nodes representing concatenation and leaves consisting of either C
20 * strings or a functional description of the string.)
21 *
22 * The following are reasonable applications of cords. They would perform
23 * unacceptably if C strings were used:
24 * - A compiler that produces assembly language output by repeatedly
25 * concatenating instructions onto a cord representing the output file.
26 * - A text editor that converts the input file to a cord, and then
27 * performs editing operations by producing a new cord representing
28 * the file after each character change (and keeping the old ones in an
29 * edit history).
30 *
31 * For optimal performance, cords should be built by
32 * concatenating short sections.
33 * This interface is designed for maximum compatibility with C strings.
34 * ASCII NUL characters may be embedded in cords using CORD_from_fn.
35 * This is handled correctly, but CORD_to_char_star will produce a string
36 * with embedded NULs when given such a cord.
37 *
38 * This interface is fairly big, largely for performance reasons.
39 * The most basic constants and functions:
40 *
41 * CORD - the type of a cord;
42 * CORD_EMPTY - empty cord;
43 * CORD_len(cord) - length of a cord;
44 * CORD_cat(cord1,cord2) - concatenation of two cords;
45 * CORD_substr(cord, start, len) - substring (or subcord);
46 * CORD_pos i; CORD_FOR(i, cord) { ... CORD_pos_fetch(i) ... } -
47 * examine each character in a cord (CORD_pos_fetch(i) is the char);
48 * CORD_fetch(int i) - Retrieve i'th character (slowly);
49 * CORD_cmp(cord1, cord2) - compare two cords;
50 * CORD_from_file(FILE * f) - turn a read-only file into a cord;
51 * CORD_to_char_star(cord) - convert to C string
52 * (non-NULL C constant strings are cords);
53 * CORD_printf (etc.) - cord version of printf (use %r for cords).
54 */
55
56 #ifndef CORD_H
57 #define CORD_H
58
59 #include <stddef.h>
60 #include <stdio.h>
61
62 #ifdef __cplusplus
63 extern "C" {
64 #endif
65
66 #if defined(GC_DLL) && !defined(CORD_NOT_DLL)
67 /* Same as for GC_API in gc_config_macros.h. */
68 # ifdef CORD_BUILD
69 # if defined(__MINGW32__) || defined(__CEGCC__)
70 # define CORD_API __declspec(dllexport)
71 # elif defined(_MSC_VER) || defined(__DMC__) || defined(__BORLANDC__) \
72 || defined(__CYGWIN__) || defined(__WATCOMC__)
73 # define CORD_API extern __declspec(dllexport)
74 # elif defined(__GNUC__) && !defined(GC_NO_VISIBILITY) \
75 && (__GNUC__ >= 4 || defined(GC_VISIBILITY_HIDDEN_SET))
76 /* Only matters if used in conjunction with -fvisibility=hidden option. */
77 # define CORD_API extern __attribute__((__visibility__("default")))
78 # endif
79 # else
80 # if defined(__MINGW32__) || defined(__CEGCC__) || defined(_MSC_VER) \
81 || defined(__DMC__) || defined(__BORLANDC__) || defined(__CYGWIN__)
82 # define CORD_API __declspec(dllimport)
83 # elif defined(__WATCOMC__)
84 # define CORD_API extern __declspec(dllimport)
85 # endif
86 # endif /* !CORD_BUILD */
87 #endif /* GC_DLL */
88
89 #ifndef CORD_API
90 # define CORD_API extern
91 #endif
92
93 /* Cords have type const char *. This is cheating quite a bit, and not */
94 /* 100% portable. But it means that nonempty character string */
95 /* constants may be used as cords directly, provided the string is */
96 /* never modified in place. The empty cord is represented by, and */
97 /* can be written as, 0. */
98
99 typedef const char * CORD;
100
101 /* An empty cord is always represented as nil. */
102 #define CORD_EMPTY 0
103
104 /* Is a nonempty cord represented as a C string? */
105 #define CORD_IS_STRING(s) (*(s) != '\0')
106
107 /* Concatenate two cords. If the arguments are C strings, they may */
108 /* not be subsequently altered. */
109 CORD_API CORD CORD_cat(CORD x, CORD y);
110
111 /* Concatenate a cord and a C string with known length. Except for the */
112 /* empty string case, this is a special case of CORD_cat. Since the */
113 /* length is known, it can be faster. */
114 /* The string y is shared with the resulting CORD. Hence it should */
115 /* not be altered by the caller. */
116 CORD_API CORD CORD_cat_char_star(CORD x, const char * y, size_t leny);
117
118 /* Compute the length of a cord. */
119 CORD_API size_t CORD_len(CORD x);
120
121 /* Cords may be represented by functions defining the ith character. */
122 typedef char (* CORD_fn)(size_t i, void * client_data);
123
124 /* Turn a functional description into a cord. */
125 CORD_API CORD CORD_from_fn(CORD_fn fn, void * client_data, size_t len);
126
127 /* Return the substring (subcord really) of x with length at most n, */
128 /* starting at position i. (The initial character has position 0.) */
129 CORD_API CORD CORD_substr(CORD x, size_t i, size_t n);
130
131 /* Return the argument, but rebalanced to allow more efficient */
132 /* character retrieval, substring operations, and comparisons. */
133 /* This is useful only for cords that were built using repeated */
134 /* concatenation. Guarantees log time access to the result, unless */
135 /* x was obtained through a large number of repeated substring ops */
136 /* or the embedded functional descriptions take longer to evaluate. */
137 /* May reallocate significant parts of the cord. The argument is not */
138 /* modified; only the result is balanced. */
139 CORD_API CORD CORD_balance(CORD x);
140
141 /* The following traverse a cord by applying a function to each */
142 /* character. This is occasionally appropriate, especially where */
143 /* speed is crucial. But, since C doesn't have nested functions, */
144 /* clients of this sort of traversal are clumsy to write. Consider */
145 /* the functions that operate on cord positions instead. */
146
147 /* Function to iteratively apply to individual characters in cord. */
148 typedef int (* CORD_iter_fn)(char c, void * client_data);
149
150 /* Function to apply to substrings of a cord. Each substring is a */
151 /* a C character string, not a general cord. */
152 typedef int (* CORD_batched_iter_fn)(const char * s, void * client_data);
153 #define CORD_NO_FN ((CORD_batched_iter_fn)0)
154
155 /* Apply f1 to each character in the cord, in ascending order, */
156 /* starting at position i. If f2 is not CORD_NO_FN, then */
157 /* multiple calls to f1 may be replaced by */
158 /* a single call to f2. The parameter f2 is provided only to allow */
159 /* some optimization by the client. This terminates when the right */
160 /* end of this string is reached, or when f1 or f2 return != 0. In the */
161 /* latter case CORD_iter returns != 0. Otherwise it returns 0. */
162 /* The specified value of i must be < CORD_len(x). */
163 CORD_API int CORD_iter5(CORD x, size_t i, CORD_iter_fn f1,
164 CORD_batched_iter_fn f2, void * client_data);
165
166 /* A simpler version that starts at 0, and without f2. */
167 CORD_API int CORD_iter(CORD x, CORD_iter_fn f1, void * client_data);
168 #define CORD_iter(x, f1, cd) CORD_iter5(x, 0, f1, CORD_NO_FN, cd)
169
170 /* Similar to CORD_iter5, but end-to-beginning. No provisions for */
171 /* CORD_batched_iter_fn. */
172 CORD_API int CORD_riter4(CORD x, size_t i, CORD_iter_fn f1, void * client_data);
173
174 /* A simpler version that starts at the end. */
175 CORD_API int CORD_riter(CORD x, CORD_iter_fn f1, void * client_data);
176
177 #ifdef __cplusplus
178 } /* extern "C" */
179 #endif
180
181 /* Functions that operate on cord positions. The easy way to traverse */
182 /* cords. A cord position is logically a pair consisting of a cord */
183 /* and an index into that cord. But it is much faster to retrieve a */
184 /* character based on a position than on an index. Unfortunately, */
185 /* positions are big (order of a few 100 bytes), so allocate them with */
186 /* caution. */
187 /* Things in cord_pos.h should be treated as opaque, except as */
188 /* described below. Also, note that CORD_pos_fetch, CORD_next and */
189 /* CORD_prev have both macro and function definitions. The former */
190 /* may evaluate their argument more than once. */
191 #include "cord_pos.h"
192
193 #ifdef __cplusplus
194 extern "C" {
195 #endif
196
197 /*
198 Visible definitions from above:
199
200 typedef <OPAQUE but fairly big> CORD_pos[1];
201
202 * Extract the cord from a position:
203 CORD CORD_pos_to_cord(CORD_pos p);
204
205 * Extract the current index from a position:
206 size_t CORD_pos_to_index(CORD_pos p);
207
208 * Fetch the character located at the given position:
209 char CORD_pos_fetch(CORD_pos p);
210
211 * Initialize the position to refer to the given cord and index.
212 * Note that this is the most expensive function on positions:
213 void CORD_set_pos(CORD_pos p, CORD x, size_t i);
214
215 * Advance the position to the next character.
216 * P must be initialized and valid.
217 * Invalidates p if past end:
218 void CORD_next(CORD_pos p);
219
220 * Move the position to the preceding character.
221 * P must be initialized and valid.
222 * Invalidates p if past beginning:
223 void CORD_prev(CORD_pos p);
224
225 * Is the position valid, i.e. inside the cord?
226 int CORD_pos_valid(CORD_pos p);
227 */
228 #define CORD_FOR(pos, cord) \
229 for (CORD_set_pos(pos, cord, 0); CORD_pos_valid(pos); CORD_next(pos))
230
231
232 /* An out of memory handler to call. May be supplied by client. */
233 /* Must not return. */
234 extern void (* CORD_oom_fn)(void);
235
236 /* Dump the representation of x to stdout in an implementation defined */
237 /* manner. Intended for debugging only. */
238 CORD_API void CORD_dump(CORD x);
239
240 /* The following could easily be implemented by the client. They are */
241 /* provided in cordxtra.c for convenience. */
242
243 /* Concatenate a character to the end of a cord. */
244 CORD_API CORD CORD_cat_char(CORD x, char c);
245
246 /* Concatenate n cords. */
247 CORD_API CORD CORD_catn(int n, /* CORD */ ...);
248
249 /* Return the character in CORD_substr(x, i, 1). */
250 CORD_API char CORD_fetch(CORD x, size_t i);
251
252 /* Return < 0, 0, or > 0, depending on whether x < y, x = y, x > y. */
253 CORD_API int CORD_cmp(CORD x, CORD y);
254
255 /* A generalization that takes both starting positions for the */
256 /* comparison, and a limit on the number of characters to be compared. */
257 CORD_API int CORD_ncmp(CORD x, size_t x_start, CORD y, size_t y_start,
258 size_t len);
259
260 /* Find the first occurrence of s in x at position start or later. */
261 /* Return the position of the first character of s in x, or */
262 /* CORD_NOT_FOUND if there is none. */
263 CORD_API size_t CORD_str(CORD x, size_t start, CORD s);
264
265 /* Return a cord consisting of i copies of (possibly NUL) c. Dangerous */
266 /* in conjunction with CORD_to_char_star. */
267 /* The resulting representation takes constant space, independent of i. */
268 CORD_API CORD CORD_chars(char c, size_t i);
269 #define CORD_nul(i) CORD_chars('\0', (i))
270
271 /* Turn a file into cord. The file must be seekable. Its contents */
272 /* must remain constant. The file may be accessed as an immediate */
273 /* result of this call and/or as a result of subsequent accesses to */
274 /* the cord. Short files are likely to be immediately read, but */
275 /* long files are likely to be read on demand, possibly relying on */
276 /* stdio for buffering. */
277 /* We must have exclusive access to the descriptor f, i.e. we may */
278 /* read it at any time, and expect the file pointer to be */
279 /* where we left it. Normally this should be invoked as */
280 /* CORD_from_file(fopen(...)). */
281 /* CORD_from_file arranges to close the file descriptor when it is no */
282 /* longer needed (e.g. when the result becomes inaccessible). */
283 /* The file f must be such that ftell reflects the actual character */
284 /* position in the file, i.e. the number of characters that can be */
285 /* or were read with fread. On UNIX systems this is always true. */
286 /* On Windows systems, f must be opened in binary mode. */
287 CORD_API CORD CORD_from_file(FILE * f);
288
289 /* Equivalent to the above, except that the entire file will be read */
290 /* and the file pointer will be closed immediately. */
291 /* The binary mode restriction from above does not apply. */
292 CORD_API CORD CORD_from_file_eager(FILE * f);
293
294 /* Equivalent to the above, except that the file will be read on */
295 /* demand. The binary mode restriction applies. */
296 CORD_API CORD CORD_from_file_lazy(FILE * f);
297
298 /* Turn a cord into a C string. The result shares no structure with */
299 /* x, and is thus modifiable. */
300 CORD_API char * CORD_to_char_star(CORD x);
301
302 /* Turn a C string into a CORD. The C string is copied, and so may */
303 /* subsequently be modified. */
304 CORD_API CORD CORD_from_char_star(const char *s);
305
306 /* Identical to the above, but the result may share structure with */
307 /* the argument and is thus not modifiable. */
308 CORD_API const char * CORD_to_const_char_star(CORD x);
309
310 /* Write a cord to a file, starting at the current position. */
311 /* No trailing NULs are newlines are added. */
312 /* Returns EOF if a write error occurs, 1 otherwise. */
313 CORD_API int CORD_put(CORD x, FILE * f);
314
315 /* "Not found" result for the following two functions. */
316 #define CORD_NOT_FOUND ((size_t)(-1))
317
318 /* A vague analog of strchr. Returns the position (an integer, not */
319 /* a pointer) of the first occurrence of (char) c inside x at position */
320 /* i or later. The value i must be < CORD_len(x). */
321 CORD_API size_t CORD_chr(CORD x, size_t i, int c);
322
323 /* A vague analog of strrchr. Returns index of the last occurrence */
324 /* of (char) c inside x at position i or earlier. The value i */
325 /* must be < CORD_len(x). */
326 CORD_API size_t CORD_rchr(CORD x, size_t i, int c);
327
328 #ifdef __cplusplus
329 } /* extern "C" */
330 #endif
331
332 /* The following are also not primitive, but are implemented in */
333 /* cordprnt.c. They provide functionality similar to the ANSI C */
334 /* functions with corresponding names, but with the following */
335 /* additions and changes: */
336 /* 1. A %r conversion specification specifies a CORD argument. Field */
337 /* width, precision, etc. have the same semantics as for %s. */
338 /* (Note that %c, %C, and %S were already taken.) */
339 /* 2. The format string is represented as a CORD. */
340 /* 3. CORD_sprintf and CORD_vsprintf assign the result through the 1st */
341 /* argument. Unlike their ANSI C versions, there is no need to */
342 /* guess the correct buffer size. */
343 /* 4. Most of the conversions are implement through the native */
344 /* vsprintf. Hence they are usually no faster, and */
345 /* idiosyncrasies of the native printf are preserved. However, */
346 /* CORD arguments to CORD_sprintf and CORD_vsprintf are NOT copied; */
347 /* the result shares the original structure. This may make them */
348 /* very efficient in some unusual applications. */
349 /* The format string is copied. */
350 /* All functions return the number of characters generated or -1 on */
351 /* error. This complies with the ANSI standard, but is inconsistent */
352 /* with some older implementations of sprintf. */
353
354 /* The implementation of these is probably less portable than the rest */
355 /* of this package. */
356
357 #ifndef CORD_NO_IO
358
359 #include <stdarg.h>
360
361 # ifdef __cplusplus
362 extern "C" {
363 # endif
364
365 CORD_API int CORD_sprintf(CORD * out, CORD format, ...);
366 CORD_API int CORD_vsprintf(CORD * out, CORD format, va_list args);
367 CORD_API int CORD_fprintf(FILE * f, CORD format, ...);
368 CORD_API int CORD_vfprintf(FILE * f, CORD format, va_list args);
369 CORD_API int CORD_printf(CORD format, ...);
370 CORD_API int CORD_vprintf(CORD format, va_list args);
371
372 # ifdef __cplusplus
373 } /* extern "C" */
374 # endif
375
376 #endif /* CORD_NO_IO */
377
378 #endif /* CORD_H */