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