/* * Copyright (c) 1983 Regents of the University of California. * All rights reserved. The Berkeley software License Agreement * specifies the terms and conditions for redistribution. */ #include "autoconf.h" #include "copyright.h" #ifndef lint static char *RCSid = "$Id: myndbm.c,v 1.5 1995/03/07 22:13:21 ambar Exp $"; USE(RCSid); #endif #if defined(LIBC_SCCS) && !defined(lint) static char sccsid[] = "@(#)ndbm.c 5.4 (Berkeley) 9/4/87"; #endif /* LIBC_SCCS and not lint */ #include "config.h" #include "myndbm.h" #define BYTESIZ 8 #undef setbit static datum makdatum(); static long finddatum(); static int additem(); static int delitem(); static long dcalchash(); extern int errno; DBM * dbm_open(file, flags, mode) char *file; int flags, mode; { struct stat statb; register DBM *db; if ((db = (DBM *) XMALLOC(sizeof(*db), "dbm_open")) == 0) { errno = ENOMEM; return ((DBM *) NULL); } db->dbm_flags = (flags & 03) == O_RDONLY ? _DBM_RDONLY : 0; if ((flags & 03) == O_WRONLY) flags = (flags & ~03) | O_RDWR; strcpy(db->dbm_pagbuf, file); strcat(db->dbm_pagbuf, ".pag"); db->dbm_pagf = open(db->dbm_pagbuf, flags, mode); if (db->dbm_pagf < 0) goto bad; strcpy(db->dbm_pagbuf, file); strcat(db->dbm_pagbuf, ".dir"); db->dbm_dirf = open(db->dbm_pagbuf, flags, mode); if (db->dbm_dirf < 0) goto bad1; fstat(db->dbm_dirf, &statb); db->dbm_maxbno = statb.st_size * BYTESIZ - 1; db->dbm_pagbno = db->dbm_dirbno = -1; return (db); bad1: (void) close(db->dbm_pagf); bad: free((char *) db); return ((DBM *) 0); } void dbm_close(db) DBM *db; { (void) close(db->dbm_dirf); (void) close(db->dbm_pagf); free((char *) db); } static int getbit(db) register DBM *db; { long bn; register b, i, n; if (db->dbm_bitno > db->dbm_maxbno) return (0); n = db->dbm_bitno % BYTESIZ; bn = db->dbm_bitno / BYTESIZ; i = bn % DBLKSIZ; b = bn / DBLKSIZ; if (b != db->dbm_dirbno) { db->dbm_dirbno = b; (void) lseek(db->dbm_dirf, (long) b * DBLKSIZ, L_SET); if (read(db->dbm_dirf, db->dbm_dirbuf, DBLKSIZ) != DBLKSIZ) bzero(db->dbm_dirbuf, DBLKSIZ); } return (db->dbm_dirbuf[i] & (1 << n)); } static void setbit(db) register DBM *db; { long bn; register i, n, b; if (db->dbm_bitno > db->dbm_maxbno) db->dbm_maxbno = db->dbm_bitno; n = db->dbm_bitno % BYTESIZ; bn = db->dbm_bitno / BYTESIZ; i = bn % DBLKSIZ; b = bn / DBLKSIZ; if (b != db->dbm_dirbno) { db->dbm_dirbno = b; (void) lseek(db->dbm_dirf, (long) b * DBLKSIZ, L_SET); if (read(db->dbm_dirf, db->dbm_dirbuf, DBLKSIZ) != DBLKSIZ) bzero(db->dbm_dirbuf, DBLKSIZ); } db->dbm_dirbuf[i] |= 1 << n; db->dbm_dirbno = b; (void) lseek(db->dbm_dirf, (long) b * DBLKSIZ, L_SET); if (write(db->dbm_dirf, db->dbm_dirbuf, DBLKSIZ) != DBLKSIZ) db->dbm_flags |= _DBM_IOERR; } long dbm_forder(db, key) register DBM *db; datum key; { long hash; hash = dcalchash(key); for (db->dbm_hmask = 0;; db->dbm_hmask = (db->dbm_hmask << 1) + 1) { db->dbm_blkno = hash & db->dbm_hmask; db->dbm_bitno = db->dbm_blkno + db->dbm_hmask; if (getbit(db) == 0) break; } return (db->dbm_blkno); } static void dbm_access(db, hash) register DBM *db; long hash; { for (db->dbm_hmask = 0;; db->dbm_hmask = (db->dbm_hmask << 1) + 1) { db->dbm_blkno = hash & db->dbm_hmask; db->dbm_bitno = db->dbm_blkno + db->dbm_hmask; if (getbit(db) == 0) break; } if (db->dbm_blkno != db->dbm_pagbno) { db->dbm_pagbno = db->dbm_blkno; (void) lseek(db->dbm_pagf, db->dbm_blkno * PBLKSIZ, L_SET); if (read(db->dbm_pagf, db->dbm_pagbuf, PBLKSIZ) != PBLKSIZ) bzero(db->dbm_pagbuf, PBLKSIZ); #ifdef DEBUG else if (chkblk(db->dbm_pagbuf) < 0) db->dbm_flags |= _DBM_IOERR; #endif } } datum dbm_fetch(db, key) register DBM *db; datum key; { register long i; datum item; if (dbm_error(db)) goto err; dbm_access(db, dcalchash(key)); if ((i = finddatum(db->dbm_pagbuf, key)) >= 0) { item = makdatum(db->dbm_pagbuf, i + 1); if (item.dptr != NULL) return (item); } err: item.dptr = NULL; item.dsize = 0; return (item); } int dbm_delete(db, key) register DBM *db; datum key; { register long i; if (dbm_error(db)) return (-1); if (dbm_rdonly(db)) { errno = EPERM; return (-1); } dbm_access(db, dcalchash(key)); if ((i = finddatum(db->dbm_pagbuf, key)) < 0) return (-1); if (!delitem(db->dbm_pagbuf, i)) goto err; db->dbm_pagbno = db->dbm_blkno; (void) lseek(db->dbm_pagf, db->dbm_blkno * PBLKSIZ, L_SET); if (write(db->dbm_pagf, db->dbm_pagbuf, PBLKSIZ) != PBLKSIZ) { err: db->dbm_flags |= _DBM_IOERR; return (-1); } return (0); } int dbm_store(db, key, dat, replace) register DBM *db; datum key, dat; int replace; { register long i; datum item, item1; char ovfbuf[PBLKSIZ]; if (dbm_error(db)) return (-1); if (dbm_rdonly(db)) { errno = EPERM; return (-1); } loop: dbm_access(db, dcalchash(key)); if ((i = finddatum(db->dbm_pagbuf, key)) >= 0) { if (!replace) return (1); if (!delitem(db->dbm_pagbuf, i)) { db->dbm_flags |= _DBM_IOERR; return (-1); } } if (!additem(db->dbm_pagbuf, key, dat)) goto split; db->dbm_pagbno = db->dbm_blkno; (void) lseek(db->dbm_pagf, db->dbm_blkno * PBLKSIZ, L_SET); if (write(db->dbm_pagf, db->dbm_pagbuf, PBLKSIZ) != PBLKSIZ) { db->dbm_flags |= _DBM_IOERR; return (-1); } return (0); split: if (key.dsize + dat.dsize + 3 * sizeof(short) >= PBLKSIZ) { db->dbm_flags |= _DBM_IOERR; errno = ENOSPC; return (-1); } bzero(ovfbuf, PBLKSIZ); for (i = 0;;) { item = makdatum(db->dbm_pagbuf, i); if (item.dptr == NULL) break; if (dcalchash(item) & (db->dbm_hmask + 1)) { item1 = makdatum(db->dbm_pagbuf, i + 1); if (item1.dptr == NULL) { fprintf(stderr, "ndbm: split not paired\n"); db->dbm_flags |= _DBM_IOERR; break; } if (!additem(ovfbuf, item, item1) || !delitem(db->dbm_pagbuf, i)) { db->dbm_flags |= _DBM_IOERR; return (-1); } continue; } i += 2; } db->dbm_pagbno = db->dbm_blkno; (void) lseek(db->dbm_pagf, db->dbm_blkno * PBLKSIZ, L_SET); if (write(db->dbm_pagf, db->dbm_pagbuf, PBLKSIZ) != PBLKSIZ) { db->dbm_flags |= _DBM_IOERR; return (-1); } (void) lseek(db->dbm_pagf, (db->dbm_blkno + db->dbm_hmask + 1) * PBLKSIZ, L_SET); if (write(db->dbm_pagf, ovfbuf, PBLKSIZ) != PBLKSIZ) { db->dbm_flags |= _DBM_IOERR; return (-1); } setbit(db); goto loop; } datum dbm_firstkey(db) DBM *db; { db->dbm_blkptr = 0L; db->dbm_keyptr = 0; return (dbm_nextkey(db)); } datum dbm_nextkey(db) register DBM *db; { struct stat statb; datum item; if (dbm_error(db) || fstat(db->dbm_pagf, &statb) < 0) goto err; statb.st_size /= PBLKSIZ; for (;;) { if (db->dbm_blkptr != db->dbm_pagbno) { db->dbm_pagbno = db->dbm_blkptr; (void) lseek(db->dbm_pagf, db->dbm_blkptr * PBLKSIZ, L_SET); if (read(db->dbm_pagf, db->dbm_pagbuf, PBLKSIZ) != PBLKSIZ) bzero(db->dbm_pagbuf, PBLKSIZ); #ifdef DEBUG else if (chkblk(db->dbm_pagbuf) < 0) db->dbm_flags |= _DBM_IOERR; #endif } if (((short *) db->dbm_pagbuf)[0] != 0) { item = makdatum(db->dbm_pagbuf, db->dbm_keyptr); if (item.dptr != NULL) { db->dbm_keyptr += 2; return (item); } db->dbm_keyptr = 0; } if (++db->dbm_blkptr >= statb.st_size) break; } err: item.dptr = NULL; item.dsize = 0; return (item); } static datum makdatum(buf, n) char buf[PBLKSIZ]; int n; { register short *sp; register t; datum item; sp = (short *) buf; if ((unsigned) n >= sp[0]) { item.dptr = NULL; item.dsize = 0; return (item); } t = PBLKSIZ; if (n > 0) t = sp[n]; item.dptr = buf + sp[n + 1]; item.dsize = t - sp[n + 1]; return (item); } static long finddatum(buf, item) char buf[PBLKSIZ]; datum item; { register short *sp; register int i, n, j; sp = (short *) buf; n = PBLKSIZ; for (i = 0, j = sp[0]; i < j; i += 2, n = sp[i]) { n -= sp[i + 1]; if (n != item.dsize) continue; if (n == 0 || bcmp(&buf[sp[i + 1]], item.dptr, n) == 0) return (i); } return (-1); } static int hitab[16] = {61, 57, 53, 49, 45, 41, 37, 33, 29, 25, 21, 17, 13, 9, 5, 1, }; static long hltab[64] = { 06100151277L, 06106161736L, 06452611562L, 05001724107L, 02614772546L, 04120731531L, 04665262210L, 07347467531L, 06735253126L, 06042345173L, 03072226605L, 01464164730L, 03247435524L, 07652510057L, 01546775256L, 05714532133L, 06173260402L, 07517101630L, 02431460343L, 01743245566L, 00261675137L, 02433103631L, 03421772437L, 04447707466L, 04435620103L, 03757017115L, 03641531772L, 06767633246L, 02673230344L, 00260612216L, 04133454451L, 00615531516L, 06137717526L, 02574116560L, 02304023373L, 07061702261L, 05153031405L, 05322056705L, 07401116734L, 06552375715L, 06165233473L, 05311063631L, 01212221723L, 01052267235L, 06000615237L, 01075222665L, 06330216006L, 04402355630L, 01451177262L, 02000133436L, 06025467062L, 07121076461L, 03123433522L, 01010635225L, 01716177066L, 05161746527L, 01736635071L, 06243505026L, 03637211610L, 01756474365L, 04723077174L, 03642763134L, 05750130273L, 03655541561L, }; static long dcalchash(item) datum item; { register int s, c, j; register char *cp; register long hashl; register int hashi; hashl = 0; hashi = 0; for (cp = item.dptr, s = item.dsize; --s >= 0;) { c = *cp++; for (j = 0; j < BYTESIZ; j += 4) { hashi += hitab[c & 017]; hashl += hltab[hashi & 63]; c >>= 4; } } return (hashl); } /* * Delete pairs of items (n & n+1). */ static int delitem(buf, n) char buf[PBLKSIZ]; int n; { register short *sp, *sp1; register i1, i2; sp = (short *) buf; i2 = sp[0]; if ((unsigned) n >= i2 || (n & 1)) return (0); if (n == i2 - 2) { sp[0] -= 2; return (1); } i1 = PBLKSIZ; if (n > 0) i1 = sp[n]; i1 -= sp[n + 2]; if (i1 > 0) { i2 = sp[i2]; bcopy(&buf[i2], &buf[i2 + i1], sp[n + 2] - i2); } sp[0] -= 2; for (sp1 = sp + sp[0], sp += n + 1; sp <= sp1; sp++) sp[0] = sp[2] + i1; return (1); } /* * Add pairs of items (item & item1). */ static int additem(buf, item, item1) char buf[PBLKSIZ]; datum item, item1; { register short *sp; register i1, i2; sp = (short *) buf; i1 = PBLKSIZ; i2 = sp[0]; if (i2 > 0) i1 = sp[i2]; i1 -= item.dsize + item1.dsize; if (i1 <= (i2 + 3) * (int) sizeof(short)) return (0); sp[0] += 2; sp[++i2] = i1 + item1.dsize; bcopy(item.dptr, &buf[i1 + item1.dsize], item.dsize); sp[++i2] = i1; bcopy(item1.dptr, &buf[i1], item1.dsize); return (1); } #ifdef DEBUG static chkblk(buf) char buf[PBLKSIZ]; { register short *sp; register t, i; sp = (short *) buf; t = PBLKSIZ; for (i = 0; i < sp[0]; i++) { if (sp[i + 1] > t) return (-1); t = sp[i + 1]; } if (t < (sp[0] + 1) * sizeof(short)) return (-1); return (0); } #endif