Annotation of parser3/src/lib/sdbm/sdbm_pair.c, revision 1.1
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:
! 64: #include "apr_sdbm.h"
! 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;
! 122: apr_sdbm_datum_t key;
! 123: apr_sdbm_datum_t val;
! 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:
! 148: apr_sdbm_datum_t
! 149: getpair(pag, key)
! 150: char *pag;
! 151: apr_sdbm_datum_t key;
! 152: {
! 153: register int i;
! 154: register int n;
! 155: apr_sdbm_datum_t val;
! 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;
! 172: apr_sdbm_datum_t key;
! 173: {
! 174: register short *ino = (short *) pag;
! 175: return ino[0] > 0 && seepair(pag, ino[0], key.dptr, key.dsize) > 0;
! 176: }
! 177:
! 178: apr_sdbm_datum_t
! 179: getnkey(pag, num)
! 180: char *pag;
! 181: int num;
! 182: {
! 183: apr_sdbm_datum_t key;
! 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;
! 202: apr_sdbm_datum_t key;
! 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: {
! 297: apr_sdbm_datum_t key;
! 298: apr_sdbm_datum_t val;
! 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