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 | |
85e6fe83 |
10 | #include "config.h" |
17f28c40 |
11 | #include "EXTERN.h" |
463ee0b2 |
12 | #include "sdbm.h" |
13 | #include "tune.h" |
14 | #include "pair.h" |
15 | |
463ee0b2 |
16 | #define exhash(item) sdbm_hash((item).dptr, (item).dsize) |
17 | |
18 | /* |
19 | * forward |
20 | */ |
21 | static int seepair proto((char *, int, char *, int)); |
22 | |
23 | /* |
24 | * page format: |
25 | * +------------------------------+ |
26 | * ino | n | keyoff | datoff | keyoff | |
27 | * +------------+--------+--------+ |
28 | * | datoff | - - - ----> | |
29 | * +--------+---------------------+ |
30 | * | F R E E A R E A | |
31 | * +--------------+---------------+ |
32 | * | <---- - - - | data | |
33 | * +--------+-----+----+----------+ |
34 | * | key | data | key | |
35 | * +--------+----------+----------+ |
36 | * |
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. |
41 | */ |
42 | |
43 | int |
f0f333f4 |
44 | fitpair(char *pag, int need) |
463ee0b2 |
45 | { |
46 | register int n; |
47 | register int off; |
48 | register int free; |
49 | register short *ino = (short *) pag; |
50 | |
51 | off = ((n = ino[0]) > 0) ? ino[n] : PBLKSIZ; |
52 | free = off - (n + 1) * sizeof(short); |
53 | need += 2 * sizeof(short); |
54 | |
55 | debug(("free %d need %d\n", free, need)); |
56 | |
57 | return need <= free; |
58 | } |
59 | |
60 | void |
f0f333f4 |
61 | putpair(char *pag, datum key, datum val) |
463ee0b2 |
62 | { |
63 | register int n; |
64 | register int off; |
65 | register short *ino = (short *) pag; |
66 | |
67 | off = ((n = ino[0]) > 0) ? ino[n] : PBLKSIZ; |
68 | /* |
69 | * enter the key first |
70 | */ |
71 | off -= key.dsize; |
72 | (void) memcpy(pag + off, key.dptr, key.dsize); |
73 | ino[n + 1] = off; |
74 | /* |
75 | * now the data |
76 | */ |
77 | off -= val.dsize; |
78 | (void) memcpy(pag + off, val.dptr, val.dsize); |
79 | ino[n + 2] = off; |
80 | /* |
81 | * adjust item count |
82 | */ |
83 | ino[0] += 2; |
84 | } |
85 | |
86 | datum |
f0f333f4 |
87 | getpair(char *pag, datum key) |
463ee0b2 |
88 | { |
89 | register int i; |
90 | register int n; |
91 | datum val; |
92 | register short *ino = (short *) pag; |
93 | |
94 | if ((n = ino[0]) == 0) |
95 | return nullitem; |
96 | |
97 | if ((i = seepair(pag, n, key.dptr, key.dsize)) == 0) |
98 | return nullitem; |
99 | |
100 | val.dptr = pag + ino[i + 1]; |
101 | val.dsize = ino[i] - ino[i + 1]; |
102 | return val; |
103 | } |
104 | |
f4b9d880 |
105 | int |
106 | exipair(char *pag, datum key) |
107 | { |
108 | register short *ino = (short *) pag; |
109 | |
110 | if (ino[0] == 0) |
111 | return 0; |
112 | |
113 | return (seepair(pag, ino[0], key.dptr, key.dsize) != 0); |
114 | } |
115 | |
463ee0b2 |
116 | #ifdef SEEDUPS |
117 | int |
f0f333f4 |
118 | duppair(char *pag, datum key) |
463ee0b2 |
119 | { |
120 | register short *ino = (short *) pag; |
121 | return ino[0] > 0 && seepair(pag, ino[0], key.dptr, key.dsize) > 0; |
122 | } |
123 | #endif |
124 | |
125 | datum |
f0f333f4 |
126 | getnkey(char *pag, int num) |
463ee0b2 |
127 | { |
128 | datum key; |
129 | register int off; |
130 | register short *ino = (short *) pag; |
131 | |
132 | num = num * 2 - 1; |
133 | if (ino[0] == 0 || num > ino[0]) |
134 | return nullitem; |
135 | |
136 | off = (num > 1) ? ino[num - 1] : PBLKSIZ; |
137 | |
138 | key.dptr = pag + ino[num]; |
139 | key.dsize = off - ino[num]; |
140 | |
141 | return key; |
142 | } |
143 | |
144 | int |
f0f333f4 |
145 | delpair(char *pag, datum key) |
463ee0b2 |
146 | { |
147 | register int n; |
148 | register int i; |
149 | register short *ino = (short *) pag; |
150 | |
151 | if ((n = ino[0]) == 0) |
152 | return 0; |
153 | |
154 | if ((i = seepair(pag, n, key.dptr, key.dsize)) == 0) |
155 | return 0; |
156 | /* |
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. |
161 | * [note: 0 < i < n] |
162 | */ |
163 | if (i < n - 1) { |
164 | register int m; |
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; |
168 | |
169 | debug(("free-up %d ", zoo)); |
170 | /* |
171 | * shift data/keys down |
172 | */ |
173 | m = ino[i + 1] - ino[n]; |
174 | #ifdef DUFF |
175 | #define MOVB *--dst = *--src |
176 | |
177 | if (m > 0) { |
178 | register int loop = (m + 8 - 1) >> 3; |
179 | |
180 | switch (m & (8 - 1)) { |
181 | case 0: do { |
182 | MOVB; case 7: MOVB; |
183 | case 6: MOVB; case 5: MOVB; |
184 | case 4: MOVB; case 3: MOVB; |
185 | case 2: MOVB; case 1: MOVB; |
186 | } while (--loop); |
187 | } |
188 | } |
189 | #else |
85e6fe83 |
190 | #ifdef HAS_MEMMOVE |
a0d0e21e |
191 | dst -= m; |
192 | src -= m; |
463ee0b2 |
193 | memmove(dst, src, m); |
194 | #else |
195 | while (m--) |
196 | *--dst = *--src; |
197 | #endif |
198 | #endif |
199 | /* |
200 | * adjust offset index up |
201 | */ |
202 | while (i < n - 1) { |
203 | ino[i] = ino[i + 2] + zoo; |
204 | i++; |
205 | } |
206 | } |
207 | ino[0] -= 2; |
208 | return 1; |
209 | } |
210 | |
211 | /* |
212 | * search for the key in the page. |
213 | * return offset index in the range 0 < i < n. |
214 | * return 0 if not found. |
215 | */ |
216 | static int |
f0f333f4 |
217 | seepair(char *pag, register int n, register char *key, register int siz) |
463ee0b2 |
218 | { |
219 | register int i; |
220 | register int off = PBLKSIZ; |
221 | register short *ino = (short *) pag; |
222 | |
223 | for (i = 1; i < n; i += 2) { |
224 | if (siz == off - ino[i] && |
36477c24 |
225 | memEQ(key, pag + ino[i], siz)) |
463ee0b2 |
226 | return i; |
227 | off = ino[i + 1]; |
228 | } |
229 | return 0; |
230 | } |
231 | |
232 | void |
f0f333f4 |
233 | splpage(char *pag, char *New, long int sbit) |
463ee0b2 |
234 | { |
235 | datum key; |
236 | datum val; |
237 | |
238 | register int n; |
239 | register int off = PBLKSIZ; |
240 | char cur[PBLKSIZ]; |
241 | register short *ino = (short *) cur; |
242 | |
243 | (void) memcpy(cur, pag, PBLKSIZ); |
244 | (void) memset(pag, 0, PBLKSIZ); |
f0f333f4 |
245 | (void) memset(New, 0, PBLKSIZ); |
463ee0b2 |
246 | |
247 | n = ino[0]; |
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]; |
253 | /* |
254 | * select the page pointer (by looking at sbit) and insert |
255 | */ |
f0f333f4 |
256 | (void) putpair((exhash(key) & sbit) ? New : pag, key, val); |
463ee0b2 |
257 | |
258 | off = ino[1]; |
259 | n -= 2; |
260 | } |
261 | |
262 | debug(("%d split %d/%d\n", ((short *) cur)[0] / 2, |
f0f333f4 |
263 | ((short *) New)[0] / 2, |
463ee0b2 |
264 | ((short *) pag)[0] / 2)); |
265 | } |
266 | |
267 | /* |
268 | * check page sanity: |
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. |
272 | */ |
273 | int |
f0f333f4 |
274 | chkpage(char *pag) |
463ee0b2 |
275 | { |
276 | register int n; |
277 | register int off; |
278 | register short *ino = (short *) pag; |
279 | |
280 | if ((n = ino[0]) < 0 || n > PBLKSIZ / sizeof(short)) |
281 | return 0; |
282 | |
283 | if (n > 0) { |
284 | off = PBLKSIZ; |
285 | for (ino++; n > 0; ino += 2) { |
286 | if (ino[0] > off || ino[1] > off || |
287 | ino[1] > ino[0]) |
288 | return 0; |
289 | off = ino[1]; |
290 | n -= 2; |
291 | } |
292 | } |
293 | return 1; |
294 | } |