1 /*
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.
6 *
7 * page-level routines
8 */
9
10 #include "config.h"
11 #ifdef __CYGWIN__
12 # define EXTCONST extern const
13 #else
14 # include "EXTERN.h"
15 #endif
16 #include "sdbm.h"
17 #include "tune.h"
18 #include "pair.h"
19
20 #define exhash(item) sdbm_hash((item).dptr, (item).dsize)
21
22 /*
23 * forward
24 */
25 static int seepair(char *, int, const char *, int);
26
27 /*
28 * page format:
29 * +------------------------------+
30 * ino | n | keyoff | datoff | keyoff |
31 * +------------+--------+--------+
32 * | datoff | - - - ----> |
33 * +--------+---------------------+
34 * | F R E E A R E A |
35 * +--------------+---------------+
36 * | <---- - - - | data |
37 * +--------+-----+----+----------+
38 * | key | data | key |
39 * +--------+----------+----------+
40 *
41 * calculating the offsets for free area: if the number
42 * of entries (ino[0]) is zero, the offset to the END of
43 * the free area is the block size. Otherwise, it is the
44 * nth (ino[ino[0]]) entry's offset.
45 */
46
47 int
fitpair(char * pag,int need)48 fitpair(char *pag, int need)
49 {
50 int n;
51 int off;
52 int free;
53 short *ino = (short *) pag;
54
55 off = ((n = ino[0]) > 0) ? ino[n] : PBLKSIZ;
56 free = off - (n + 1) * sizeof(short);
57 need += 2 * sizeof(short);
58
59 debug(("free %d need %d\n", free, need));
60
61 return need <= free;
62 }
63
64 void
putpair(char * pag,datum key,datum val)65 putpair(char *pag, datum key, datum val)
66 {
67 int n;
68 int off;
69 short *ino = (short *) pag;
70
71 off = ((n = ino[0]) > 0) ? ino[n] : PBLKSIZ;
72 /*
73 * enter the key first
74 */
75 off -= key.dsize;
76 (void) memcpy(pag + off, key.dptr, key.dsize);
77 ino[n + 1] = off;
78 /*
79 * now the data
80 */
81 off -= val.dsize;
82 (void) memcpy(pag + off, val.dptr, val.dsize);
83 ino[n + 2] = off;
84 /*
85 * adjust item count
86 */
87 ino[0] += 2;
88 }
89
90 datum
getpair(char * pag,datum key)91 getpair(char *pag, datum key)
92 {
93 int i;
94 int n;
95 datum val;
96 short *ino = (short *) pag;
97
98 if ((n = ino[0]) == 0)
99 return nullitem;
100
101 if ((i = seepair(pag, n, key.dptr, key.dsize)) == 0)
102 return nullitem;
103
104 val.dptr = pag + ino[i + 1];
105 val.dsize = ino[i] - ino[i + 1];
106 return val;
107 }
108
109 int
exipair(char * pag,datum key)110 exipair(char *pag, datum key)
111 {
112 short *ino = (short *) pag;
113
114 if (ino[0] == 0)
115 return 0;
116
117 return (seepair(pag, ino[0], key.dptr, key.dsize) != 0);
118 }
119
120 #ifdef SEEDUPS
121 int
duppair(char * pag,datum key)122 duppair(char *pag, datum key)
123 {
124 short *ino = (short *) pag;
125 return ino[0] > 0 && seepair(pag, ino[0], key.dptr, key.dsize) > 0;
126 }
127 #endif
128
129 datum
getnkey(char * pag,int num)130 getnkey(char *pag, int num)
131 {
132 datum key;
133 int off;
134 short *ino = (short *) pag;
135
136 num = num * 2 - 1;
137 if (ino[0] == 0 || num > ino[0])
138 return nullitem;
139
140 off = (num > 1) ? ino[num - 1] : PBLKSIZ;
141
142 key.dptr = pag + ino[num];
143 key.dsize = off - ino[num];
144
145 return key;
146 }
147
148 int
delpair(char * pag,datum key)149 delpair(char *pag, datum key)
150 {
151 int n;
152 int i;
153 short *ino = (short *) pag;
154
155 if ((n = ino[0]) == 0)
156 return 0;
157
158 if ((i = seepair(pag, n, key.dptr, key.dsize)) == 0)
159 return 0;
160 /*
161 * found the key. if it is the last entry
162 * [i.e. i == n - 1] we just adjust the entry count.
163 * hard case: move all data down onto the deleted pair,
164 * shift offsets onto deleted offsets, and adjust them.
165 * [note: 0 < i < n]
166 */
167 if (i < n - 1) {
168 int m;
169 char *dst = pag + (i == 1 ? PBLKSIZ : ino[i - 1]);
170 char *src = pag + ino[i + 1];
171 int zoo = dst - src;
172
173 debug(("free-up %d ", zoo));
174 /*
175 * shift data/keys down
176 */
177 m = ino[i + 1] - ino[n];
178 #ifdef DUFF
179 #define MOVB *--dst = *--src
180
181 if (m > 0) {
182 int loop = (m + 8 - 1) >> 3;
183
184 switch (m & (8 - 1)) {
185 case 0: do {
186 MOVB; /* FALLTHROUGH */ case 7: MOVB; /* FALLTHROUGH */
187 case 6: MOVB; /* FALLTHROUGH */ case 5: MOVB; /* FALLTHROUGH */
188 case 4: MOVB; /* FALLTHROUGH */ case 3: MOVB; /* FALLTHROUGH */
189 case 2: MOVB; /* FALLTHROUGH */ case 1: MOVB;
190 } while (--loop);
191 }
192 }
193 #else
194 dst -= m;
195 src -= m;
196 memmove(dst, src, m);
197 #endif
198 /*
199 * adjust offset index up
200 */
201 while (i < n - 1) {
202 ino[i] = ino[i + 2] + zoo;
203 i++;
204 }
205 }
206 ino[0] -= 2;
207 return 1;
208 }
209
210 /*
211 * search for the key in the page.
212 * return offset index in the range 0 < i < n.
213 * return 0 if not found.
214 */
215 static int
seepair(char * pag,int n,const char * key,int siz)216 seepair(char *pag, int n, const char *key, int siz)
217 {
218 int i;
219 int off = PBLKSIZ;
220 short *ino = (short *) pag;
221
222 for (i = 1; i < n; i += 2) {
223 if (siz == off - ino[i] &&
224 memEQ(key, pag + ino[i], siz))
225 return i;
226 off = ino[i + 1];
227 }
228 return 0;
229 }
230
231 void
splpage(char * pag,char * New,long int sbit)232 splpage(char *pag, char *New, long int sbit)
233 {
234 datum key;
235 datum val;
236
237 int n;
238 int off = PBLKSIZ;
239 char cur[PBLKSIZ];
240 short *ino = (short *) cur;
241
242 (void) memcpy(cur, pag, PBLKSIZ);
243 (void) memset(pag, 0, PBLKSIZ);
244 (void) memset(New, 0, PBLKSIZ);
245
246 n = ino[0];
247 for (ino++; n > 0; ino += 2) {
248 key.dptr = cur + ino[0];
249 key.dsize = off - ino[0];
250 val.dptr = cur + ino[1];
251 val.dsize = ino[0] - ino[1];
252 /*
253 * select the page pointer (by looking at sbit) and insert
254 */
255 (void) putpair((exhash(key) & sbit) ? New : pag, key, val);
256
257 off = ino[1];
258 n -= 2;
259 }
260
261 debug(("%d split %d/%d\n", ((short *) cur)[0] / 2,
262 ((short *) New)[0] / 2,
263 ((short *) pag)[0] / 2));
264 }
265
266 /*
267 * check page sanity:
268 * number of entries should be something
269 * reasonable, and all offsets in the index should be in order.
270 * this could be made more rigorous.
271 */
272 /*
273 Layout of a page is:
274 Top of block:
275 number of keys/values (short)
276 Array of (number of keys/values) offsets, alternating between key offsets
277 and value offsets (shorts)
278 End of block:
279 - value/key data, last key ends at end of block (bytes)
280
281 So:
282 N key0off val0off key1off val1off ... val1 key1 val0 key0
283
284 Be careful to note N is the number of offsets, *not* the number of keys.
285 */
286 int
chkpage(char * pag)287 chkpage(char *pag)
288 {
289 int n;
290 int off;
291 short *ino = (short *) pag;
292
293 if ((n = ino[0]) < 0 || n > (int)(PBLKSIZ / sizeof(short)))
294 return 0;
295
296 if (n > 0) {
297 off = PBLKSIZ;
298 for (ino++; n > 0; ino += 2) {
299 if (ino[0] > off || ino[1] > off ||
300 ino[1] > ino[0] || ino[1] <= 0)
301 return 0;
302 off = ino[1];
303 n -= 2;
304 }
305 /* there must be an even number of offsets */
306 if (n != 0)
307 return 0;
308 /* check the key/value offsets don't overlap the key/value data */
309 if ((char *)ino > pag + off)
310 return 0;
311 }
312 return 1;
313 }
314