![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to hashing.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Research Unix] / researchv10no / cmd / visi|
Return to hashing.c CVS log | Up to [Research Unix] / researchv10no / cmd / visi |
1.1 root 1: /*
2: * hashing.c 1.3
3: *
4: * Hashing Functions for Spreadsheet Program `vis'
5: *
6: * A. F. Gettier
7: * Bell Laboratories
8: * Update made 11/1/82 11:11:37
9: * Retrieved 11/15/82 13:22:21
10: */
11: #include <stdio.h>
12: #include "vis.h"
13: #include "y.tab.h"
14:
15: struct hashhdr htbl;
16:
17: static struct reswd reswd[]={
18: "PI", PI,
19: "ABS", ABS,
20: "ACOS", ACOS,
21: "ASIN", ASIN,
22: "AT", AT,
23: "ATAN", ATAN,
24: "ATAN2", ATAN2,
25: "COS", COS,
26: "EXP", EXP,
27: "GAMMA", GAMMA,
28: "HYPOT", HYPOT,
29: "INT", INT,
30: "LOG", LOG,
31: "POW", POW,
32: "SIN", SIN,
33: "SQRT", SQRT,
34: "COL", COL,
35: "COPY", COPY,
36: "DEBUG", DEBUG,
37: "DOWN", DOWN,
38: "DUP", DUP,
39: "DUPLICATE", DUPLICATE,
40: "EDIT", EDIT,
41: "HELP", HELP,
42: "LEFT", LEFT,
43: "LIST", LIST,
44: "POSITION", POSITION,
45: "READ", READ,
46: "REDRAW", REDRAW,
47: "REFRESH", REFRESH,
48: "REP", REP,
49: "REPLICATE", REPLICATE,
50: "RIGHT", RIGHT,
51: "ROW", ROW,
52: "SCALE", SCALE,
53: "SHIFT", SHIFT,
54: "SLIDE", SLIDE,
55: "SHELL", SHELL,
56: "SH", SH,
57: "THRU", THRU,
58: "UP", UP,
59: "VER", VER,
60: "WIDTH", WIDTH,
61: "WRITE", WRITE,
62: "ZERO", ZERO,
63: "QUIT", QUIT,
64: 0, 0 };
65:
66: /*
67: * Init a hash table
68: */
69: void hashinit()
70: {
71: int i;
72: int size;
73: struct hashentry *tbl;
74: size = 63; /* default hash table size */
75: htbl.size = size;
76: tbl = htbl.table = multnode( hashentry, size );
77: for ( i=0; i<size; i++ ) (tbl++)->symbol = 0;
78: /*
79: * enter all the keywords
80: */
81: for( i=0; reswd[i].name!=0; i++ )
82: hashenter( reswd[i].name, reswd[i].value );
83: }
84:
85: /*
86: * Search a hash table
87: */
88: hashsearch( symbol )
89: char *symbol;
90: {
91: int key, mkey;
92: struct hashentry *tbl, *start;
93: key = makekey( symbol );
94: mkey = key%(htbl.size - 1);
95: start = tbl = htbl.table + mkey;
96: do {
97: if ( tbl->symbol == 0 ) return( 0 );
98: if ( tbl->symbol != (char *)(-1) && tbl->key == key
99: && strcmp( symbol, tbl->symbol ) == 0 )
100: return(tbl->value);
101: tbl++;
102: if ( tbl >= (htbl.table + htbl.size ) ) tbl = htbl.table;
103: } while ( tbl != start );
104: return( 0 );
105: }
106:
107: /*
108: * Enter into a hash table
109: */
110: void hashenter( symbol, value )
111: char *symbol;
112: int value;
113: {
114: int key, mkey;
115: float a, b;
116: struct hashentry *tbl;
117: a = htbl.size;
118: b = htbl.entry;
119: /*
120: * First try to clean up the table
121: */
122: if ( b/a > .65 ) hashclean( );
123: /*
124: * Now expand
125: */
126: b = htbl.entry;
127: if ( b/a > .65 ) hashexpand( );
128: key = makekey( symbol );
129: mkey = key%(htbl.size - 1);
130: tbl = htbl.table;
131: tbl += mkey;
132: loop {
133: if ( tbl->symbol == 0 || tbl->symbol == (char *)(-1)) {
134: tbl->key = key;
135: tbl->symbol = symbol;
136: (htbl.entry)++;
137: tbl->value = value;
138: return;
139: }
140: if ( tbl->key == key && strcmp( symbol, tbl->symbol ) == 0 ) {
141: tbl->value = value;
142: return;
143: }
144: tbl++;
145: if ( tbl >= (htbl.table + htbl.size ) ) tbl = htbl.table;
146: }
147: }
148:
149: /*
150: * Make the key
151: */
152: static makekey( symbol )
153: char *symbol;
154: {
155: int key, i;
156: key = 0;
157: i = 8;
158: while (*symbol != 0) {
159: key += *symbol + ((*symbol)<<8) + ((*symbol)<<(i++));
160: symbol++;
161: }
162: return( ((key<0)?(-key):(key)) );
163: }
164:
165: /*
166: * Expand the Hash Table
167: */
168: static hashexpand( )
169: {
170: int i, mkey, size;
171: struct hashentry *tbl, *temp, *tbl2;
172: size = htbl.size * 2 + 1;
173: tbl = temp = multnode( hashentry, size );
174: for ( i=0; i<size; i++ ) (temp++)->symbol = 0;
175: tbl2 = htbl.table;
176: for ( i=0; i<htbl.size; i++ ) {
177: if ( tbl2->symbol == 0 || tbl2->symbol == (char *)(-1)) {
178: tbl2++;
179: continue;
180: }
181: mkey = (tbl2->key)%(size - 1);
182: temp = tbl;
183: temp += mkey;
184: loop {
185: if ( temp->symbol == 0 ) {
186: temp->key = tbl2->key;
187: temp->symbol = tbl2->symbol;
188: temp->value = tbl2->value;
189: tbl2++;
190: break;
191: }
192: temp++;
193: if ( temp >= ( tbl+ size ) ) temp = tbl;
194: }
195: }
196: free( (char *)htbl.table );
197: htbl.size = size;
198: htbl.table = tbl;
199: }
200:
201: /*
202: * Clean up the Hash Table
203: */
204: static hashclean( )
205: {
206: int i, mkey, size, entry;
207: struct hashentry *tbl, *temp, *tbl2;
208: size = htbl.size;
209: tbl = temp = multnode( hashentry, size );
210: for ( i=0; i<size; i++ ) (temp++)->symbol = 0;
211: entry = 0;
212: tbl2 = htbl.table;
213: for ( i=0; i<htbl.size; i++ ) {
214: if ( tbl2->symbol == 0 || tbl2->symbol == (char *)(-1)) {
215: tbl2++;
216: continue;
217: }
218: mkey = (tbl2->key)%(size - 1);
219: temp = tbl;
220: temp += mkey;
221: loop {
222: if ( temp->symbol == 0 ) {
223: temp->key = tbl2->key;
224: temp->symbol = tbl2->symbol;
225: temp->value = tbl2->value;
226: tbl2++;
227: entry++;
228: break;
229: }
230: temp++;
231: if ( temp >= ( tbl+ size ) ) temp = tbl;
232: }
233: }
234: free( (char *)htbl.table );
235: htbl.entry = entry;
236: htbl.table = tbl;
237: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.