1/* 2 * sdbm - ndbm work-alike hashed database library 3 * based on Per-Aake Larson's Dynamic Hashing algorithms. BIT 18 (1978). 4 * author: oz@nexus.yorku.ca 5 * status: public domain. 6 * 7 * core routines 8 */ 9 10#ifndef lint 11static char rcsid[] = "$Id: sdbm.c,v 1.1 2004/05/23 22:50:39 neumann Exp $"; 12#endif 13 14/*#include "config.h"*/ 15#include "sdbm.h" 16#include "tune.h" 17#include "pair.h" 18 19#ifdef HAVE_UNISTD_H 20#include <unistd.h> 21#endif 22#include <stdlib.h> 23#ifdef HAVE_MEMORY_H 24#include <memory.h> 25#endif 26#include <string.h> 27#include <stdio.h> 28#include <errno.h> 29#include <sys/types.h> 30#include <sys/stat.h> 31#ifdef HAVE_SYS_FILE_H 32# include <sys/file.h> 33#endif 34#ifdef _WIN32 35# define HAVE_FCNTL_H 36# include <io.h> 37#endif 38/* 39#ifdef HAVE_FCNTL_H 40*/ 41# include <fcntl.h> 42/* 43#endif 44*/ 45#ifdef __STDC__ 46#include <stddef.h> 47#endif 48 49#ifndef NULL 50#define NULL 0 51#endif 52 53/* 54 * externals 55 */ 56#ifndef _WIN32 57#ifndef HAVE_UNISTD_H 58extern long lseek(); 59#endif 60#endif 61 62/* 63 * forward 64 */ 65static int getdbit proto((DBM *, long)); 66static int setdbit proto((DBM *, long)); 67static int getpage proto((DBM *, long)); 68static datum getnext proto((DBM *)); 69static int makroom proto((DBM *, long, int)); 70 71/* 72 * useful macros 73 */ 74#define bad(x) ((x).dptr == NULL || (x).dsize <= 0) 75#define exhash(item) sdbm_hash((item).dptr, (item).dsize) 76#define ioerr(db) ((db)->flags |= SDBM_IOERR) 77 78#define OFF_PAG(off) (long) (off) * PBLKSIZ 79#define OFF_DIR(off) (long) (off) * DBLKSIZ 80 81static long masks[] = { 82 000000000000, 000000000001, 000000000003, 000000000007, 83 000000000017, 000000000037, 000000000077, 000000000177, 84 000000000377, 000000000777, 000000001777, 000000003777, 85 000000007777, 000000017777, 000000037777, 000000077777, 86 000000177777, 000000377777, 000000777777, 000001777777, 87 000003777777, 000007777777, 000017777777, 000037777777, 88 000077777777, 000177777777, 000377777777, 000777777777, 89 001777777777, 003777777777, 007777777777, 017777777777 90}; 91 92datum nullitem = {NULL, 0}; 93 94DBM * 95sdbm_open(file, flags, mode) 96register char *file; 97register int flags; 98register int mode; 99{ 100 register DBM *db; 101 register char *dirname; 102 register char *pagname; 103 register int n; 104 105 if (file == NULL || !*file) 106 return errno = EINVAL, (DBM *) NULL; 107/* 108 * need space for two seperate filenames 109 */ 110 n = strlen(file) * 2 + strlen(DIRFEXT) + strlen(PAGFEXT) + 2; 111 112 if ((dirname = malloc((unsigned) n)) == NULL) 113 return errno = ENOMEM, (DBM *) NULL; 114/* 115 * build the file names 116 */ 117 dirname = strcat(strcpy(dirname, file), DIRFEXT); 118 pagname = strcpy(dirname + strlen(dirname) + 1, file); 119 pagname = strcat(pagname, PAGFEXT); 120 121 db = sdbm_prep(dirname, pagname, flags, mode); 122 free((char *) dirname); 123 return db; 124} 125 126DBM * 127sdbm_prep(dirname, pagname, flags, mode) 128char *dirname; 129char *pagname; 130int flags; 131int mode; 132{ 133 register DBM *db; 134 struct stat dstat; 135 136 if ((db = (DBM *) malloc(sizeof(DBM))) == NULL) 137 return errno = ENOMEM, (DBM *) NULL; 138 139 db->flags = 0; 140 db->hmask = 0; 141 db->blkptr = 0; 142 db->keyptr = 0; 143/* 144 * adjust user flags so that WRONLY becomes RDWR, 145 * as required by this package. Also set our internal 146 * flag for RDONLY if needed. 147 */ 148 if (flags & O_WRONLY) 149 flags = (flags & ~O_WRONLY) | O_RDWR; 150 151 else if ((flags & 03) == O_RDONLY) 152 db->flags = SDBM_RDONLY; 153 154#ifdef O_BINARY 155 /* GO32 / DOS-Braindamage */ 156 flags |= O_BINARY; 157#endif 158 159/* 160 * open the files in sequence, and stat the dirfile. 161 * If we fail anywhere, undo everything, return NULL. 162 */ 163 if ((db->pagf = open(pagname, flags, mode)) > -1) { 164 if ((db->dirf = open(dirname, flags, mode)) > -1) { 165/* 166 * need the dirfile size to establish max bit number. 167 */ 168 if (fstat(db->dirf, &dstat) == 0) { 169/* 170 * zero size: either a fresh database, or one with a single, 171 * unsplit data page: dirpage is all zeros. 172 */ 173 db->dirbno = (!dstat.st_size) ? 0 : -1; 174 db->pagbno = -1; 175 db->maxbno = dstat.st_size * BYTESIZ; 176 177 (void) memset(db->pagbuf, 0, PBLKSIZ); 178 (void) memset(db->dirbuf, 0, DBLKSIZ); 179 /* 180 * success 181 */ 182 return db; 183 } 184 (void) close(db->dirf); 185 } 186 (void) close(db->pagf); 187 } 188 free((char *) db); 189 return (DBM *) NULL; 190} 191 192void 193sdbm_close(db) 194register DBM *db; 195{ 196 if (db == NULL) 197 errno = EINVAL; 198 else { 199 (void) close(db->dirf); 200 (void) close(db->pagf); 201 free((char *) db); 202 } 203} 204 205datum 206sdbm_fetch(db, key) 207register DBM *db; 208datum key; 209{ 210 if (db == NULL || bad(key)) 211 return errno = EINVAL, nullitem; 212 213 if (getpage(db, exhash(key))) 214 return getpair(db->pagbuf, key); 215 216 return ioerr(db), nullitem; 217} 218 219int 220sdbm_delete(db, key) 221register DBM *db; 222datum key; 223{ 224 if (db == NULL || bad(key)) 225 return errno = EINVAL, -1; 226 if (sdbm_rdonly(db)) 227 return errno = EPERM, -1; 228 229 if (getpage(db, exhash(key))) { 230 if (!delpair(db->pagbuf, key)) 231 return -1; 232/* 233 * update the page file 234 */ 235 if (lseek(db->pagf, OFF_PAG(db->pagbno), SEEK_SET) < 0 236 || write(db->pagf, db->pagbuf, PBLKSIZ) < 0) 237 return ioerr(db), -1; 238 239 return 0; 240 } 241 242 return ioerr(db), -1; 243} 244 245int 246sdbm_store(db, key, val, flags) 247register DBM *db; 248datum key; 249datum val; 250int flags; 251{ 252 int need; 253 register long hash; 254 255 if (db == NULL || bad(key)) 256 return errno = EINVAL, -1; 257 if (sdbm_rdonly(db)) 258 return errno = EPERM, -1; 259 260 need = key.dsize + val.dsize; 261/* 262 * is the pair too big (or too small) for this database ?? 263 */ 264 if (need < 0 || need > PAIRMAX) 265 return errno = EINVAL, -1; 266 267 if (getpage(db, (hash = exhash(key)))) { 268/* 269 * if we need to replace, delete the key/data pair 270 * first. If it is not there, ignore. 271 */ 272 if (flags == SDBM_REPLACE) 273 (void) delpair(db->pagbuf, key); 274#ifdef SEEDUPS 275 else if (duppair(db->pagbuf, key)) 276 return 1; 277#endif 278/* 279 * if we do not have enough room, we have to split. 280 */ 281 if (!fitpair(db->pagbuf, need)) 282 if (!makroom(db, hash, need)) 283 return ioerr(db), -1; 284/* 285 * we have enough room or split is successful. insert the key, 286 * and update the page file. 287 */ 288 (void) putpair(db->pagbuf, key, val); 289 290 if (lseek(db->pagf, OFF_PAG(db->pagbno), SEEK_SET) < 0 291 || write(db->pagf, db->pagbuf, PBLKSIZ) < 0) 292 return ioerr(db), -1; 293 /* 294 * success 295 */ 296 return 0; 297 } 298 299 return ioerr(db), -1; 300} 301 302/* 303 * makroom - make room by splitting the overfull page 304 * this routine will attempt to make room for SPLTMAX times before 305 * giving up. 306 */ 307static int 308makroom(db, hash, need) 309register DBM *db; 310long hash; 311int need; 312{ 313 long newp; 314 char twin[PBLKSIZ]; 315 char *pag = db->pagbuf; 316 char *new = twin; 317 register int smax = SPLTMAX; 318 319 do { 320/* 321 * split the current page 322 */ 323 (void) splpage(pag, new, db->hmask + 1); 324/* 325 * address of the new page 326 */ 327 newp = (hash & db->hmask) | (db->hmask + 1); 328 329/* 330 * write delay, read avoidence/cache shuffle: 331 * select the page for incoming pair: if key is to go to the new page, 332 * write out the previous one, and copy the new one over, thus making 333 * it the current page. If not, simply write the new page, and we are 334 * still looking at the page of interest. current page is not updated 335 * here, as sdbm_store will do so, after it inserts the incoming pair. 336 */ 337 if (hash & (db->hmask + 1)) { 338 if (lseek(db->pagf, OFF_PAG(db->pagbno), SEEK_SET) < 0 339 || write(db->pagf, db->pagbuf, PBLKSIZ) < 0) 340 return 0; 341 db->pagbno = newp; 342 (void) memcpy(pag, new, PBLKSIZ); 343 } 344 else if (lseek(db->pagf, OFF_PAG(newp), SEEK_SET) < 0 345 || write(db->pagf, new, PBLKSIZ) < 0) 346 return 0; 347 348 if (!setdbit(db, db->curbit)) 349 return 0; 350/* 351 * see if we have enough room now 352 */ 353 if (fitpair(pag, need)) 354 return 1; 355/* 356 * try again... update curbit and hmask as getpage would have 357 * done. because of our update of the current page, we do not 358 * need to read in anything. BUT we have to write the current 359 * [deferred] page out, as the window of failure is too great. 360 */ 361 db->curbit = 2 * db->curbit + 362 ((hash & (db->hmask + 1)) ? 2 : 1); 363 db->hmask |= db->hmask + 1; 364 365 if (lseek(db->pagf, OFF_PAG(db->pagbno), SEEK_SET) < 0 366 || write(db->pagf, db->pagbuf, PBLKSIZ) < 0) 367 return 0; 368 369 } while (--smax); 370/* 371 * if we are here, this is real bad news. After SPLTMAX splits, 372 * we still cannot fit the key. say goodnight. 373 */ 374#ifdef BADMESS 375 (void) write(2, "sdbm: cannot insert after SPLTMAX attempts.\n", 44); 376#endif 377 return 0; 378 379} 380 381/* 382 * the following two routines will break if 383 * deletions aren't taken into account. (ndbm bug) 384 */ 385datum 386sdbm_firstkey(db) 387register DBM *db; 388{ 389 if (db == NULL) 390 return errno = EINVAL, nullitem; 391/* 392 * start at page 0 393 */ 394 if (lseek(db->pagf, OFF_PAG(0), SEEK_SET) < 0 395 || read(db->pagf, db->pagbuf, PBLKSIZ) < 0) 396 return ioerr(db), nullitem; 397 db->pagbno = 0; 398 db->blkptr = 0; 399 db->keyptr = 0; 400 401 return getnext(db); 402} 403 404datum 405sdbm_nextkey(db) 406register DBM *db; 407{ 408 if (db == NULL) 409 return errno = EINVAL, nullitem; 410 return getnext(db); 411} 412 413/* 414 * all important binary trie traversal 415 */ 416static int 417getpage(db, hash) 418register DBM *db; 419register long hash; 420{ 421 register int hbit; 422 register long dbit; 423 register long pagb; 424 425 dbit = 0; 426 hbit = 0; 427 while (dbit < db->maxbno && getdbit(db, dbit)) 428 dbit = 2 * dbit + ((hash & (1 << hbit++)) ? 2 : 1); 429 430 debug(("dbit: %d...", dbit)); 431 432 db->curbit = dbit; 433 db->hmask = masks[hbit]; 434 435 pagb = hash & db->hmask; 436/* 437 * see if the block we need is already in memory. 438 * note: this lookaside cache has about 10% hit rate. 439 */ 440 if (pagb != db->pagbno) { 441/* 442 * note: here, we assume a "hole" is read as 0s. 443 * if not, must zero pagbuf first. 444 */ 445 if (lseek(db->pagf, OFF_PAG(pagb), SEEK_SET) < 0 446 || read(db->pagf, db->pagbuf, PBLKSIZ) < 0) 447 return 0; 448 if (!chkpage(db->pagbuf)) 449 return 0; 450 db->pagbno = pagb; 451 452 debug(("pag read: %d\n", pagb)); 453 } 454 return 1; 455} 456 457static int 458getdbit(db, dbit) 459register DBM *db; 460register long dbit; 461{ 462 register long c; 463 register long dirb; 464 465 c = dbit / BYTESIZ; 466 dirb = c / DBLKSIZ; 467 468 if (dirb != db->dirbno) { 469 if (lseek(db->dirf, OFF_DIR(dirb), SEEK_SET) < 0 470 || read(db->dirf, db->dirbuf, DBLKSIZ) < 0) 471 return 0; 472 db->dirbno = dirb; 473 474 debug(("dir read: %d\n", dirb)); 475 } 476 477 return db->dirbuf[c % DBLKSIZ] & (1 << dbit % BYTESIZ); 478} 479 480static int 481setdbit(db, dbit) 482register DBM *db; 483register long dbit; 484{ 485 register long c; 486 register long dirb; 487 488 c = dbit / BYTESIZ; 489 dirb = c / DBLKSIZ; 490 491 if (dirb != db->dirbno) { 492 if (lseek(db->dirf, OFF_DIR(dirb), SEEK_SET) < 0 493 || read(db->dirf, db->dirbuf, DBLKSIZ) < 0) 494 return 0; 495 db->dirbno = dirb; 496 497 debug(("dir read: %d\n", dirb)); 498 } 499 500 db->dirbuf[c % DBLKSIZ] |= (1 << dbit % BYTESIZ); 501 502 if (dbit >= db->maxbno) 503 db->maxbno += DBLKSIZ * BYTESIZ; 504 505 if (lseek(db->dirf, OFF_DIR(dirb), SEEK_SET) < 0 506 || write(db->dirf, db->dirbuf, DBLKSIZ) < 0) 507 return 0; 508 509 return 1; 510} 511 512/* 513 * getnext - get the next key in the page, and if done with 514 * the page, try the next page in sequence 515 */ 516static datum 517getnext(db) 518register DBM *db; 519{ 520 datum key; 521 522 for (;;) { 523 db->keyptr++; 524 key = getnkey(db->pagbuf, db->keyptr); 525 if (key.dptr != NULL) 526 return key; 527/* 528 * we either run out, or there is nothing on this page.. 529 * try the next one... If we lost our position on the 530 * file, we will have to seek. 531 */ 532 db->keyptr = 0; 533 if (db->pagbno != db->blkptr++) 534 if (lseek(db->pagf, OFF_PAG(db->blkptr), SEEK_SET) < 0) 535 break; 536 db->pagbno = db->blkptr; 537 if (read(db->pagf, db->pagbuf, PBLKSIZ) <= 0) 538 break; 539 if (!chkpage(db->pagbuf)) 540 break; 541 } 542 543 return ioerr(db), nullitem; 544} 545