| 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 */ |