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
11static char rcsid[] = "$Id: pair.c,v 1.3 2006/09/27 08:12:40 neumann Exp $";
12#endif
13
14#include "sdbm.h"
15#include "tune.h"
16#include "pair.h"
17
18#include <stdlib.h>
19#include <string.h>
20
21#define exhash(item)	sdbm_hash((item).dptr, (item).dsize)
22
23/*
24 * forward
25 */
26static int seepair proto((char *, int, char *, size_t));
27
28/*
29 * page format:
30 *	+------------------------------+
31 * ino	| n | keyoff | datoff | keyoff |
32 * 	+------------+--------+--------+
33 *	| datoff | - - - ---->	       |
34 *	+--------+---------------------+
35 *	|	 F R E E A R E A       |
36 *	+--------------+---------------+
37 *	|  <---- - - - | data          |
38 *	+--------+-----+----+----------+
39 *	|  key   | data     | key      |
40 *	+--------+----------+----------+
41 *
42 * calculating the offsets for free area:  if the number
43 * of entries (ino[0]) is zero, the offset to the END of
44 * the free area is the block size. Otherwise, it is the
45 * nth (ino[ino[0]]) entry's offset.
46 */
47
48int
49fitpair(pag, need)
50char *pag;
51int need;
52{
53	register int n;
54	register int off;
55	register int free_space;
56	/* this cast "increases the alignment". Its not the only one, though.*/
57	register short *ino = (short *) pag;
58
59	off = ((n = ino[0]) > 0) ? ino[n] : PBLKSIZ;
60	free_space = off - (n + 1) * sizeof(short);
61	need += 2 * sizeof(short);
62
63	debug(("free %d need %d\n", free_space, need));
64
65	return need <= free_space;
66}
67
68void
69putpair(pag, key, val)
70char *pag;
71datum key;
72datum 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
97datum
98getpair(pag, key)
99char *pag;
100datum 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
119int
120duppair(pag, key)
121char *pag;
122datum 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
129datum
130getnkey(pag, num)
131char *pag;
132int 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
150int
151delpair(pag, key)
152char *pag;
153datum 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 */
222static int
223seepair(pag, n, key, siz)
224char *pag;
225register int n;
226register char *key;
227register size_t 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 ((int)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
242void
243splpage(pag, new, sbit)
244char *pag;
245char *new;
246long 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 */
286int
287chkpage(pag)
288char *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}
309