sdbm_pair.c revision 251886
1218065Sadrian/* Licensed to the Apache Software Foundation (ASF) under one or more 2218065Sadrian * contributor license agreements. See the NOTICE file distributed with 3240592Sadrian * this work for additional information regarding copyright ownership. 4218065Sadrian * The ASF licenses this file to You under the Apache License, Version 2.0 5218065Sadrian * (the "License"); you may not use this file except in compliance with 6218065Sadrian * the License. You may obtain a copy of the License at 7218065Sadrian * 8218065Sadrian * http://www.apache.org/licenses/LICENSE-2.0 9218065Sadrian * 10218065Sadrian * Unless required by applicable law or agreed to in writing, software 11218065Sadrian * distributed under the License is distributed on an "AS IS" BASIS, 12218065Sadrian * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13218065Sadrian * See the License for the specific language governing permissions and 14218065Sadrian * limitations under the License. 15218065Sadrian */ 16218065Sadrian 17218065Sadrian/* 18218065Sadrian * sdbm - ndbm work-alike hashed database library 19218065Sadrian * based on Per-Aake Larson's Dynamic Hashing algorithms. BIT 18 (1978). 20218065Sadrian * author: oz@nexus.yorku.ca 21218065Sadrian * status: ex-public domain. 22218065Sadrian * 23218065Sadrian * page-level routines 24218065Sadrian */ 25218065Sadrian 26218065Sadrian#include "apr_sdbm.h" 27218065Sadrian 28218065Sadrian#include "sdbm_tune.h" 29218065Sadrian#include "sdbm_pair.h" 30218065Sadrian#include "sdbm_private.h" 31218065Sadrian 32218065Sadrian#include <string.h> /* for memset() */ 33218065Sadrian 34218065Sadrian 35218065Sadrian#define exhash(item) sdbm_hash((item).dptr, (item).dsize) 36218065Sadrian 37218065Sadrian/* 38218065Sadrian * forward 39218065Sadrian */ 40218065Sadrianstatic int seepair(char *, int, char *, int); 41218065Sadrian 42218065Sadrian/* 43218065Sadrian * page format: 44218065Sadrian * +------------------------------+ 45218065Sadrian * ino | n | keyoff | datoff | keyoff | 46218065Sadrian * +------------+--------+--------+ 47218065Sadrian * | datoff | - - - ----> | 48218065Sadrian * +--------+---------------------+ 49218065Sadrian * | F R E E A R E A | 50218065Sadrian * +--------------+---------------+ 51218065Sadrian * | <---- - - - | data | 52218065Sadrian * +--------+-----+----+----------+ 53218065Sadrian * | key | data | key | 54218065Sadrian * +--------+----------+----------+ 55218065Sadrian * 56218065Sadrian * calculating the offsets for free area: if the number 57218065Sadrian * of entries (ino[0]) is zero, the offset to the END of 58218065Sadrian * the free area is the block size. Otherwise, it is the 59218065Sadrian * nth (ino[ino[0]]) entry's offset. 60218065Sadrian */ 61218065Sadrian 62218065Sadrianint 63218065Sadrianfitpair(pag, need) 64218065Sadrianchar *pag; 65218065Sadrianint need; 66218065Sadrian{ 67218065Sadrian register int n; 68218065Sadrian register int off; 69218065Sadrian register int avail; 70218065Sadrian register short *ino = (short *) pag; 71218065Sadrian 72218065Sadrian off = ((n = ino[0]) > 0) ? ino[n] : PBLKSIZ; 73218065Sadrian avail = off - (n + 1) * sizeof(short); 74218065Sadrian need += 2 * sizeof(short); 75218065Sadrian 76218065Sadrian debug(("avail %d need %d\n", avail, need)); 77218065Sadrian 78218065Sadrian return need <= avail; 79218065Sadrian} 80218065Sadrian 81227364Sadrianvoid 82218065Sadrianputpair(pag, key, val) 83218065Sadrianchar *pag; 84218065Sadrianapr_sdbm_datum_t key; 85218065Sadrianapr_sdbm_datum_t val; 86218065Sadrian{ 87218065Sadrian register int n; 88218065Sadrian register int off; 89218065Sadrian register short *ino = (short *) pag; 90218065Sadrian 91218065Sadrian off = ((n = ino[0]) > 0) ? ino[n] : PBLKSIZ; 92218065Sadrian/* 93218065Sadrian * enter the key first 94218065Sadrian */ 95218065Sadrian off -= key.dsize; 96218065Sadrian (void) memcpy(pag + off, key.dptr, key.dsize); 97218065Sadrian ino[n + 1] = off; 98218065Sadrian/* 99218065Sadrian * now the data 100218065Sadrian */ 101218065Sadrian off -= val.dsize; 102218240Sadrian (void) memcpy(pag + off, val.dptr, val.dsize); 103218065Sadrian ino[n + 2] = off; 104242782Sadrian/* 105242782Sadrian * adjust item count 106242782Sadrian */ 107242782Sadrian ino[0] += 2; 108218154Sadrian} 109227364Sadrian 110227364Sadrianapr_sdbm_datum_t 111227364Sadriangetpair(pag, key) 112227364Sadrianchar *pag; 113240946Sadrianapr_sdbm_datum_t key; 114240946Sadrian{ 115240946Sadrian register int i; 116240946Sadrian register int n; 117240946Sadrian apr_sdbm_datum_t val; 118241170Sadrian register short *ino = (short *) pag; 119241170Sadrian 120241170Sadrian if ((n = ino[0]) == 0) 121227364Sadrian return sdbm_nullitem; 122227364Sadrian 123227364Sadrian if ((i = seepair(pag, n, key.dptr, key.dsize)) == 0) 124227364Sadrian return sdbm_nullitem; 125236872Sadrian 126236872Sadrian val.dptr = pag + ino[i + 1]; 127227364Sadrian val.dsize = ino[i] - ino[i + 1]; 128227364Sadrian return val; 129240639Sadrian} 130240639Sadrian 131240639Sadrianint 132227364Sadrianduppair(pag, key) 133243162Sadrianchar *pag; 134243162Sadrianapr_sdbm_datum_t key; 135243162Sadrian{ 136243162Sadrian register short *ino = (short *) pag; 137243162Sadrian return ino[0] > 0 && seepair(pag, ino[0], key.dptr, key.dsize) > 0; 138243162Sadrian} 139243162Sadrian 140243162Sadrianapr_sdbm_datum_t 141243162Sadriangetnkey(pag, num) 142243162Sadrianchar *pag; 143243162Sadrianint num; 144243162Sadrian{ 145243162Sadrian apr_sdbm_datum_t key; 146243162Sadrian register int off; 147243162Sadrian register short *ino = (short *) pag; 148243162Sadrian 149243162Sadrian num = num * 2 - 1; 150243162Sadrian if (ino[0] == 0 || num > ino[0]) 151243162Sadrian return sdbm_nullitem; 152243162Sadrian 153243162Sadrian off = (num > 1) ? ino[num - 1] : PBLKSIZ; 154243162Sadrian 155243162Sadrian key.dptr = pag + ino[num]; 156243162Sadrian key.dsize = off - ino[num]; 157243162Sadrian 158243162Sadrian return key; 159243162Sadrian} 160243162Sadrian 161243162Sadrianint 162227364Sadriandelpair(pag, key) 163218154Sadrianchar *pag; 164218154Sadrianapr_sdbm_datum_t key; 165218154Sadrian{ 166218154Sadrian register int n; 167218154Sadrian register int i; 168239198Sadrian register short *ino = (short *) pag; 169239198Sadrian 170218154Sadrian if ((n = ino[0]) == 0) 171218154Sadrian return 0; 172227364Sadrian 173227364Sadrian if ((i = seepair(pag, n, key.dptr, key.dsize)) == 0) 174227364Sadrian return 0; 175227364Sadrian/* 176227364Sadrian * found the key. if it is the last entry 177227364Sadrian * [i.e. i == n - 1] we just adjust the entry count. 178227364Sadrian * hard case: move all data down onto the deleted pair, 179227364Sadrian * shift offsets onto deleted offsets, and adjust them. 180227364Sadrian * [note: 0 < i < n] 181227364Sadrian */ 182227364Sadrian if (i < n - 1) { 183227364Sadrian register int m; 184227364Sadrian register char *dst = pag + (i == 1 ? PBLKSIZ : ino[i - 1]); 185227364Sadrian register char *src = pag + ino[i + 1]; 186227364Sadrian register short zoo = (short) (dst - src); 187227364Sadrian 188227364Sadrian debug(("free-up %d ", zoo)); 189227364Sadrian/* 190227364Sadrian * shift data/keys down 191227364Sadrian */ 192240639Sadrian m = ino[i + 1] - ino[n]; 193240639Sadrian 194240639Sadrian#undef DUFF /* just use memmove. it should be plenty fast. */ 195240639Sadrian#ifdef DUFF 196240639Sadrian#define MOVB *--dst = *--src 197240639Sadrian 198240639Sadrian if (m > 0) { 199240639Sadrian register int loop = (m + 8 - 1) >> 3; 200240639Sadrian 201240639Sadrian switch (m & (8 - 1)) { 202240639Sadrian case 0: do { 203240639Sadrian MOVB; case 7: MOVB; 204240639Sadrian case 6: MOVB; case 5: MOVB; 205240639Sadrian case 4: MOVB; case 3: MOVB; 206240639Sadrian case 2: MOVB; case 1: MOVB; 207240639Sadrian } while (--loop); 208227364Sadrian } 209227364Sadrian } 210227364Sadrian#else 211227364Sadrian dst -= m; 212227364Sadrian src -= m; 213227364Sadrian memmove(dst, src, m); 214227364Sadrian#endif 215227364Sadrian 216227364Sadrian/* 217227364Sadrian * adjust offset index up 218227364Sadrian */ 219227364Sadrian while (i < n - 1) { 220227364Sadrian ino[i] = ino[i + 2] + zoo; 221227364Sadrian i++; 222227364Sadrian } 223227364Sadrian } 224227364Sadrian ino[0] -= 2; 225227364Sadrian return 1; 226227364Sadrian} 227227364Sadrian 228227364Sadrian/* 229227364Sadrian * search for the key in the page. 230227364Sadrian * return offset index in the range 0 < i < n. 231227364Sadrian * return 0 if not found. 232227364Sadrian */ 233227364Sadrianstatic int 234227364Sadrianseepair(pag, n, key, siz) 235240946Sadrianchar *pag; 236227364Sadrianregister int n; 237227364Sadrianregister char *key; 238218065Sadrianregister int siz; 239218065Sadrian{ 240218065Sadrian register int i; 241218065Sadrian register int off = PBLKSIZ; 242218065Sadrian register short *ino = (short *) pag; 243218065Sadrian 244218065Sadrian for (i = 1; i < n; i += 2) { 245218065Sadrian if (siz == off - ino[i] && 246227344Sadrian memcmp(key, pag + ino[i], siz) == 0) 247218065Sadrian return i; 248227344Sadrian off = ino[i + 1]; 249236993Sadrian } 250218065Sadrian return 0; 251218065Sadrian} 252218065Sadrian 253218065Sadrianvoid 254218065Sadriansplpage(pag, new, sbit) 255218065Sadrianchar *pag; 256218065Sadrianchar *new; 257218065Sadrianlong sbit; 258218065Sadrian{ 259218065Sadrian apr_sdbm_datum_t key; 260218065Sadrian apr_sdbm_datum_t val; 261218065Sadrian 262218065Sadrian register int n; 263218065Sadrian register int off = PBLKSIZ; 264218065Sadrian char cur[PBLKSIZ]; 265218065Sadrian register short *ino = (short *) cur; 266218065Sadrian 267218065Sadrian (void) memcpy(cur, pag, PBLKSIZ); 268237000Sadrian (void) memset(pag, 0, PBLKSIZ); 269237000Sadrian (void) memset(new, 0, PBLKSIZ); 270218065Sadrian 271234009Sadrian n = ino[0]; 272234009Sadrian for (ino++; n > 0; ino += 2) { 273218065Sadrian key.dptr = cur + ino[0]; 274218065Sadrian key.dsize = off - ino[0]; 275218065Sadrian val.dptr = cur + ino[1]; 276218065Sadrian val.dsize = ino[0] - ino[1]; 277227344Sadrian/* 278218065Sadrian * select the page pointer (by looking at sbit) and insert 279218065Sadrian */ 280218065Sadrian (void) putpair((exhash(key) & sbit) ? new : pag, key, val); 281227344Sadrian 282218065Sadrian off = ino[1]; 283218065Sadrian n -= 2; 284218065Sadrian } 285218065Sadrian 286218065Sadrian debug(("%d split %d/%d\n", ((short *) cur)[0] / 2, 287218065Sadrian ((short *) new)[0] / 2, 288218065Sadrian ((short *) pag)[0] / 2)); 289218065Sadrian} 290218065Sadrian 291218065Sadrian/* 292218065Sadrian * check page sanity: 293218065Sadrian * number of entries should be something 294218065Sadrian * reasonable, and all offsets in the index should be in order. 295218065Sadrian * this could be made more rigorous. 296218065Sadrian */ 297218065Sadrianint 298218065Sadrianchkpage(pag) 299218065Sadrianchar *pag; 300218065Sadrian{ 301218065Sadrian register int n; 302218065Sadrian register int off; 303218065Sadrian register short *ino = (short *) pag; 304218065Sadrian 305218065Sadrian if ((n = ino[0]) < 0 || n > PBLKSIZ / sizeof(short)) 306218065Sadrian return 0; 307218065Sadrian 308218065Sadrian if (n > 0) { 309218065Sadrian off = PBLKSIZ; 310218065Sadrian for (ino++; n > 0; ino += 2) { 311218065Sadrian if (ino[0] > off || ino[1] > off || 312218065Sadrian ino[1] > ino[0]) 313218065Sadrian return 0; 314218065Sadrian off = ino[1]; 315218065Sadrian n -= 2; 316218065Sadrian } 317218065Sadrian } 318218065Sadrian return 1; 319218065Sadrian} 320218065Sadrian