/* * sdbm - ndbm work-alike hashed database library * based on Per-Aake Larson's Dynamic Hashing algorithms. BIT 18 (1978). * author: oz@nexus.yorku.ca * status: public domain. * * page-level routines */ #include "config.h" #ifdef __CYGWIN__ # define EXTCONST extern const #else # include "EXTERN.h" #endif #include "sdbm.h" #include "tune.h" #include "pair.h" #define exhash(item) sdbm_hash((item).dptr, (item).dsize) /* * forward */ static int seepair proto((char *, int, char *, int)); /* * page format: * +------------------------------+ * ino | n | keyoff | datoff | keyoff | * +------------+--------+--------+ * | datoff | - - - ----> | * +--------+---------------------+ * | F R E E A R E A | * +--------------+---------------+ * | <---- - - - | data | * +--------+-----+----+----------+ * | key | data | key | * +--------+----------+----------+ * * calculating the offsets for free area: if the number * of entries (ino[0]) is zero, the offset to the END of * the free area is the block size. Otherwise, it is the * nth (ino[ino[0]]) entry's offset. */ int fitpair(char *pag, int need) 997 { 997 register int n; 997 register int off; 997 register int free; 997 register short *ino = (short *) pag; 997 off = ((n = ino[0]) > 0) ? ino[n] : PBLKSIZ; 997 free = off - (n + 1) * sizeof(short); 997 need += 2 * sizeof(short); debug(("free %d need %d\n", free, need)); 997 return need <= free; } void putpair(char *pag, datum key, datum val) 1715 { 1715 register int n; 1715 register int off; 1715 register short *ino = (short *) pag; 1715 off = ((n = ino[0]) > 0) ? ino[n] : PBLKSIZ; /* * enter the key first */ 1715 off -= key.dsize; 1715 (void) memcpy(pag + off, key.dptr, key.dsize); 1715 ino[n + 1] = off; /* * now the data */ 1715 off -= val.dsize; 1715 (void) memcpy(pag + off, val.dptr, val.dsize); 1715 ino[n + 2] = off; /* * adjust item count */ 1715 ino[0] += 2; } datum getpair(char *pag, datum key) 1154 { 1154 register int i; 1154 register int n; 1154 datum val; 1154 register short *ino = (short *) pag; 1154 if ((n = ino[0]) == 0) ###### return nullitem; 1154 if ((i = seepair(pag, n, key.dptr, key.dsize)) == 0) 8 return nullitem; 1146 val.dptr = pag + ino[i + 1]; 1146 val.dsize = ino[i] - ino[i + 1]; 1146 return val; } int exipair(char *pag, datum key) 2 { 2 register short *ino = (short *) pag; 2 if (ino[0] == 0) ###### return 0; 2 return (seepair(pag, ino[0], key.dptr, key.dsize) != 0); } #ifdef SEEDUPS int duppair(char *pag, datum key) ###### { ###### register short *ino = (short *) pag; ###### return ino[0] > 0 && seepair(pag, ino[0], key.dptr, key.dsize) > 0; } #endif datum getnkey(char *pag, int num) 425 { 425 datum key; 425 register int off; 425 register short *ino = (short *) pag; 425 num = num * 2 - 1; 425 if (ino[0] == 0 || num > ino[0]) 41 return nullitem; 384 off = (num > 1) ? ino[num - 1] : PBLKSIZ; 384 key.dptr = pag + ino[num]; 384 key.dsize = off - ino[num]; 384 return key; } int delpair(char *pag, datum key) 997 { 997 register int n; 997 register int i; 997 register short *ino = (short *) pag; 997 if ((n = ino[0]) == 0) 29 return 0; 968 if ((i = seepair(pag, n, key.dptr, key.dsize)) == 0) 559 return 0; /* * found the key. if it is the last entry * [i.e. i == n - 1] we just adjust the entry count. * hard case: move all data down onto the deleted pair, * shift offsets onto deleted offsets, and adjust them. * [note: 0 < i < n] */ 409 if (i < n - 1) { 401 register int m; 401 register char *dst = pag + (i == 1 ? PBLKSIZ : ino[i - 1]); 401 register char *src = pag + ino[i + 1]; 401 register int zoo = dst - src; debug(("free-up %d ", zoo)); /* * shift data/keys down */ 401 m = ino[i + 1] - ino[n]; #ifdef DUFF #define MOVB *--dst = *--src 401 if (m > 0) { 401 register int loop = (m + 8 - 1) >> 3; 401 switch (m & (8 - 1)) { 14596 case 0: do { 14596 MOVB; case 7: MOVB; 14744 case 6: MOVB; case 5: MOVB; 14846 case 4: MOVB; case 3: MOVB; 14892 case 2: MOVB; case 1: MOVB; 14914 } while (--loop); } } #else #ifdef HAS_MEMMOVE dst -= m; src -= m; memmove(dst, src, m); #else while (m--) *--dst = *--src; #endif #endif /* * adjust offset index up */ 45137 while (i < n - 1) { 44736 ino[i] = ino[i + 2] + zoo; 44736 i++; } } 409 ino[0] -= 2; 409 return 1; } /* * search for the key in the page. * return offset index in the range 0 < i < n. * return 0 if not found. */ static int seepair(char *pag, register int n, register char *key, register int siz) 2124 { 2124 register int i; 2124 register int off = PBLKSIZ; 2124 register short *ino = (short *) pag; 83364 for (i = 1; i < n; i += 2) { 82796 if (siz == off - ino[i] && memEQ(key, pag + ino[i], siz)) 1556 return i; 81240 off = ino[i + 1]; } 568 return 0; } void splpage(char *pag, char *New, long int sbit) 6 { 6 datum key; 6 datum val; 6 register int n; 6 register int off = PBLKSIZ; 6 char cur[PBLKSIZ]; 6 register short *ino = (short *) cur; 6 (void) memcpy(cur, pag, PBLKSIZ); 6 (void) memset(pag, 0, PBLKSIZ); 6 (void) memset(New, 0, PBLKSIZ); 6 n = ino[0]; 730 for (ino++; n > 0; ino += 2) { 724 key.dptr = cur + ino[0]; 724 key.dsize = off - ino[0]; 724 val.dptr = cur + ino[1]; 724 val.dsize = ino[0] - ino[1]; /* * select the page pointer (by looking at sbit) and insert */ 724 (void) putpair((exhash(key) & sbit) ? New : pag, key, val); 724 off = ino[1]; 724 n -= 2; } debug(("%d split %d/%d\n", ((short *) cur)[0] / 2, ((short *) New)[0] / 2, ((short *) pag)[0] / 2)); } /* * check page sanity: * number of entries should be something * reasonable, and all offsets in the index should be in order. * this could be made more rigorous. */ int chkpage(char *pag) 1380 { 1380 register int n; 1380 register int off; 1380 register short *ino = (short *) pag; 1380 if ((n = ino[0]) < 0 || n > PBLKSIZ / sizeof(short)) ###### return 0; 1380 if (n > 0) { 1351 off = PBLKSIZ; 109022 for (ino++; n > 0; ino += 2) { 107671 if (ino[0] > off || ino[1] > off || ino[1] > ino[0]) ###### return 0; 107671 off = ino[1]; 107671 n -= 2; } } 1380 return 1; }