Annotation of parser3/src/lib/sdbm/sdbm_pair.c, revision 1.2
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: #include <string.h> /* for memset() */
71:
72:
73: #define exhash(item) sdbm_hash((item).dptr, (item).dsize)
74:
75: /*
76: * forward
77: */
78: static int seepair(char *, int, char *, int);
79:
80: /*
81: * page format:
82: * +------------------------------+
83: * ino | n | keyoff | datoff | keyoff |
84: * +------------+--------+--------+
85: * | datoff | - - - ----> |
86: * +--------+---------------------+
87: * | F R E E A R E A |
88: * +--------------+---------------+
89: * | <---- - - - | data |
90: * +--------+-----+----+----------+
91: * | key | data | key |
92: * +--------+----------+----------+
93: *
94: * calculating the offsets for free area: if the number
95: * of entries (ino[0]) is zero, the offset to the END of
96: * the free area is the block size. Otherwise, it is the
97: * nth (ino[ino[0]]) entry's offset.
98: */
99:
100: int
101: fitpair(pag, need)
102: char *pag;
103: int need;
104: {
105: register int n;
106: register int off;
107: register int avail;
108: register short *ino = (short *) pag;
109:
110: off = ((n = ino[0]) > 0) ? ino[n] : PBLKSIZ;
111: avail = off - (n + 1) * sizeof(short);
112: need += 2 * sizeof(short);
113:
114: debug(("avail %d need %d\n", avail, need));
115:
116: return need <= avail;
117: }
118:
119: void
120: putpair(pag, key, val)
121: char *pag;
1.2 ! moko 122: pa_sdbm_datum_t key;
! 123: pa_sdbm_datum_t val;
1.1 paf 124: {
125: register int n;
126: register int off;
127: register short *ino = (short *) pag;
128:
129: off = ((n = ino[0]) > 0) ? ino[n] : PBLKSIZ;
130: /*
131: * enter the key first
132: */
133: off -= key.dsize;
134: (void) memcpy(pag + off, key.dptr, key.dsize);
135: ino[n + 1] = off;
136: /*
137: * now the data
138: */
139: off -= val.dsize;
140: (void) memcpy(pag + off, val.dptr, val.dsize);
141: ino[n + 2] = off;
142: /*
143: * adjust item count
144: */
145: ino[0] += 2;
146: }
147:
1.2 ! moko 148: pa_sdbm_datum_t
1.1 paf 149: getpair(pag, key)
150: char *pag;
1.2 ! moko 151: pa_sdbm_datum_t key;
1.1 paf 152: {
153: register int i;
154: register int n;
1.2 ! moko 155: pa_sdbm_datum_t val;
1.1 paf 156: register short *ino = (short *) pag;
157:
158: if ((n = ino[0]) == 0)
159: return sdbm_nullitem;
160:
161: if ((i = seepair(pag, n, key.dptr, key.dsize)) == 0)
162: return sdbm_nullitem;
163:
164: val.dptr = pag + ino[i + 1];
165: val.dsize = ino[i] - ino[i + 1];
166: return val;
167: }
168:
169: int
170: duppair(pag, key)
171: char *pag;
1.2 ! moko 172: pa_sdbm_datum_t key;
1.1 paf 173: {
174: register short *ino = (short *) pag;
175: return ino[0] > 0 && seepair(pag, ino[0], key.dptr, key.dsize) > 0;
176: }
177:
1.2 ! moko 178: pa_sdbm_datum_t
1.1 paf 179: getnkey(pag, num)
180: char *pag;
181: int num;
182: {
1.2 ! moko 183: pa_sdbm_datum_t key;
1.1 paf 184: register int off;
185: register short *ino = (short *) pag;
186:
187: num = num * 2 - 1;
188: if (ino[0] == 0 || num > ino[0])
189: return sdbm_nullitem;
190:
191: off = (num > 1) ? ino[num - 1] : PBLKSIZ;
192:
193: key.dptr = pag + ino[num];
194: key.dsize = off - ino[num];
195:
196: return key;
197: }
198:
199: int
200: delpair(pag, key)
201: char *pag;
1.2 ! moko 202: pa_sdbm_datum_t key;
1.1 paf 203: {
204: register int n;
205: register int i;
206: register short *ino = (short *) pag;
207:
208: if ((n = ino[0]) == 0)
209: return 0;
210:
211: if ((i = seepair(pag, n, key.dptr, key.dsize)) == 0)
212: return 0;
213: /*
214: * found the key. if it is the last entry
215: * [i.e. i == n - 1] we just adjust the entry count.
216: * hard case: move all data down onto the deleted pair,
217: * shift offsets onto deleted offsets, and adjust them.
218: * [note: 0 < i < n]
219: */
220: if (i < n - 1) {
221: register int m;
222: register char *dst = pag + (i == 1 ? PBLKSIZ : ino[i - 1]);
223: register char *src = pag + ino[i + 1];
224: register int zoo = dst - src;
225:
226: debug(("free-up %d ", zoo));
227: /*
228: * shift data/keys down
229: */
230: m = ino[i + 1] - ino[n];
231:
232: #undef DUFF /* just use memmove. it should be plenty fast. */
233: #ifdef DUFF
234: #define MOVB *--dst = *--src
235:
236: if (m > 0) {
237: register int loop = (m + 8 - 1) >> 3;
238:
239: switch (m & (8 - 1)) {
240: case 0: do {
241: MOVB; case 7: MOVB;
242: case 6: MOVB; case 5: MOVB;
243: case 4: MOVB; case 3: MOVB;
244: case 2: MOVB; case 1: MOVB;
245: } while (--loop);
246: }
247: }
248: #else
249: dst -= m;
250: src -= m;
251: memmove(dst, src, m);
252: #endif
253:
254: /*
255: * adjust offset index up
256: */
257: while (i < n - 1) {
258: ino[i] = ino[i + 2] + zoo;
259: i++;
260: }
261: }
262: ino[0] -= 2;
263: return 1;
264: }
265:
266: /*
267: * search for the key in the page.
268: * return offset index in the range 0 < i < n.
269: * return 0 if not found.
270: */
271: static int
272: seepair(pag, n, key, siz)
273: char *pag;
274: register int n;
275: register char *key;
276: register int siz;
277: {
278: register int i;
279: register int off = PBLKSIZ;
280: register short *ino = (short *) pag;
281:
282: for (i = 1; i < n; i += 2) {
283: if (siz == off - ino[i] &&
284: memcmp(key, pag + ino[i], siz) == 0)
285: return i;
286: off = ino[i + 1];
287: }
288: return 0;
289: }
290:
291: void
292: splpage(pag, new, sbit)
293: char *pag;
294: char *new;
295: long sbit;
296: {
1.2 ! moko 297: pa_sdbm_datum_t key;
! 298: pa_sdbm_datum_t val;
1.1 paf 299:
300: register int n;
301: register int off = PBLKSIZ;
302: char cur[PBLKSIZ];
303: register short *ino = (short *) cur;
304:
305: (void) memcpy(cur, pag, PBLKSIZ);
306: (void) memset(pag, 0, PBLKSIZ);
307: (void) memset(new, 0, PBLKSIZ);
308:
309: n = ino[0];
310: for (ino++; n > 0; ino += 2) {
311: key.dptr = cur + ino[0];
312: key.dsize = off - ino[0];
313: val.dptr = cur + ino[1];
314: val.dsize = ino[0] - ino[1];
315: /*
316: * select the page pointer (by looking at sbit) and insert
317: */
318: (void) putpair((exhash(key) & sbit) ? new : pag, key, val);
319:
320: off = ino[1];
321: n -= 2;
322: }
323:
324: debug(("%d split %d/%d\n", ((short *) cur)[0] / 2,
325: ((short *) new)[0] / 2,
326: ((short *) pag)[0] / 2));
327: }
328:
329: /*
330: * check page sanity:
331: * number of entries should be something
332: * reasonable, and all offsets in the index should be in order.
333: * this could be made more rigorous.
334: */
335: int
336: chkpage(pag)
337: char *pag;
338: {
339: register int n;
340: register int off;
341: register short *ino = (short *) pag;
342:
343: if ((n = ino[0]) < 0 || n > PBLKSIZ / sizeof(short))
344: return 0;
345:
346: if (n > 0) {
347: off = PBLKSIZ;
348: for (ino++; n > 0; ino += 2) {
349: if (ino[0] > off || ino[1] > off ||
350: ino[1] > ino[0])
351: return 0;
352: off = ino[1];
353: n -= 2;
354: }
355: }
356: return 1;
357: }
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