Annotation of parser3/src/lib/sdbm/sdbm_pair.c, revision 1.4
1.4 ! moko 1: /* Copyright 2000-2005 The Apache Software Foundation or its licensors, as
! 2: * applicable.
1.1 paf 3: *
1.4 ! moko 4: * Licensed under the Apache License, Version 2.0 (the "License");
! 5: * you may not use this file except in compliance with the License.
! 6: * 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.
1.1 paf 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:
1.2 moko 26: #include "pa_sdbm.h"
1.1 paf 27:
28: #include "sdbm_tune.h"
29: #include "sdbm_pair.h"
30: #include "sdbm_private.h"
31:
32: #define exhash(item) sdbm_hash((item).dptr, (item).dsize)
33:
34: /*
35: * forward
36: */
37: static int seepair(char *, int, char *, int);
38:
39: /*
40: * page format:
41: * +------------------------------+
42: * ino | n | keyoff | datoff | keyoff |
43: * +------------+--------+--------+
44: * | datoff | - - - ----> |
45: * +--------+---------------------+
46: * | F R E E A R E A |
47: * +--------------+---------------+
48: * | <---- - - - | data |
49: * +--------+-----+----+----------+
50: * | key | data | key |
51: * +--------+----------+----------+
52: *
53: * calculating the offsets for free area: if the number
54: * of entries (ino[0]) is zero, the offset to the END of
55: * the free area is the block size. Otherwise, it is the
56: * nth (ino[ino[0]]) entry's offset.
57: */
58:
59: int
60: fitpair(pag, need)
61: char *pag;
62: int need;
63: {
64: register int n;
65: register int off;
66: register int avail;
67: register short *ino = (short *) pag;
68:
69: off = ((n = ino[0]) > 0) ? ino[n] : PBLKSIZ;
70: avail = off - (n + 1) * sizeof(short);
71: need += 2 * sizeof(short);
72:
73: debug(("avail %d need %d\n", avail, need));
74:
75: return need <= avail;
76: }
77:
78: void
79: putpair(pag, key, val)
80: char *pag;
1.2 moko 81: pa_sdbm_datum_t key;
82: pa_sdbm_datum_t val;
1.1 paf 83: {
84: register int n;
85: register int off;
86: register short *ino = (short *) pag;
87:
88: off = ((n = ino[0]) > 0) ? ino[n] : PBLKSIZ;
89: /*
90: * enter the key first
91: */
92: off -= key.dsize;
93: (void) memcpy(pag + off, key.dptr, key.dsize);
94: ino[n + 1] = off;
95: /*
96: * now the data
97: */
98: off -= val.dsize;
99: (void) memcpy(pag + off, val.dptr, val.dsize);
100: ino[n + 2] = off;
101: /*
102: * adjust item count
103: */
104: ino[0] += 2;
105: }
106:
1.2 moko 107: pa_sdbm_datum_t
1.1 paf 108: getpair(pag, key)
109: char *pag;
1.2 moko 110: pa_sdbm_datum_t key;
1.1 paf 111: {
112: register int i;
113: register int n;
1.2 moko 114: pa_sdbm_datum_t val;
1.1 paf 115: register short *ino = (short *) pag;
116:
117: if ((n = ino[0]) == 0)
118: return sdbm_nullitem;
119:
120: if ((i = seepair(pag, n, key.dptr, key.dsize)) == 0)
121: return sdbm_nullitem;
122:
123: val.dptr = pag + ino[i + 1];
124: val.dsize = ino[i] - ino[i + 1];
125: return val;
126: }
127:
128: int
129: duppair(pag, key)
130: char *pag;
1.2 moko 131: pa_sdbm_datum_t key;
1.1 paf 132: {
133: register short *ino = (short *) pag;
134: return ino[0] > 0 && seepair(pag, ino[0], key.dptr, key.dsize) > 0;
135: }
136:
1.2 moko 137: pa_sdbm_datum_t
1.1 paf 138: getnkey(pag, num)
139: char *pag;
140: int num;
141: {
1.2 moko 142: pa_sdbm_datum_t key;
1.1 paf 143: register int off;
144: register short *ino = (short *) pag;
145:
146: num = num * 2 - 1;
147: if (ino[0] == 0 || num > ino[0])
148: return sdbm_nullitem;
149:
150: off = (num > 1) ? ino[num - 1] : PBLKSIZ;
151:
152: key.dptr = pag + ino[num];
153: key.dsize = off - ino[num];
154:
155: return key;
156: }
157:
158: int
159: delpair(pag, key)
160: char *pag;
1.2 moko 161: pa_sdbm_datum_t key;
1.1 paf 162: {
163: register int n;
164: register int i;
165: register short *ino = (short *) pag;
166:
167: if ((n = ino[0]) == 0)
168: return 0;
169:
170: if ((i = seepair(pag, n, key.dptr, key.dsize)) == 0)
171: return 0;
172: /*
173: * found the key. if it is the last entry
174: * [i.e. i == n - 1] we just adjust the entry count.
175: * hard case: move all data down onto the deleted pair,
176: * shift offsets onto deleted offsets, and adjust them.
177: * [note: 0 < i < n]
178: */
179: if (i < n - 1) {
180: register int m;
181: register char *dst = pag + (i == 1 ? PBLKSIZ : ino[i - 1]);
182: register char *src = pag + ino[i + 1];
183: register int zoo = dst - src;
184:
185: debug(("free-up %d ", zoo));
186: /*
187: * shift data/keys down
188: */
189: m = ino[i + 1] - ino[n];
190:
191: #undef DUFF /* just use memmove. it should be plenty fast. */
192: #ifdef DUFF
193: #define MOVB *--dst = *--src
194:
195: if (m > 0) {
196: register int loop = (m + 8 - 1) >> 3;
197:
198: switch (m & (8 - 1)) {
199: case 0: do {
200: MOVB; case 7: MOVB;
201: case 6: MOVB; case 5: MOVB;
202: case 4: MOVB; case 3: MOVB;
203: case 2: MOVB; case 1: MOVB;
204: } while (--loop);
205: }
206: }
207: #else
208: dst -= m;
209: src -= m;
210: memmove(dst, src, m);
211: #endif
212:
213: /*
214: * adjust offset index up
215: */
216: while (i < n - 1) {
217: ino[i] = ino[i + 2] + zoo;
218: i++;
219: }
220: }
221: ino[0] -= 2;
222: return 1;
223: }
224:
225: /*
226: * search for the key in the page.
227: * return offset index in the range 0 < i < n.
228: * return 0 if not found.
229: */
230: static int
231: seepair(pag, n, key, siz)
232: char *pag;
233: register int n;
234: register char *key;
235: register int siz;
236: {
237: register int i;
238: register int off = PBLKSIZ;
239: register short *ino = (short *) pag;
240:
241: for (i = 1; i < n; i += 2) {
242: if (siz == off - ino[i] &&
243: memcmp(key, pag + ino[i], siz) == 0)
244: return i;
245: off = ino[i + 1];
246: }
247: return 0;
248: }
249:
250: void
251: splpage(pag, new, sbit)
252: char *pag;
253: char *new;
254: long sbit;
255: {
1.2 moko 256: pa_sdbm_datum_t key;
257: pa_sdbm_datum_t val;
1.1 paf 258:
259: register int n;
260: register int off = PBLKSIZ;
261: char cur[PBLKSIZ];
262: register short *ino = (short *) cur;
263:
264: (void) memcpy(cur, pag, PBLKSIZ);
265: (void) memset(pag, 0, PBLKSIZ);
266: (void) memset(new, 0, PBLKSIZ);
267:
268: n = ino[0];
269: for (ino++; n > 0; ino += 2) {
270: key.dptr = cur + ino[0];
271: key.dsize = off - ino[0];
272: val.dptr = cur + ino[1];
273: val.dsize = ino[0] - ino[1];
274: /*
275: * select the page pointer (by looking at sbit) and insert
276: */
277: (void) putpair((exhash(key) & sbit) ? new : pag, key, val);
278:
279: off = ino[1];
280: n -= 2;
281: }
282:
283: debug(("%d split %d/%d\n", ((short *) cur)[0] / 2,
284: ((short *) new)[0] / 2,
285: ((short *) pag)[0] / 2));
286: }
287:
288: /*
289: * check page sanity:
290: * number of entries should be something
291: * reasonable, and all offsets in the index should be in order.
292: * this could be made more rigorous.
293: */
294: int
295: chkpage(pag)
296: char *pag;
297: {
298: register int n;
299: register int off;
300: register short *ino = (short *) pag;
301:
302: if ((n = ino[0]) < 0 || n > PBLKSIZ / sizeof(short))
303: return 0;
304:
305: if (n > 0) {
306: off = PBLKSIZ;
307: for (ino++; n > 0; ino += 2) {
308: if (ino[0] > off || ino[1] > off ||
309: ino[1] > ino[0])
310: return 0;
311: off = ino[1];
312: n -= 2;
313: }
314: }
315: return 1;
316: }
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