Annotation of parser3/src/lib/sdbm/sdbm_pair.c, revision 1.3
1.1 paf 1: /* ====================================================================
2: * The Apache Software License, Version 1.1
3: *
4: * Copyright (c) 2000-2002 The Apache Software Foundation. All rights
5: * reserved.
6: *
7: * Redistribution and use in source and binary forms, with or without
8: * modification, are permitted provided that the following conditions
9: * are met:
10: *
11: * 1. Redistributions of source code must retain the above copyright
12: * notice, this list of conditions and the following disclaimer.
13: *
14: * 2. Redistributions in binary form must reproduce the above copyright
15: * notice, this list of conditions and the following disclaimer in
16: * the documentation and/or other materials provided with the
17: * distribution.
18: *
19: * 3. The end-user documentation included with the redistribution,
20: * if any, must include the following acknowledgment:
21: * "This product includes software developed by the
22: * Apache Software Foundation (http://www.apache.org/)."
23: * Alternately, this acknowledgment may appear in the software itself,
24: * if and wherever such third-party acknowledgments normally appear.
25: *
26: * 4. The names "Apache" and "Apache Software Foundation" must
27: * not be used to endorse or promote products derived from this
28: * software without prior written permission. For written
29: * permission, please contact apache@apache.org.
30: *
31: * 5. Products derived from this software may not be called "Apache",
32: * nor may "Apache" appear in their name, without prior written
33: * permission of the Apache Software Foundation.
34: *
35: * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
36: * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
37: * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
38: * DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
39: * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
40: * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
41: * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
42: * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
43: * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
44: * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
45: * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
46: * SUCH DAMAGE.
47: * ====================================================================
48: *
49: * This software consists of voluntary contributions made by many
50: * individuals on behalf of the Apache Software Foundation. For more
51: * information on the Apache Software Foundation, please see
52: * <http://www.apache.org/>.
53: */
54:
55: /*
56: * sdbm - ndbm work-alike hashed database library
57: * based on Per-Aake Larson's Dynamic Hashing algorithms. BIT 18 (1978).
58: * author: oz@nexus.yorku.ca
59: * status: ex-public domain.
60: *
61: * page-level routines
62: */
63:
1.2 moko 64: #include "pa_sdbm.h"
1.1 paf 65:
66: #include "sdbm_tune.h"
67: #include "sdbm_pair.h"
68: #include "sdbm_private.h"
69:
70: #define exhash(item) sdbm_hash((item).dptr, (item).dsize)
71:
72: /*
73: * forward
74: */
75: static int seepair(char *, int, char *, int);
76:
77: /*
78: * page format:
79: * +------------------------------+
80: * ino | n | keyoff | datoff | keyoff |
81: * +------------+--------+--------+
82: * | datoff | - - - ----> |
83: * +--------+---------------------+
84: * | F R E E A R E A |
85: * +--------------+---------------+
86: * | <---- - - - | data |
87: * +--------+-----+----+----------+
88: * | key | data | key |
89: * +--------+----------+----------+
90: *
91: * calculating the offsets for free area: if the number
92: * of entries (ino[0]) is zero, the offset to the END of
93: * the free area is the block size. Otherwise, it is the
94: * nth (ino[ino[0]]) entry's offset.
95: */
96:
97: int
98: fitpair(pag, need)
99: char *pag;
100: int need;
101: {
102: register int n;
103: register int off;
104: register int avail;
105: register short *ino = (short *) pag;
106:
107: off = ((n = ino[0]) > 0) ? ino[n] : PBLKSIZ;
108: avail = off - (n + 1) * sizeof(short);
109: need += 2 * sizeof(short);
110:
111: debug(("avail %d need %d\n", avail, need));
112:
113: return need <= avail;
114: }
115:
116: void
117: putpair(pag, key, val)
118: char *pag;
1.2 moko 119: pa_sdbm_datum_t key;
120: pa_sdbm_datum_t val;
1.1 paf 121: {
122: register int n;
123: register int off;
124: register short *ino = (short *) pag;
125:
126: off = ((n = ino[0]) > 0) ? ino[n] : PBLKSIZ;
127: /*
128: * enter the key first
129: */
130: off -= key.dsize;
131: (void) memcpy(pag + off, key.dptr, key.dsize);
132: ino[n + 1] = off;
133: /*
134: * now the data
135: */
136: off -= val.dsize;
137: (void) memcpy(pag + off, val.dptr, val.dsize);
138: ino[n + 2] = off;
139: /*
140: * adjust item count
141: */
142: ino[0] += 2;
143: }
144:
1.2 moko 145: pa_sdbm_datum_t
1.1 paf 146: getpair(pag, key)
147: char *pag;
1.2 moko 148: pa_sdbm_datum_t key;
1.1 paf 149: {
150: register int i;
151: register int n;
1.2 moko 152: pa_sdbm_datum_t val;
1.1 paf 153: register short *ino = (short *) pag;
154:
155: if ((n = ino[0]) == 0)
156: return sdbm_nullitem;
157:
158: if ((i = seepair(pag, n, key.dptr, key.dsize)) == 0)
159: return sdbm_nullitem;
160:
161: val.dptr = pag + ino[i + 1];
162: val.dsize = ino[i] - ino[i + 1];
163: return val;
164: }
165:
166: int
167: duppair(pag, key)
168: char *pag;
1.2 moko 169: pa_sdbm_datum_t key;
1.1 paf 170: {
171: register short *ino = (short *) pag;
172: return ino[0] > 0 && seepair(pag, ino[0], key.dptr, key.dsize) > 0;
173: }
174:
1.2 moko 175: pa_sdbm_datum_t
1.1 paf 176: getnkey(pag, num)
177: char *pag;
178: int num;
179: {
1.2 moko 180: pa_sdbm_datum_t key;
1.1 paf 181: register int off;
182: register short *ino = (short *) pag;
183:
184: num = num * 2 - 1;
185: if (ino[0] == 0 || num > ino[0])
186: return sdbm_nullitem;
187:
188: off = (num > 1) ? ino[num - 1] : PBLKSIZ;
189:
190: key.dptr = pag + ino[num];
191: key.dsize = off - ino[num];
192:
193: return key;
194: }
195:
196: int
197: delpair(pag, key)
198: char *pag;
1.2 moko 199: pa_sdbm_datum_t key;
1.1 paf 200: {
201: register int n;
202: register int i;
203: register short *ino = (short *) pag;
204:
205: if ((n = ino[0]) == 0)
206: return 0;
207:
208: if ((i = seepair(pag, n, key.dptr, key.dsize)) == 0)
209: return 0;
210: /*
211: * found the key. if it is the last entry
212: * [i.e. i == n - 1] we just adjust the entry count.
213: * hard case: move all data down onto the deleted pair,
214: * shift offsets onto deleted offsets, and adjust them.
215: * [note: 0 < i < n]
216: */
217: if (i < n - 1) {
218: register int m;
219: register char *dst = pag + (i == 1 ? PBLKSIZ : ino[i - 1]);
220: register char *src = pag + ino[i + 1];
221: register int zoo = dst - src;
222:
223: debug(("free-up %d ", zoo));
224: /*
225: * shift data/keys down
226: */
227: m = ino[i + 1] - ino[n];
228:
229: #undef DUFF /* just use memmove. it should be plenty fast. */
230: #ifdef DUFF
231: #define MOVB *--dst = *--src
232:
233: if (m > 0) {
234: register int loop = (m + 8 - 1) >> 3;
235:
236: switch (m & (8 - 1)) {
237: case 0: do {
238: MOVB; case 7: MOVB;
239: case 6: MOVB; case 5: MOVB;
240: case 4: MOVB; case 3: MOVB;
241: case 2: MOVB; case 1: MOVB;
242: } while (--loop);
243: }
244: }
245: #else
246: dst -= m;
247: src -= m;
248: memmove(dst, src, m);
249: #endif
250:
251: /*
252: * adjust offset index up
253: */
254: while (i < n - 1) {
255: ino[i] = ino[i + 2] + zoo;
256: i++;
257: }
258: }
259: ino[0] -= 2;
260: return 1;
261: }
262:
263: /*
264: * search for the key in the page.
265: * return offset index in the range 0 < i < n.
266: * return 0 if not found.
267: */
268: static int
269: seepair(pag, n, key, siz)
270: char *pag;
271: register int n;
272: register char *key;
273: register int siz;
274: {
275: register int i;
276: register int off = PBLKSIZ;
277: register short *ino = (short *) pag;
278:
279: for (i = 1; i < n; i += 2) {
280: if (siz == off - ino[i] &&
281: memcmp(key, pag + ino[i], siz) == 0)
282: return i;
283: off = ino[i + 1];
284: }
285: return 0;
286: }
287:
288: void
289: splpage(pag, new, sbit)
290: char *pag;
291: char *new;
292: long sbit;
293: {
1.2 moko 294: pa_sdbm_datum_t key;
295: pa_sdbm_datum_t val;
1.1 paf 296:
297: register int n;
298: register int off = PBLKSIZ;
299: char cur[PBLKSIZ];
300: register short *ino = (short *) cur;
301:
302: (void) memcpy(cur, pag, PBLKSIZ);
303: (void) memset(pag, 0, PBLKSIZ);
304: (void) memset(new, 0, PBLKSIZ);
305:
306: n = ino[0];
307: for (ino++; n > 0; ino += 2) {
308: key.dptr = cur + ino[0];
309: key.dsize = off - ino[0];
310: val.dptr = cur + ino[1];
311: val.dsize = ino[0] - ino[1];
312: /*
313: * select the page pointer (by looking at sbit) and insert
314: */
315: (void) putpair((exhash(key) & sbit) ? new : pag, key, val);
316:
317: off = ino[1];
318: n -= 2;
319: }
320:
321: debug(("%d split %d/%d\n", ((short *) cur)[0] / 2,
322: ((short *) new)[0] / 2,
323: ((short *) pag)[0] / 2));
324: }
325:
326: /*
327: * check page sanity:
328: * number of entries should be something
329: * reasonable, and all offsets in the index should be in order.
330: * this could be made more rigorous.
331: */
332: int
333: chkpage(pag)
334: char *pag;
335: {
336: register int n;
337: register int off;
338: register short *ino = (short *) pag;
339:
340: if ((n = ino[0]) < 0 || n > PBLKSIZ / sizeof(short))
341: return 0;
342:
343: if (n > 0) {
344: off = PBLKSIZ;
345: for (ino++; n > 0; ino += 2) {
346: if (ino[0] > off || ino[1] > off ||
347: ino[1] > ino[0])
348: return 0;
349: off = ino[1];
350: n -= 2;
351: }
352: }
353: return 1;
354: }
E-mail:
![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to sdbm_pair.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [parser3project] / parser3 / src / lib / sdbm