![[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.