Annotation of win32/development/msvcee/cord/cordbscs.cpp, revision 1.1
1.1 ! 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 3, 1994 5:19 pm PDT */
! 16: # include "cord.h"
! 17: # include <stdlib.h>
! 18: # include <stdio.h>
! 19: # include <string.h>
! 20:
! 21: /* An implementation of the cord primitives. These are the only */
! 22: /* Functions that understand the representation. We perform only */
! 23: /* minimal checks on arguments to these functions. Out of bounds */
! 24: /* arguments to the iteration functions may result in client functions */
! 25: /* invoked on garbage data. In most cases, client functions should be */
! 26: /* programmed defensively enough that this does not result in memory */
! 27: /* smashes. */
! 28:
! 29: #define GC_NEW(s) 0
! 30: #define GC_MALLOC_ATOMIC(s) 0
! 31:
! 32: typedef void (* oom_fn)(void);
! 33:
! 34: oom_fn CORD_oom_fn = (oom_fn) 0;
! 35:
! 36: # define OUT_OF_MEMORY { if (CORD_oom_fn != (oom_fn) 0) (*CORD_oom_fn)(); \
! 37: ABORT("Out of memory\n"); }
! 38: # define ABORT(msg) { fprintf(stderr, "%s\n", msg); abort(); }
! 39:
! 40: typedef unsigned long word;
! 41:
! 42: typedef union {
! 43: struct Concatenation {
! 44: char null;
! 45: char header;
! 46: char depth; /* concatenation nesting depth. */
! 47: unsigned char left_len;
! 48: /* Length of left child if it is sufficiently */
! 49: /* short; 0 otherwise. */
! 50: # define MAX_LEFT_LEN 255
! 51: word len;
! 52: CORD left; /* length(left) > 0 */
! 53: CORD right; /* length(right) > 0 */
! 54: } concatenation;
! 55: struct Function {
! 56: char null;
! 57: char header;
! 58: char depth; /* always 0 */
! 59: char left_len; /* always 0 */
! 60: word len;
! 61: CORD_fn fn;
! 62: void * client_data;
! 63: } function;
! 64: struct Generic {
! 65: char null;
! 66: char header;
! 67: char depth;
! 68: char left_len;
! 69: word len;
! 70: } generic;
! 71: char string[1];
! 72: } CordRep;
! 73:
! 74: # define CONCAT_HDR 1
! 75:
! 76: # define FN_HDR 4
! 77: # define SUBSTR_HDR 6
! 78: /* Substring nodes are a special case of function nodes. */
! 79: /* The client_data field is known to point to a substr_args */
! 80: /* structure, and the function is either CORD_apply_access_fn */
! 81: /* or CORD_index_access_fn. */
! 82:
! 83: /* The following may be applied only to function and concatenation nodes: */
! 84: #define IS_CONCATENATION(s) (((CordRep *)s)->generic.header == CONCAT_HDR)
! 85:
! 86: #define IS_FUNCTION(s) ((((CordRep *)s)->generic.header & FN_HDR) != 0)
! 87:
! 88: #define IS_SUBSTR(s) (((CordRep *)s)->generic.header == SUBSTR_HDR)
! 89:
! 90: #define LEN(s) (((CordRep *)s) -> generic.len)
! 91: #define DEPTH(s) (((CordRep *)s) -> generic.depth)
! 92: #define GEN_LEN(s) (CORD_IS_STRING(s) ? strlen(s) : LEN(s))
! 93:
! 94: #define LEFT_LEN(c) ((c) -> left_len != 0? \
! 95: (c) -> left_len \
! 96: : (CORD_IS_STRING(D((c) -> left)) ? \
! 97: (c) -> len - GEN_LEN(D((c) -> right)) \
! 98: : LEN(D((c) -> left))))
! 99:
! 100: #define SHORT_LIMIT (sizeof(CordRep) - 1)
! 101: /* Cords shorter than this are C strings */
! 102:
! 103: /* paf: using knowledge of interal structure to speedup */
! 104: char CORD_nul_func(size_t i, void * client_data);
! 105:
! 106: size_t CORD_len(CORD x)
! 107: {
! 108: if (x == 0) {
! 109: return(0);
! 110: } else {
! 111: return(GEN_LEN(x));
! 112: }
! 113: }
! 114:
! 115: struct substr_args {
! 116: CordRep * sa_cord;
! 117: size_t sa_index;
! 118: };
! 119:
! 120: char CORD_index_access_fn(size_t i, void * client_data)
! 121: {
! 122: register struct substr_args *descr = (struct substr_args *)client_data;
! 123:
! 124: return(((char *)(descr->sa_cord))[i + descr->sa_index]);
! 125: }
! 126:
! 127: char CORD_apply_access_fn(size_t i, void * client_data)
! 128: {
! 129: register struct substr_args *descr = (struct substr_args *)client_data;
! 130: register CordRep::Function * fn_cord = &(descr->sa_cord->function);
! 131:
! 132: return((*(fn_cord->fn))(i + descr->sa_index, fn_cord->client_data));
! 133: }
! 134:
! 135:
! 136: # define SUBSTR_LIMIT (10 * SHORT_LIMIT)
! 137: /* Substrings of function nodes and flat strings shorter than */
! 138: /* this are flat strings. Othewise we use a functional */
! 139: /* representation, which is significantly slower to access. */
! 140:
! 141:
! 142: /* See cord.h for definition. We assume i is in range. */
! 143: int CORD_iter5(DEBUGHELPER *pHelper, CORD x, size_t i, CORD_iter_fn f1,
! 144: CORD_batched_iter_fn f2, void * client_data)
! 145: {
! 146: int result;
! 147: if (x == 0) return(0);
! 148: if (CORD_IS_STRING(x)) {
! 149: register const char* p = x+i;
! 150:
! 151: if (*p == '\0') ABORT("2nd arg to CORD_iter5 too big");
! 152: if (f2 != CORD_NO_FN) {
! 153: return((*f2)(p, client_data));
! 154: } else {
! 155: while (*p) {
! 156: if (result=(*f1)(*p, client_data))
! 157: return result;
! 158: p++;
! 159: }
! 160: return(0);
! 161: }
! 162: } else if (IS_CONCATENATION(x)) {
! 163: register CordRep::Concatenation * conc = &(((CordRep *)x) -> concatenation);
! 164: if (i > 0) {
! 165: register size_t left_len = LEFT_LEN(conc);
! 166:
! 167: if (i >= left_len) {
! 168: return(CORD_iter5(pHelper, D(conc -> right), i - left_len, f1, f2,
! 169: client_data));
! 170: }
! 171: }
! 172: result=CORD_iter5(pHelper, D(conc -> left), i, f1, f2, client_data);
! 173: if (result) return result;
! 174: return(CORD_iter5(pHelper, D(conc -> right), 0, f1, f2, client_data));
! 175: } else /* function */ {
! 176: register CordRep::Function * f = &(((CordRep *)x) -> function);
! 177: register size_t j;
! 178: register size_t lim = f -> len;
! 179:
! 180: for (j = i; j < lim; j++) {
! 181: if (result=(*f1)((*(f -> fn))(j, f -> client_data), client_data))
! 182: return result;
! 183: }
! 184: return(0);
! 185: }
! 186: }
E-mail:
![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to cordbscs.cpp CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [parser3project] / win32 / development / msvcee / cord