Commit | Line | Data |
---|---|---|
463ee0b2 LW |
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" |
d308986b | 11 | #ifdef __CYGWIN__ |
8736538c AS |
12 | # define EXTCONST extern const |
13 | #else | |
14 | # include "EXTERN.h" | |
15 | #endif | |
463ee0b2 LW |
16 | #include "sdbm.h" |
17 | #include "tune.h" | |
18 | #include "pair.h" | |
19 | ||
463ee0b2 LW |
20 | #define exhash(item) sdbm_hash((item).dptr, (item).dsize) |
21 | ||
22 | /* | |
23 | * forward | |
24 | */ | |
d3f5e399 | 25 | static int seepair proto((char *, int, const char *, int)); |
463ee0b2 LW |
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 | |
f0f333f4 | 48 | fitpair(char *pag, int need) |
463ee0b2 | 49 | { |
5aaab254 KW |
50 | int n; |
51 | int off; | |
52 | int free; | |
53 | short *ino = (short *) pag; | |
463ee0b2 LW |
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 | |
f0f333f4 | 65 | putpair(char *pag, datum key, datum val) |
463ee0b2 | 66 | { |
5aaab254 KW |
67 | int n; |
68 | int off; | |
69 | short *ino = (short *) pag; | |
463ee0b2 LW |
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 | |
f0f333f4 | 91 | getpair(char *pag, datum key) |
463ee0b2 | 92 | { |
5aaab254 KW |
93 | int i; |
94 | int n; | |
463ee0b2 | 95 | datum val; |
5aaab254 | 96 | short *ino = (short *) pag; |
463ee0b2 LW |
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 | ||
f4b9d880 RA |
109 | int |
110 | exipair(char *pag, datum key) | |
111 | { | |
5aaab254 | 112 | short *ino = (short *) pag; |
f4b9d880 RA |
113 | |
114 | if (ino[0] == 0) | |
115 | return 0; | |
116 | ||
117 | return (seepair(pag, ino[0], key.dptr, key.dsize) != 0); | |
118 | } | |
119 | ||
463ee0b2 LW |
120 | #ifdef SEEDUPS |
121 | int | |
f0f333f4 | 122 | duppair(char *pag, datum key) |
463ee0b2 | 123 | { |
5aaab254 | 124 | short *ino = (short *) pag; |
463ee0b2 LW |
125 | return ino[0] > 0 && seepair(pag, ino[0], key.dptr, key.dsize) > 0; |
126 | } | |
127 | #endif | |
128 | ||
129 | datum | |
f0f333f4 | 130 | getnkey(char *pag, int num) |
463ee0b2 LW |
131 | { |
132 | datum key; | |
5aaab254 KW |
133 | int off; |
134 | short *ino = (short *) pag; | |
463ee0b2 LW |
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 | |
f0f333f4 | 149 | delpair(char *pag, datum key) |
463ee0b2 | 150 | { |
5aaab254 KW |
151 | int n; |
152 | int i; | |
153 | short *ino = (short *) pag; | |
463ee0b2 LW |
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) { | |
5aaab254 KW |
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; | |
463ee0b2 LW |
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) { | |
5aaab254 | 182 | int loop = (m + 8 - 1) >> 3; |
463ee0b2 LW |
183 | |
184 | switch (m & (8 - 1)) { | |
185 | case 0: do { | |
186 | MOVB; case 7: MOVB; | |
187 | case 6: MOVB; case 5: MOVB; | |
188 | case 4: MOVB; case 3: MOVB; | |
189 | case 2: MOVB; case 1: MOVB; | |
190 | } while (--loop); | |
191 | } | |
192 | } | |
193 | #else | |
85e6fe83 | 194 | #ifdef HAS_MEMMOVE |
a0d0e21e LW |
195 | dst -= m; |
196 | src -= m; | |
463ee0b2 LW |
197 | memmove(dst, src, m); |
198 | #else | |
199 | while (m--) | |
200 | *--dst = *--src; | |
201 | #endif | |
202 | #endif | |
203 | /* | |
204 | * adjust offset index up | |
205 | */ | |
206 | while (i < n - 1) { | |
207 | ino[i] = ino[i + 2] + zoo; | |
208 | i++; | |
209 | } | |
210 | } | |
211 | ino[0] -= 2; | |
212 | return 1; | |
213 | } | |
214 | ||
215 | /* | |
216 | * search for the key in the page. | |
217 | * return offset index in the range 0 < i < n. | |
218 | * return 0 if not found. | |
219 | */ | |
220 | static int | |
5aaab254 | 221 | seepair(char *pag, int n, const char *key, int siz) |
463ee0b2 | 222 | { |
5aaab254 KW |
223 | int i; |
224 | int off = PBLKSIZ; | |
225 | short *ino = (short *) pag; | |
463ee0b2 LW |
226 | |
227 | for (i = 1; i < n; i += 2) { | |
228 | if (siz == off - ino[i] && | |
36477c24 | 229 | memEQ(key, pag + ino[i], siz)) |
463ee0b2 LW |
230 | return i; |
231 | off = ino[i + 1]; | |
232 | } | |
233 | return 0; | |
234 | } | |
235 | ||
236 | void | |
f0f333f4 | 237 | splpage(char *pag, char *New, long int sbit) |
463ee0b2 LW |
238 | { |
239 | datum key; | |
240 | datum val; | |
241 | ||
5aaab254 KW |
242 | int n; |
243 | int off = PBLKSIZ; | |
463ee0b2 | 244 | char cur[PBLKSIZ]; |
5aaab254 | 245 | short *ino = (short *) cur; |
463ee0b2 LW |
246 | |
247 | (void) memcpy(cur, pag, PBLKSIZ); | |
248 | (void) memset(pag, 0, PBLKSIZ); | |
f0f333f4 | 249 | (void) memset(New, 0, PBLKSIZ); |
463ee0b2 LW |
250 | |
251 | n = ino[0]; | |
252 | for (ino++; n > 0; ino += 2) { | |
253 | key.dptr = cur + ino[0]; | |
254 | key.dsize = off - ino[0]; | |
255 | val.dptr = cur + ino[1]; | |
256 | val.dsize = ino[0] - ino[1]; | |
257 | /* | |
258 | * select the page pointer (by looking at sbit) and insert | |
259 | */ | |
f0f333f4 | 260 | (void) putpair((exhash(key) & sbit) ? New : pag, key, val); |
463ee0b2 LW |
261 | |
262 | off = ino[1]; | |
263 | n -= 2; | |
264 | } | |
265 | ||
266 | debug(("%d split %d/%d\n", ((short *) cur)[0] / 2, | |
f0f333f4 | 267 | ((short *) New)[0] / 2, |
463ee0b2 LW |
268 | ((short *) pag)[0] / 2)); |
269 | } | |
270 | ||
271 | /* | |
272 | * check page sanity: | |
273 | * number of entries should be something | |
274 | * reasonable, and all offsets in the index should be in order. | |
275 | * this could be made more rigorous. | |
276 | */ | |
277 | int | |
f0f333f4 | 278 | chkpage(char *pag) |
463ee0b2 | 279 | { |
5aaab254 KW |
280 | int n; |
281 | int off; | |
282 | short *ino = (short *) pag; | |
463ee0b2 | 283 | |
c33e8be1 | 284 | if ((n = ino[0]) < 0 || n > (int)(PBLKSIZ / sizeof(short))) |
463ee0b2 LW |
285 | return 0; |
286 | ||
287 | if (n > 0) { | |
288 | off = PBLKSIZ; | |
289 | for (ino++; n > 0; ino += 2) { | |
290 | if (ino[0] > off || ino[1] > off || | |
291 | ino[1] > ino[0]) | |
292 | return 0; | |
293 | off = ino[1]; | |
294 | n -= 2; | |
295 | } | |
296 | } | |
297 | return 1; | |
298 | } |