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 */
40static 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
62int
63fitpair(pag, need)
64char *pag;
65int 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
81void
82putpair(pag, key, val)
83char *pag;
84apr_sdbm_datum_t key;
85apr_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
110apr_sdbm_datum_t
111getpair(pag, key)
112char *pag;
113apr_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
131int
132duppair(pag, key)
133char *pag;
134apr_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
140apr_sdbm_datum_t
141getnkey(pag, num)
142char *pag;
143int 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
161int
162delpair(pag, key)
163char *pag;
164apr_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 */
233static int
234seepair(pag, n, key, siz)
235char *pag;
236register int n;
237register char *key;
238register 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
253void
254splpage(pag, new, sbit)
255char *pag;
256char *new;
257long 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 */
297int
298chkpage(pag)
299char *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