![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to turbo_load.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [CSRG BSD Unix] / 43BSDReno / contrib / isode-beta / quipu|
Return to turbo_load.c CVS log | Up to [CSRG BSD Unix] / 43BSDReno / contrib / isode-beta / quipu |
1.1 ! root 1: /* turbo_load.c - Quickly check for duplicate RDN's (from Tim Howes) */ ! 2: ! 3: #ifndef lint ! 4: static char *rcsid = "$Header: /f/osi/quipu/RCS/turbo_load.c,v 7.1 90/07/09 14:46:48 mrose Exp $"; ! 5: #endif ! 6: ! 7: /* ! 8: * $Header: /f/osi/quipu/RCS/turbo_load.c,v 7.1 90/07/09 14:46:48 mrose Exp $ ! 9: * ! 10: * ! 11: * $Log: turbo_load.c,v $ ! 12: * Revision 7.1 90/07/09 14:46:48 mrose ! 13: * sync ! 14: * ! 15: * Revision 7.0 89/11/23 22:20:57 mrose ! 16: * Release 6.0 ! 17: * ! 18: */ ! 19: ! 20: /* ! 21: * NOTICE ! 22: * ! 23: * Acquisition, use, and distribution of this module and related ! 24: * materials are subject to the restrictions of a license agreement. ! 25: * Consult the Preface in the User's Manual for the full terms of ! 26: * this agreement. ! 27: * ! 28: */ ! 29: ! 30: #include "quipu/config.h" ! 31: #include "quipu/util.h" ! 32: #include "quipu/entry.h" ! 33: #include "quipu/malloc.h" ! 34: #include <sys/stat.h> ! 35: #ifdef TURBO_DISK ! 36: #include "../../gdbm-1.3/gdbmdefs.h" ! 37: #endif ! 38: ! 39: extern LLog * log_dsap; ! 40: ! 41: extern int turbo_size; ! 42: extern int turbo_name_size; ! 43: ! 44: struct node { ! 45: char *name; ! 46: struct node *left; ! 47: struct node *right; ! 48: int bf; ! 49: }; ! 50: ! 51: static struct node *node_heap; ! 52: static struct node *node_next; ! 53: ! 54: static char *name_heap; ! 55: static char *name_next; ! 56: ! 57: static struct node *root; ! 58: static long count; ! 59: static long comparisons; ! 60: static long entries; ! 61: ! 62: turbo_start(file) ! 63: #ifdef TURBO_DISK ! 64: gdbm_file_info *file; ! 65: #else ! 66: FILE *file; ! 67: #endif ! 68: { ! 69: struct stat buf; ! 70: int save_heap; ! 71: ! 72: #ifdef TURBO_DISK ! 73: if ( fstat(file->desc, &buf) != 0 ) { ! 74: #else ! 75: if ( fstat(fileno(file), &buf) != 0 ) { ! 76: #endif ! 77: LLOG (log_dsap, LLOG_EXCEPTIONS,("turbo: could not get filesize")); ! 78: return FALSE; ! 79: } ! 80: ! 81: /* ! 82: * This is a heuristic based on some edb file sizes at ! 83: * UM. If you find this isn't enough, try using ! 84: * a smaller turbo_size (in quiputailor). This should ! 85: * eventually be fixed to malloc more if the heuristic ! 86: * turns out not to be enough. ! 87: */ ! 88: entries = (buf.st_size) / turbo_size; ! 89: if ( entries < 100 ) entries = 100; ! 90: ! 91: save_heap = mem_heap; ! 92: GENERAL_HEAP; ! 93: node_heap = (struct node *) calloc( (unsigned)entries, sizeof(struct node) ); ! 94: node_next = node_heap; ! 95: name_heap = (char *) calloc( (unsigned)entries, (unsigned)turbo_name_size ); ! 96: name_next = name_heap; ! 97: mem_heap = save_heap; ! 98: root = 0; ! 99: count = 0; ! 100: comparisons = 0; ! 101: ! 102: mem_heap = save_heap; ! 103: return TRUE; ! 104: } ! 105: ! 106: #define LH -1 ! 107: #define EH 0 ! 108: #define RH 1 ! 109: #define ROTATERIGHT(x) { struct node *tmp;\ ! 110: if ( *x == NULL || (*x)->left == NULL ) {\ ! 111: (void) printf("RR error\n"); exit(1); \ ! 112: }\ ! 113: tmp = (*x)->left;\ ! 114: (*x)->left = tmp->right;\ ! 115: tmp->right = *x;\ ! 116: *x = tmp;\ ! 117: } ! 118: #define ROTATELEFT(x) { struct node *tmp;\ ! 119: if ( *x == NULL || (*x)->right == NULL ) {\ ! 120: (void) printf("RL error\n"); exit(1); \ ! 121: }\ ! 122: tmp = (*x)->right;\ ! 123: (*x)->right = tmp->left;\ ! 124: tmp->left = *x;\ ! 125: *x = tmp;\ ! 126: } ! 127: ! 128: ! 129: static avl_insert(iroot, name, taller) ! 130: struct node **iroot; ! 131: char *name; ! 132: int *taller; ! 133: { ! 134: int rc, cmp, tallersub; ! 135: struct node *l, *r; ! 136: ! 137: comparisons++; ! 138: if ( *iroot == 0 ) { ! 139: *iroot = node_next++; ! 140: (*iroot)->left = 0; ! 141: (*iroot)->right = 0; ! 142: (*iroot)->bf = 0; ! 143: (*iroot)->name = name_next; ! 144: while ( *(name_next++) = *(name++) ); ! 145: *taller = 1; ! 146: return (OK); ! 147: } ! 148: ! 149: cmp = strcmp(name, (*iroot)->name); ! 150: /* equal - duplicate name */ ! 151: if ( cmp == 0 ) { ! 152: *taller = 0; ! 153: return (NOTOK); ! 154: } ! 155: /* go right */ ! 156: else if ( cmp > 0 ) { ! 157: rc = avl_insert(&((*iroot)->right), name, &tallersub); ! 158: if (tallersub) ! 159: switch ((*iroot)->bf) { ! 160: case LH : /* left high - balance is restored */ ! 161: (*iroot)->bf = EH; ! 162: *taller = 0; ! 163: break; ! 164: case EH : /* equal height - now right heavy */ ! 165: (*iroot)->bf = RH; ! 166: *taller = 1; ! 167: break; ! 168: case RH : /* right heavy to start - right balance */ ! 169: r = (*iroot)->right; ! 170: switch (r->bf) { ! 171: case LH : /* double rotation left */ ! 172: l = r->left; ! 173: switch (l->bf) { ! 174: case LH : (*iroot)->bf = EH; ! 175: r->bf = RH; ! 176: break; ! 177: case EH : (*iroot)->bf = EH; ! 178: r->bf = EH; ! 179: break; ! 180: case RH : (*iroot)->bf = LH; ! 181: r->bf = EH; ! 182: break; ! 183: } ! 184: l->bf = EH; ! 185: ROTATERIGHT((&r)) ! 186: (*iroot)->right = r; ! 187: ROTATELEFT(iroot) ! 188: *taller = 0; ! 189: break; ! 190: case EH : /* This should never happen */ ! 191: break; ! 192: case RH : /* single rotation left */ ! 193: (*iroot)->bf = EH; ! 194: r->bf = EH; ! 195: ROTATELEFT(iroot) ! 196: *taller = 0; ! 197: break; ! 198: } ! 199: break; ! 200: } ! 201: else ! 202: *taller = 0; ! 203: } ! 204: /* go left */ ! 205: else { ! 206: rc = avl_insert(&((*iroot)->left), name, &tallersub); ! 207: if (tallersub) ! 208: switch ((*iroot)->bf) { ! 209: case LH : /* left high to start - left balance */ ! 210: l = (*iroot)->left; ! 211: switch (l->bf) { ! 212: case LH : /* single rotation right */ ! 213: (*iroot)->bf = EH; ! 214: l->bf = EH; ! 215: ROTATERIGHT(iroot) ! 216: *taller = 0; ! 217: break; ! 218: case EH : /* this should never happen */ ! 219: break; ! 220: case RH : /* double rotation right */ ! 221: r = l->right; ! 222: switch (r->bf) { ! 223: case LH : (*iroot)->bf = RH; ! 224: l->bf = EH; ! 225: break; ! 226: case EH : (*iroot)->bf = EH; ! 227: l->bf = EH; ! 228: break; ! 229: case RH : (*iroot)->bf = EH; ! 230: l->bf = LH; ! 231: break; ! 232: } ! 233: r->bf = EH; ! 234: ROTATELEFT((&l)) ! 235: (*iroot)->left = l; ! 236: ROTATERIGHT(iroot) ! 237: *taller = 0; ! 238: break; ! 239: } ! 240: break; ! 241: case EH : /* equal height - now left heavy */ ! 242: (*iroot)->bf = LH; ! 243: *taller = 1; ! 244: break; ! 245: case RH : /* right high - balance is restored */ ! 246: (*iroot)->bf = EH; ! 247: *taller = 0; ! 248: break; ! 249: } ! 250: else ! 251: *taller = 0; ! 252: } ! 253: return(rc); ! 254: } ! 255: ! 256: turbo_insert(name) ! 257: RDN name; ! 258: { ! 259: int taller; ! 260: ! 261: if ( ++count >= entries ) { ! 262: if (count == entries) ! 263: LLOG (log_dsap,LLOG_EXCEPTIONS,("turbo botch - decrease turbo_size (currently %d - %d entries read)",turbo_size,entries)); ! 264: /* should realloc */ ! 265: return OK; ! 266: } ! 267: ! 268: if (strlen ((char *) name->rdn_av.av_struct) >= turbo_name_size) { ! 269: LLOG (log_dsap,LLOG_EXCEPTIONS,("turbo botch - increase turbo_name_size (%d required for '%s', currently %d)", ! 270: strlen ((char *) name->rdn_av.av_struct), ! 271: (char *)name->rdn_av.av_struct, turbo_name_size)); ! 272: /* should realloc */ ! 273: return OK; ! 274: } ! 275: ! 276: return (avl_insert(&root, (char *) name->rdn_av.av_struct, &taller)); ! 277: } ! 278: ! 279: turbo_end() ! 280: { ! 281: int save_heap; ! 282: ! 283: DLOG (log_dsap,LLOG_DEBUG,("turbo %d entries unused",entries - count)); ! 284: ! 285: save_heap = mem_heap; ! 286: GENERAL_HEAP; ! 287: ! 288: free(name_heap); ! 289: free((char *)node_heap); ! 290: ! 291: mem_heap = save_heap; ! 292: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.