1 /* Licensed to the Apache Software Foundation (ASF) under one or more
2 * contributor license agreements. See the NOTICE file distributed with
3 * this work for additional information regarding copyright ownership.
4 * The ASF licenses this file to You under the Apache License, Version 2.0
5 * (the "License"); you may not use this file except in compliance with
6 * the License. You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 /*
18 * sdbm - ndbm work-alike hashed database library
19 * based on Per-Aake Larson's Dynamic Hashing algorithms. BIT 18 (1978).
20 * author: oz@nexus.yorku.ca
21 * status: ex-public domain.
22 *
23 * page-level routines
24 */
25
26 #include "apr_sdbm.h"
27
28 #include "sdbm_tune.h"
29 #include "sdbm_pair.h"
30 #include "sdbm_private.h"
31
32 #include <string.h> /* for memset() */
33
34
35 #define exhash(item) sdbm_hash((item).dptr, (item).dsize)
36
37 /*
38 * forward
39 */
40 static int seepair(char *, int, char *, int);
41
42 /*
43 * page format:
44 * +------------------------------+
45 * ino | n | keyoff | datoff | keyoff |
46 * +------------+--------+--------+
47 * | datoff | - - - ----> |
48 * +--------+---------------------+
49 * | F R E E A R E A |
50 * +--------------+---------------+
51 * | <---- - - - | data |
52 * +--------+-----+----+----------+
53 * | key | data | key |
54 * +--------+----------+----------+
55 *
56 * calculating the offsets for free area: if the number
57 * of entries (ino[0]) is zero, the offset to the END of
58 * the free area is the block size. Otherwise, it is the
59 * nth (ino[ino[0]]) entry's offset.
60 */
61
62 int
fitpair(pag,need)63 fitpair(pag, need)
64 char *pag;
65 int need;
66 {
67 register int n;
68 register int off;
69 register int avail;
70 register short *ino = (short *) pag;
71
72 off = ((n = ino[0]) > 0) ? ino[n] : PBLKSIZ;
73 avail = off - (n + 1) * sizeof(short);
74 need += 2 * sizeof(short);
75
76 debug(("avail %d need %d\n", avail, need));
77
78 return need <= avail;
79 }
80
81 void
putpair(pag,key,val)82 putpair(pag, key, val)
83 char *pag;
84 apr_sdbm_datum_t key;
85 apr_sdbm_datum_t val;
86 {
87 register int n;
88 register int off;
89 register short *ino = (short *) pag;
90
91 off = ((n = ino[0]) > 0) ? ino[n] : PBLKSIZ;
92 /*
93 * enter the key first
94 */
95 off -= key.dsize;
96 (void) memcpy(pag + off, key.dptr, key.dsize);
97 ino[n + 1] = off;
98 /*
99 * now the data
100 */
101 off -= val.dsize;
102 (void) memcpy(pag + off, val.dptr, val.dsize);
103 ino[n + 2] = off;
104 /*
105 * adjust item count
106 */
107 ino[0] += 2;
108 }
109
110 apr_sdbm_datum_t
getpair(pag,key)111 getpair(pag, key)
112 char *pag;
113 apr_sdbm_datum_t key;
114 {
115 register int i;
116 register int n;
117 apr_sdbm_datum_t val;
118 register short *ino = (short *) pag;
119
120 if ((n = ino[0]) == 0)
121 return sdbm_nullitem;
122
123 if ((i = seepair(pag, n, key.dptr, key.dsize)) == 0)
124 return sdbm_nullitem;
125
126 val.dptr = pag + ino[i + 1];
127 val.dsize = ino[i] - ino[i + 1];
128 return val;
129 }
130
131 int
duppair(pag,key)132 duppair(pag, key)
133 char *pag;
134 apr_sdbm_datum_t key;
135 {
136 register short *ino = (short *) pag;
137 return ino[0] > 0 && seepair(pag, ino[0], key.dptr, key.dsize) > 0;
138 }
139
140 apr_sdbm_datum_t
getnkey(pag,num)141 getnkey(pag, num)
142 char *pag;
143 int num;
144 {
145 apr_sdbm_datum_t key;
146 register int off;
147 register short *ino = (short *) pag;
148
149 num = num * 2 - 1;
150 if (ino[0] == 0 || num > ino[0])
151 return sdbm_nullitem;
152
153 off = (num > 1) ? ino[num - 1] : PBLKSIZ;
154
155 key.dptr = pag + ino[num];
156 key.dsize = off - ino[num];
157
158 return key;
159 }
160
161 int
delpair(pag,key)162 delpair(pag, key)
163 char *pag;
164 apr_sdbm_datum_t key;
165 {
166 register int n;
167 register int i;
168 register short *ino = (short *) pag;
169
170 if ((n = ino[0]) == 0)
171 return 0;
172
173 if ((i = seepair(pag, n, key.dptr, key.dsize)) == 0)
174 return 0;
175 /*
176 * found the key. if it is the last entry
177 * [i.e. i == n - 1] we just adjust the entry count.
178 * hard case: move all data down onto the deleted pair,
179 * shift offsets onto deleted offsets, and adjust them.
180 * [note: 0 < i < n]
181 */
182 if (i < n - 1) {
183 register int m;
184 register char *dst = pag + (i == 1 ? PBLKSIZ : ino[i - 1]);
185 register char *src = pag + ino[i + 1];
186 register short zoo = (short) (dst - src);
187
188 debug(("free-up %d ", zoo));
189 /*
190 * shift data/keys down
191 */
192 m = ino[i + 1] - ino[n];
193
194 #undef DUFF /* just use memmove. it should be plenty fast. */
195 #ifdef DUFF
196 #define MOVB *--dst = *--src
197
198 if (m > 0) {
199 register int loop = (m + 8 - 1) >> 3;
200
201 switch (m & (8 - 1)) {
202 case 0: do {
203 MOVB; case 7: MOVB;
204 case 6: MOVB; case 5: MOVB;
205 case 4: MOVB; case 3: MOVB;
206 case 2: MOVB; case 1: MOVB;
207 } while (--loop);
208 }
209 }
210 #else
211 dst -= m;
212 src -= m;
213 memmove(dst, src, m);
214 #endif
215
216 /*
217 * adjust offset index up
218 */
219 while (i < n - 1) {
220 ino[i] = ino[i + 2] + zoo;
221 i++;
222 }
223 }
224 ino[0] -= 2;
225 return 1;
226 }
227
228 /*
229 * search for the key in the page.
230 * return offset index in the range 0 < i < n.
231 * return 0 if not found.
232 */
233 static int
seepair(pag,n,key,siz)234 seepair(pag, n, key, siz)
235 char *pag;
236 register int n;
237 register char *key;
238 register int siz;
239 {
240 register int i;
241 register int off = PBLKSIZ;
242 register short *ino = (short *) pag;
243
244 for (i = 1; i < n; i += 2) {
245 if (siz == off - ino[i] &&
246 memcmp(key, pag + ino[i], siz) == 0)
247 return i;
248 off = ino[i + 1];
249 }
250 return 0;
251 }
252
253 void
splpage(pag,new,sbit)254 splpage(pag, new, sbit)
255 char *pag;
256 char *new;
257 long sbit;
258 {
259 apr_sdbm_datum_t key;
260 apr_sdbm_datum_t val;
261
262 register int n;
263 register int off = PBLKSIZ;
264 char cur[PBLKSIZ];
265 register short *ino = (short *) cur;
266
267 (void) memcpy(cur, pag, PBLKSIZ);
268 (void) memset(pag, 0, PBLKSIZ);
269 (void) memset(new, 0, PBLKSIZ);
270
271 n = ino[0];
272 for (ino++; n > 0; ino += 2) {
273 key.dptr = cur + ino[0];
274 key.dsize = off - ino[0];
275 val.dptr = cur + ino[1];
276 val.dsize = ino[0] - ino[1];
277 /*
278 * select the page pointer (by looking at sbit) and insert
279 */
280 (void) putpair((exhash(key) & sbit) ? new : pag, key, val);
281
282 off = ino[1];
283 n -= 2;
284 }
285
286 debug(("%d split %d/%d\n", ((short *) cur)[0] / 2,
287 ((short *) new)[0] / 2,
288 ((short *) pag)[0] / 2));
289 }
290
291 /*
292 * check page sanity:
293 * number of entries should be something
294 * reasonable, and all offsets in the index should be in order.
295 * this could be made more rigorous.
296 */
297 int
chkpage(pag)298 chkpage(pag)
299 char *pag;
300 {
301 register int n;
302 register int off;
303 register short *ino = (short *) pag;
304
305 if ((n = ino[0]) < 0 || n > PBLKSIZ / sizeof(short))
306 return 0;
307
308 if (n > 0) {
309 off = PBLKSIZ;
310 for (ino++; n > 0; ino += 2) {
311 if (ino[0] < 0 || ino[0] > off ||
312 ino[1] < 0 || ino[1] > off ||
313 ino[1] > ino[0])
314 return 0;
315 off = ino[1];
316 n -= 2;
317 }
318 }
319 return 1;
320 }
321