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