2 * sdbm - ndbm work-alike hashed database library
3 * based on Per-Aake Larson's Dynamic Hashing algorithms. BIT 18 (1978).
4 * author: oz@nexus.yorku.ca
5 * status: public domain.
16 #define exhash(item) sdbm_hash((item).dptr, (item).dsize)
21 static int seepair proto((char *, int, char *, int));
25 * +------------------------------+
26 * ino | n | keyoff | datoff | keyoff |
27 * +------------+--------+--------+
28 * | datoff | - - - ----> |
29 * +--------+---------------------+
31 * +--------------+---------------+
32 * | <---- - - - | data |
33 * +--------+-----+----+----------+
34 * | key | data | key |
35 * +--------+----------+----------+
37 * calculating the offsets for free area: if the number
38 * of entries (ino[0]) is zero, the offset to the END of
39 * the free area is the block size. Otherwise, it is the
40 * nth (ino[ino[0]]) entry's offset.
44 fitpair(char *pag, int need)
49 register short *ino = (short *) pag;
51 off = ((n = ino[0]) > 0) ? ino[n] : PBLKSIZ;
52 free = off - (n + 1) * sizeof(short);
53 need += 2 * sizeof(short);
55 debug(("free %d need %d\n", free, need));
61 putpair(char *pag, datum key, datum val)
65 register short *ino = (short *) pag;
67 off = ((n = ino[0]) > 0) ? ino[n] : PBLKSIZ;
72 (void) memcpy(pag + off, key.dptr, key.dsize);
78 (void) memcpy(pag + off, val.dptr, val.dsize);
87 getpair(char *pag, datum key)
92 register short *ino = (short *) pag;
94 if ((n = ino[0]) == 0)
97 if ((i = seepair(pag, n, key.dptr, key.dsize)) == 0)
100 val.dptr = pag + ino[i + 1];
101 val.dsize = ino[i] - ino[i + 1];
106 exipair(char *pag, datum key)
108 register short *ino = (short *) pag;
113 return (seepair(pag, ino[0], key.dptr, key.dsize) != 0);
118 duppair(char *pag, datum key)
120 register short *ino = (short *) pag;
121 return ino[0] > 0 && seepair(pag, ino[0], key.dptr, key.dsize) > 0;
126 getnkey(char *pag, int num)
130 register short *ino = (short *) pag;
133 if (ino[0] == 0 || num > ino[0])
136 off = (num > 1) ? ino[num - 1] : PBLKSIZ;
138 key.dptr = pag + ino[num];
139 key.dsize = off - ino[num];
145 delpair(char *pag, datum key)
149 register short *ino = (short *) pag;
151 if ((n = ino[0]) == 0)
154 if ((i = seepair(pag, n, key.dptr, key.dsize)) == 0)
157 * found the key. if it is the last entry
158 * [i.e. i == n - 1] we just adjust the entry count.
159 * hard case: move all data down onto the deleted pair,
160 * shift offsets onto deleted offsets, and adjust them.
165 register char *dst = pag + (i == 1 ? PBLKSIZ : ino[i - 1]);
166 register char *src = pag + ino[i + 1];
167 register int zoo = dst - src;
169 debug(("free-up %d ", zoo));
171 * shift data/keys down
173 m = ino[i + 1] - ino[n];
175 #define MOVB *--dst = *--src
178 register int loop = (m + 8 - 1) >> 3;
180 switch (m & (8 - 1)) {
183 case 6: MOVB; case 5: MOVB;
184 case 4: MOVB; case 3: MOVB;
185 case 2: MOVB; case 1: MOVB;
193 memmove(dst, src, m);
200 * adjust offset index up
203 ino[i] = ino[i + 2] + zoo;
212 * search for the key in the page.
213 * return offset index in the range 0 < i < n.
214 * return 0 if not found.
217 seepair(char *pag, register int n, register char *key, register int siz)
220 register int off = PBLKSIZ;
221 register short *ino = (short *) pag;
223 for (i = 1; i < n; i += 2) {
224 if (siz == off - ino[i] &&
225 memEQ(key, pag + ino[i], siz))
233 splpage(char *pag, char *New, long int sbit)
239 register int off = PBLKSIZ;
241 register short *ino = (short *) cur;
243 (void) memcpy(cur, pag, PBLKSIZ);
244 (void) memset(pag, 0, PBLKSIZ);
245 (void) memset(New, 0, PBLKSIZ);
248 for (ino++; n > 0; ino += 2) {
249 key.dptr = cur + ino[0];
250 key.dsize = off - ino[0];
251 val.dptr = cur + ino[1];
252 val.dsize = ino[0] - ino[1];
254 * select the page pointer (by looking at sbit) and insert
256 (void) putpair((exhash(key) & sbit) ? New : pag, key, val);
262 debug(("%d split %d/%d\n", ((short *) cur)[0] / 2,
263 ((short *) New)[0] / 2,
264 ((short *) pag)[0] / 2));
269 * number of entries should be something
270 * reasonable, and all offsets in the index should be in order.
271 * this could be made more rigorous.
278 register short *ino = (short *) pag;
280 if ((n = ino[0]) < 0 || n > PBLKSIZ / sizeof(short))
285 for (ino++; n > 0; ino += 2) {
286 if (ino[0] > off || ino[1] > off ||