gc-7.2/include/cord.h

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