ext/SDBM_File/sdbm/sdbm.c

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