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#include "config.h"
11#ifdef __CYGWIN__
12# define EXTCONST extern const
13#else
14# include "EXTERN.h"
15#endif
16#include "sdbm.h"
17#include "tune.h"
18#include "pair.h"
19
20#define exhash(item)    sdbm_hash((item).dptr, (item).dsize)
21
22/*
23 * forward
24 */
25static int seepair(char *, int, const char *, int);
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
47int
48fitpair(char *pag, int need)
49{
50        int n;
51        int off;
52        int free;
53        short *ino = (short *) pag;
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
64void
65putpair(char *pag, datum key, datum val)
66{
67        int n;
68        int off;
69        short *ino = (short *) pag;
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
90datum
91getpair(char *pag, datum key)
92{
93        int i;
94        int n;
95        datum val;
96        short *ino = (short *) pag;
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
109int
110exipair(char *pag, datum key)
111{
112        short *ino = (short *) pag;
113
114        if (ino[0] == 0)
115                return 0;
116
117        return (seepair(pag, ino[0], key.dptr, key.dsize) != 0);
118}
119
120#ifdef SEEDUPS
121int
122duppair(char *pag, datum key)
123{
124        short *ino = (short *) pag;
125        return ino[0] > 0 && seepair(pag, ino[0], key.dptr, key.dsize) > 0;
126}
127#endif
128
129datum
130getnkey(char *pag, int num)
131{
132        datum key;
133        int off;
134        short *ino = (short *) pag;
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
148int
149delpair(char *pag, datum key)
150{
151        int n;
152        int i;
153        short *ino = (short *) pag;
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) {
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;
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) {
182                        int loop = (m + 8 - 1) >> 3;
183
184                        switch (m & (8 - 1)) {
185                        case 0: do {
186                                MOVB; /* FALLTHROUGH */ case 7: MOVB; /* FALLTHROUGH */
187                        case 6: MOVB; /* FALLTHROUGH */ case 5: MOVB; /* FALLTHROUGH */
188                        case 4: MOVB; /* FALLTHROUGH */ case 3: MOVB; /* FALLTHROUGH */
189                        case 2: MOVB; /* FALLTHROUGH */ case 1: MOVB;
190                                } while (--loop);
191                        }
192                }
193#else
194                dst -= m;
195                src -= m;
196                memmove(dst, src, m);
197#endif
198/*
199 * adjust offset index up
200 */
201                while (i < n - 1) {
202                        ino[i] = ino[i + 2] + zoo;
203                        i++;
204                }
205        }
206        ino[0] -= 2;
207        return 1;
208}
209
210/*
211 * search for the key in the page.
212 * return offset index in the range 0 < i < n.
213 * return 0 if not found.
214 */
215static int
216seepair(char *pag, int n, const char *key, int siz)
217{
218        int i;
219        int off = PBLKSIZ;
220        short *ino = (short *) pag;
221
222        for (i = 1; i < n; i += 2) {
223                if (siz == off - ino[i] &&
224                    memEQ(key, pag + ino[i], siz))
225                        return i;
226                off = ino[i + 1];
227        }
228        return 0;
229}
230
231void
232splpage(char *pag, char *New, long int sbit)
233{
234        datum key;
235        datum val;
236
237        int n;
238        int off = PBLKSIZ;
239        char cur[PBLKSIZ];
240        short *ino = (short *) cur;
241
242        (void) memcpy(cur, pag, PBLKSIZ);
243        (void) memset(pag, 0, PBLKSIZ);
244        (void) memset(New, 0, PBLKSIZ);
245
246        n = ino[0];
247        for (ino++; n > 0; ino += 2) {
248                key.dptr = cur + ino[0];
249                key.dsize = off - ino[0];
250                val.dptr = cur + ino[1];
251                val.dsize = ino[0] - ino[1];
252/*
253 * select the page pointer (by looking at sbit) and insert
254 */
255                (void) putpair((exhash(key) & sbit) ? New : pag, key, val);
256
257                off = ino[1];
258                n -= 2;
259        }
260
261        debug(("%d split %d/%d\n", ((short *) cur)[0] / 2,
262               ((short *) New)[0] / 2,
263               ((short *) pag)[0] / 2));
264}
265
266/*
267 * check page sanity:
268 * number of entries should be something
269 * reasonable, and all offsets in the index should be in order.
270 * this could be made more rigorous.
271 */
272/*
273  Layout of a page is:
274  Top of block:
275  number of keys/values (short)
276  Array of (number of keys/values) offsets, alternating between key offsets
277  and value offsets (shorts)
278  End of block:
279   - value/key data, last key ends at end of block (bytes)
280
281  So:
282    N key0off val0off key1off val1off ... val1 key1 val0 key0
283
284  Be careful to note N is the number of offsets, *not* the number of keys.
285 */
286int
287chkpage(char *pag)
288{
289        int n;
290        int off;
291        short *ino = (short *) pag;
292
293        if ((n = ino[0]) < 0 || n > (int)(PBLKSIZ / sizeof(short)))
294                return 0;
295
296        if (n > 0) {
297                off = PBLKSIZ;
298                for (ino++; n > 0; ino += 2) {
299                        if (ino[0] > off || ino[1] > off ||
300                            ino[1] > ino[0] || ino[1] <= 0)
301                                return 0;
302                        off = ino[1];
303                        n -= 2;
304                }
305                /* there must be an even number of offsets */
306                if (n != 0)
307                    return 0;
308                /* check the key/value offsets don't overlap the key/value data */
309                if ((char *)ino > pag + off)
310                    return 0;
311        }
312        return 1;
313}
314