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