lee@sq.sq.com (Liam R. E. Quin) (03/04/91)
: cut here --- cut here --
: To unbundle, sh this file
#! /bin/sh
: part 13
echo x - lq-text/src/ozmahash/hash.h 1>&2
sed 's/^X//' >lq-text/src/ozmahash/hash.h <<'@@@End of lq-text/src/ozmahash/hash.h'
X/*-
X * Copyright (c) 1990 The Regents of the University of California.
X * All rights reserved.
X *
X * This code is derived from software contributed to Berkeley by
X * Margo Seltzer.
X *
X * %sccs.include.redist.c%
X *
X * %W% (Berkeley) %G%
X */
X
X/* Operations */
Xtypedef enum { HASH_GET, HASH_PUT, HASH_PUTNEW, HASH_DELETE,
X HASH_FIRST, HASH_NEXT } ACTION;
X
X/* Buffer Management structures */
Xtypedef struct _bufhead BUFHEAD;
X
Xstruct _bufhead {
X BUFHEAD *prev; /* LRU links */
X BUFHEAD *next; /* LRU links */
X BUFHEAD *ovfl; /* Overflow page buffer header */
X int addr; /* Address of this page */
X char *page; /* Actual page data */
X char flags; /* Combination of BUF_MOD, BUF_DISK, BUF_BUCKET */
X};
X
X/* Flag Values */
X#define BUF_MOD 0x0001
X#define BUF_DISK 0x0002
X#define BUF_BUCKET 0x0004
X
X#define IS_BUCKET(X) (X & BUF_BUCKET)
X
Xtypedef BUFHEAD **SEGMENT;
X
X/* Hash Table Information */
Xtypedef struct hashhdr { /* Disk resident portion */
X int magic; /* Magic NO for hash tables */
X int version; /* Version ID */
X long lorder; /* Byte Order */
X int bsize; /* Bucket/Page Size */
X int bshift; /* Bucket shift */
X int dsize; /* Directory Size */
X int ssize; /* Segment Size */
X int sshift; /* Segment shift */
X int max_bucket; /* ID of Maximum bucket in use */
X int high_mask; /* Mask to modulo into entire table */
X int low_mask; /* Mask to modulo into lower half of table */
X int ffactor; /* Fill factor */
X int nkeys; /* Number of keys in hash table */
X int hdrpages; /* Size of table header */
X int h_charkey; /* value of hash(CHARKEY) */
X# define NCACHED 32 /* number of bit maps and spare points*/
X int spares[NCACHED]; /* spare pages for overflow */
X u_short bitmaps[NCACHED]; /* address of overflow page bitmaps */
X} HASHHDR;
X
Xtypedef struct htab { /* Memory resident data structure */
X HASHHDR hdr; /* Header */
X int nsegs; /* Number of allocated segments */
X int exsegs; /* Number of extra allocated segments */
X int (*hash)(); /* Hash Function */
X int flags; /* Flag values */
X int fp; /* File pointer */
X char *tmp_buf; /* Temporary Buffer for BIG data */
X char *tmp_key; /* Temporary Buffer for BIG keys */
X BUFHEAD *cpage; /* Current page */
X int cbucket; /* Current bucket */
X int cndx; /* Index of next item on cpage */
X int errno; /* Error Number -- for DBM compatability */
X int new_file; /* Indicates whether fd is backing store or no */
X int save_file; /* Indicates whether we need to flush file at exit */
X u_long *mapp[NCACHED]; /* Pointers to page maps */
X int nbufs; /* Number of buffers left to allocate */
X BUFHEAD bufhead; /* Header of buffer lru list */
X SEGMENT *dir; /* Hash Bucket directory */
X} HTAB;
X
X
X/*
X * Constants
X */
X#define MAX_BSIZE 65536 /* 2^16 */
X#define MIN_BUFFERS 6
X#define MINHDRSIZE 512
X#define DEF_BUFSIZE 65536 /* 64 K */
X#define DEF_BUCKET_SIZE 256
X#define DEF_BUCKET_SHIFT 8 /* log2(BUCKET) */
X#define DEF_SEGSIZE 256
X#define DEF_SEGSIZE_SHIFT 8 /* log2(SEGSIZE) */
X#define DEF_DIRSIZE 256
X#define DEF_FFACTOR 5
X#define SPLTMAX 8
X#define CHARKEY "%$sniglet^&"
X#define NUMKEY 1038583
X#define VERSION_NO 3
X#define BYTE_SHIFT 3
X#define INT_TO_BYTE 2
X#define INT_BYTE_SHIFT 5
X#define ALL_SET ((unsigned)0xFFFFFFFF)
X#define ALL_CLEAR 0
X
X
X#define MAX(A,B) ( (A>B)?A:B )
X#define PTROF(X) ((BUFHEAD *)((unsigned)(X)&~0x3))
X#define ISMOD(X) ((unsigned)(X)&0x1)
X#define DOMOD(X) (X = (char *)( (unsigned)X | 0x1))
X#define ISDISK(X) ((unsigned)(X)&0x2)
X#define DODISK(X) (X = (char *)( (unsigned)X | 0x2))
X
X#define BITS_PER_MAP 32
X
X/* Given the address of the beginning of a big map, clear/set the nth bit */
X
X#define CLRBIT(A,N) ((A)[N/BITS_PER_MAP] &= ~(1<<(N%BITS_PER_MAP)))
X#define SETBIT(A,N) ((A)[N/BITS_PER_MAP] |= (1<<(N%BITS_PER_MAP)))
X#define ISSET(A,N) ((A)[N/BITS_PER_MAP] & (1<<(N%BITS_PER_MAP)))
X
X/* Overflow management */
X/*
X Overflow page numbers are allocated per split point.
X At each doubling of the table, we can allocate extra
X pages. So, an overflow page number has the top 5 bits
X indicate which split point and the lower 11 bits indicate
X which page at that split point is indicated (pages within
X split points are numberered starting with 1).
X
X
X*/
X
X#define SPLITSHIFT 11
X#define SPLITMASK 0x7FF
X#define SPLITNUM(N) (((unsigned)N) >> SPLITSHIFT)
X#define OPAGENUM(N) (N & SPLITMASK)
X#define OADDR_OF(S,O) ((S << SPLITSHIFT) + O)
X
X#define BUCKET_TO_PAGE(B) \
X B + hashp->HDRPAGES + (B ? hashp->SPARES[log2(B+1)-1] : 0)
X#define OADDR_TO_PAGE(B) \
X BUCKET_TO_PAGE ( (1 << SPLITNUM(B)) -1 ) + OPAGENUM(B);
X
X/*
X page.h contains a detailed description of the page format.
X
X Normally, keys and data are accessed from offset tables in the
X top of each page which point to the beginning of the key and
X data. There are four flag values which may be stored in these
X offset tables which indicate the following:
X
X OVFLPAGE Rather than a key data pair, this pair contains
X the address of an overflow page. The format of
X the pair is:
X OVERFLOW_PAGE_NUMBER OVFLPAGE
X
X PARTIAL_KEY This must be the first key/data pair on a page
X and implies that page contains only a partial key.
X That is, the key is too big to fit on a single page
X so it starts on this page and continues on the next.
X The format of the page is:
X KEY_OFF PARTIAL_KEY OVFL_PAGENO OVFLPAGE
X
X KEY_OFF -- offset of the beginning of the key
X PARTIAL_KEY -- 1
X OVFL_PAGENO - page number of the next overflow page
X OVFLPAGE -- 0
X FULL_KEY This must be the first key/data pair on the page. It
X is used in two cases.
X
X Case 1:
X There is a complete key on the page but no data
X (because it wouldn't fit). The next page contains
X the data.
X
X Page format it:
X KEY_OFF FULL_KEY OVFL_PAGENO OVFL_PAGE
X
X KEY_OFF -- offset of the beginning of the key
X FULL_KEY -- 2
X OVFL_PAGENO - page number of the next overflow page
X OVFLPAGE -- 0
X
X Case 2:
X This page contains no key, but part of a large
X data field, which is continued on the next page.
X
X Page format it:
X DATA_OFF FULL_KEY OVFL_PAGENO OVFL_PAGE
X
X KEY_OFF -- offset of the beginning of the data on
X this page
X FULL_KEY -- 2
X OVFL_PAGENO - page number of the next overflow page
X OVFLPAGE -- 0
X
X FULL_KEY_DATA This must be the first key/data pair on the page.
X There are two cases:
X
X Case 1:
X This page contains a key and the beginning of the
X data field, but the data field is continued on the
X next page.
X
X Page format is:
X KEY_OFF FULL_KEY_DATA OVFL_PAGENO DATA_OFF
X
X KEY_OFF -- offset of the beginning of the key
X FULL_KEY_DATA -- 3
X OVFL_PAGENO - page number of the next overflow page
X DATA_OFF -- offset of the beginning of the data
X
X Case 2:
X This page contains the last page of a big data pair.
X There is no key, only the tail end of the data
X on this page.
X
X Page format is:
X DATA_OFF FULL_KEY_DATA <OVFL_PAGENO> <OVFLPAGE>
X
X DATA_OFF -- offset of the beginning of the data on
X this page
X FULL_KEY_DATA -- 3
X OVFL_PAGENO - page number of the next overflow page
X OVFLPAGE -- 0
X
X OVFL_PAGENO and OVFLPAGE are optional (they are
X not present if there is no next page).
X*/
X#define OVFLPAGE 0
X#define PARTIAL_KEY 1
X#define FULL_KEY 2
X#define FULL_KEY_DATA 3
X#define REAL_KEY 4
X
X
X/* Short hands for accessing structure */
X#define BSIZE hdr.bsize
X#define BSHIFT hdr.bshift
X#define DSIZE hdr.dsize
X#define SGSIZE hdr.ssize
X#define SSHIFT hdr.sshift
X#define LORDER hdr.lorder
X#define MAX_BUCKET hdr.max_bucket
X#define FFACTOR hdr.ffactor
X#define HIGH_MASK hdr.high_mask
X#define LOW_MASK hdr.low_mask
X#define NKEYS hdr.nkeys
X#define HDRPAGES hdr.hdrpages
X#define SPARES hdr.spares
X#define BITMAPS hdr.bitmaps
X#define VERSION hdr.version
X#define MAGIC hdr.magic
X#define NEXT_FREE hdr.next_free
X#define H_CHARKEY hdr.h_charkey
@@@End of lq-text/src/ozmahash/hash.h
echo x - lq-text/src/ozmahash/hfunc.c 1>&2
sed 's/^X//' >lq-text/src/ozmahash/hfunc.c <<'@@@End of lq-text/src/ozmahash/hfunc.c'
X/*-
X * Copyright (c) 1990 The Regents of the University of California.
X * All rights reserved.
X *
X * This code is derived from software contributed to Berkeley by
X * Margo Seltzer.
X *
X * %sccs.include.redist.c%
X */
X
X#if defined(LIBC_SCCS) && !defined(lint)
Xstatic char sccsid[] = "%W% (Berkeley) %G%";
X#endif /* LIBC_SCCS and not lint */
X
X/* Global default hash function */
Xstatic int hash1();
Xstatic int hash2();
Xstatic int hash3();
Xstatic int hash4();
X
Xint (*default_hash)() = hash4;
X
X/******************************* HASH FUNCTIONS **************************/
X/*
X Assume that we've already split the bucket to which this
X key hashes, calculate that bucket, and check that in fact
X we did already split it.
X
X This came from ejb's hsearch.
X*/
X
X# define PRIME1 37
X# define PRIME2 1048583
X
Xstatic int
Xhash1(key,len)
Xchar *key;
Xint len;
X{
X register int h;
X register int l = len;
X register unsigned char *k = (unsigned char *) key;
X
X h = 0;
X /*
X * Convert string to integer
X */
X while (l--) h = h * PRIME1 ^ (*k++ - ' ');
X h %= PRIME2;
X
X return (h);
X}
X
X/*
X Phong's linear congruential hash
X*/
X#define dcharhash(h, c) ((h) = 0x63c63cd9*(h) + 0x9c39c33d + (c))
X
Xstatic int
Xhash2(str, n)
X register unsigned char *str;
X int n;
X{
X register unsigned char *e, c;
X register int h;
X
X e = str + n;
X for (h = 0; str != e;) {
X c = *str++;
X if (!c && str > e)
X break;
X dcharhash(h,c);
X }
X return(h);
X}
X
X/*
X * This is INCREDIBLY ugly, but fast.
X * We break the string up into 8 byte units. On the first time
X * through the loop we get the "leftover bytes" (strlen % 8).
X * On every other iteration, we perform 8 HASHC's so we handle
X * all 8 bytes. Essentially, this saves us 7 cmp & branch
X * instructions. If this routine is heavily used enough, it's
X * worth the ugly coding
X *
X * OZ's original sdbm hash
X */
Xstatic int
Xhash3(key,nbytes)
Xchar *key;
Xint nbytes;
X{
X register int n = 0;
X register char *str = key;
X register int loop;
X register int len = nbytes;
X
X#define HASHC n = *str++ + 65599 * n
X
X if (len > 0) {
X loop = (len + 8 - 1) >> 3;
X
X switch(len & (8 - 1)) {
X case 0: do { /* All fall throughs */
X HASHC;
X case 7: HASHC;
X case 6: HASHC;
X case 5: HASHC;
X case 4: HASHC;
X case 3: HASHC;
X case 2: HASHC;
X case 1: HASHC;
X } while (--loop);
X }
X
X }
X return(n);
X}
X
X/* Hash function from Chris Torek */
Xstatic int
Xhash4(key,nbytes)
Xchar *key;
Xint nbytes;
X{
X register int h = 0;
X register char *p = key;
X register int loop;
X register int len = nbytes;
X
X#define HASH4a h = (h << 5) - h + *p++;
X#define HASH4b h = (h << 5) + h + *p++;
X#define HASH4 HASH4b
X
X if (len > 0) {
X loop = (len + 8 - 1) >> 3;
X
X switch(len & (8 - 1)) {
X case 0: do { /* All fall throughs */
X HASH4;
X case 7: HASH4;
X case 6: HASH4;
X case 5: HASH4;
X case 4: HASH4;
X case 3: HASH4;
X case 2: HASH4;
X case 1: HASH4;
X } while (--loop);
X }
X
X }
X return(h);
X}
@@@End of lq-text/src/ozmahash/hfunc.c
echo x - lq-text/src/ozmahash/hsearch.c 1>&2
sed 's/^X//' >lq-text/src/ozmahash/hsearch.c <<'@@@End of lq-text/src/ozmahash/hsearch.c'
X/*-
X * Copyright (c) 1990 The Regents of the University of California.
X * All rights reserved.
X *
X * This code is derived from software contributed to Berkeley by
X * Margo Seltzer.
X *
X * %sccs.include.redist.c%
X */
X
X#if defined(LIBC_SCCS) && !defined(lint)
Xstatic char sccsid[] = "%W% (Berkeley) %G%";
X#endif /* LIBC_SCCS and not lint */
X#include <sys/file.h>
X#include <sys/types.h>
X#include <stdio.h>
X#include <db.h>
X#include <search.h>
X
Xstatic DB *dbp = NULL;
Xstatic ENTRY retval;
X
Xextern int
Xhcreate ( nel )
Xunsigned nel;
X{
X int status;
X HASHINFO info;
X
X info.nelem = nel;
X info.bsize = 256;
X info.ffactor = 8;
X info.ncached = NULL;
X info.hash = NULL;
X info.lorder = 0;
X dbp = hash_open ( NULL, O_CREAT|O_RDWR, 0600, &info );
X return ( (int) dbp );
X}
X
X
Xextern ENTRY *
Xhsearch ( item, action )
XENTRY item;
XACTION action;
X{
X int status;
X DBT key, val;
X
X if ( !dbp ) {
X return(NULL);
X }
X
X key.data = item.key;
X key.size = strlen(item.key) + 1;
X
X if ( action == ENTER ) {
X val.data = item.data;
X val.size = strlen(item.data) + 1;
X status = (dbp->put) ( dbp, &key, &val, R_NOOVERWRITE );
X if ( status ) {
X return(NULL);
X }
X } else {
X /* FIND */
X status = (dbp->get) ( dbp, &key, &val );
X if ( status ) {
X return ( NULL );
X } else {
X item.data = val.data;
X }
X }
X return ( &item );
X}
X
X
Xextern void
Xhdestroy ()
X{
X if (dbp) {
X (void)(dbp->close) (dbp);
X dbp = NULL;
X }
X return;
X}
X
X
@@@End of lq-text/src/ozmahash/hsearch.c
echo x - lq-text/src/ozmahash/log2.c 1>&2
sed 's/^X//' >lq-text/src/ozmahash/log2.c <<'@@@End of lq-text/src/ozmahash/log2.c'
X/*-
X * Copyright (c) 1990 The Regents of the University of California.
X * All rights reserved.
X *
X * This code is derived from software contributed to Berkeley by
X * Margo Seltzer.
X *
X * %sccs.include.redist.c%
X */
X
X#if defined(LIBC_SCCS) && !defined(lint)
Xstatic char sccsid[] = "%W% (Berkeley) %G%";
X#endif /* LIBC_SCCS and not lint */
X
Xlog2( num )
Xint num;
X{
X register int i;
X register int limit = 1;
X
X for ( i = 0; limit < num; limit = limit << 1, i++ );
X return (i);
X}
@@@End of lq-text/src/ozmahash/log2.c
echo x - lq-text/src/ozmahash/mkstemp.c 1>&2
sed 's/^X//' >lq-text/src/ozmahash/mkstemp.c <<'@@@End of lq-text/src/ozmahash/mkstemp.c'
X/*-
X * Copyright (c) 1990 The Regents of the University of California.
X * All rights reserved.
X *
X * This code is derived from software contributed to Berkeley by
X * Margo Seltzer.
X *
X * %sccs.include.redist.c%
X */
X
X#if defined(LIBC_SCCS) && !defined(lint)
Xstatic char sccsid[] = "%W% (Berkeley) %G%";
X#endif /* LIBC_SCCS and not lint */
X
X#include <sys/file.h>
X
Xmkstemp(as)
X char *as;
X{
X register char *s;
X register unsigned int pid;
X register int fd, i;
X
X pid = getpid();
X s = as;
X while (*s++)
X /* void */;
X s--;
X while (*--s == 'X') {
X *s = (pid % 10) + '0';
X pid /= 10;
X }
X s++;
X i = 'a';
X while ((fd = open(as, O_CREAT|O_EXCL|O_RDWR, 0600)) == -1) {
X if (i == 'z')
X return(-1);
X *s = i++;
X }
X return(fd);
X}
@@@End of lq-text/src/ozmahash/mkstemp.c
echo x - lq-text/src/ozmahash/ndbm.c 1>&2
sed 's/^X//' >lq-text/src/ozmahash/ndbm.c <<'@@@End of lq-text/src/ozmahash/ndbm.c'
X/*-
X * Copyright (c) 1990 The Regents of the University of California.
X * All rights reserved.
X *
X * This code is derived from software contributed to Berkeley by
X * Margo Seltzer.
X *
X * %sccs.include.redist.c%
X */
X
X#if defined(LIBC_SCCS) && !defined(lint)
Xstatic char sccsid[] = "%W% (Berkeley) %G%";
X#endif /* LIBC_SCCS and not lint */
X/*
X This package provides a dbm compatible interface to the new hashing
X package described in db(3)
X*/
X
X#include <sys/types.h>
X#include <stdio.h>
X#include <ndbm.h>
X#include <hash.h>
X
X/*
X return *DBM on success
X NULL on failure
X*/
Xextern DBM *
Xdbm_open( file, flags, mode )
Xchar *file;
Xint flags;
Xint mode;
X{
X HASHINFO info;
X
X info.bsize = 1024;
X info.ffactor = 256; /* Liam -- smaller databases? */
X /** info.ffactor = 5; **/
X info.nelem = 1;
X info.ncached = NULL;
X info.hash = NULL;
X info.lorder = 0;
X return( hash_open ( file, flags, mode, &info ) );
X}
X
Xextern void
Xdbm_close(db)
XDBM *db;
X{
X (void)(db->close) (db);
X}
X
X/*
X Returns DATUM on success
X NULL on failure
X*/
Xextern datum
Xdbm_fetch( db, key )
XDBM *db;
Xdatum key;
X{
X int status;
X datum retval;
X
X status = (db->get) ( db, (DBT *)&key, (DBT *)&retval );
X if ( status ) {
X retval.dptr = NULL;
X retval.dsize = 0;
X }
X return(retval);
X}
X
X/*
X Returns DATUM on success
X NULL on failure
X*/
Xextern datum
Xdbm_firstkey(db)
XDBM *db;
X{
X int status;
X datum retkey;
X datum retdata;
X
X status = (db->seq) ( db, (DBT *)&retkey, (DBT *)&retdata, R_FIRST );
X if ( status ) {
X retkey.dptr = NULL;
X retkey.dsize = 0;
X }
X return(retkey);
X}
X/*
X Returns DATUM on success
X NULL on failure
X*/
Xextern datum
Xdbm_nextkey(db)
XDBM *db;
X{
X int status;
X datum retkey;
X datum retdata;
X
X status = (db->seq) ( db, (DBT *)&retkey, (DBT *)&retdata, R_NEXT );
X if ( status ) {
X retkey.dptr = NULL;
X retkey.dsize = 0;
X }
X return(retkey);
X}
X
X/*
X 0 on success
X <0 failure
X*/
Xextern int
Xdbm_delete(db, key)
XDBM *db;
Xdatum key;
X{
X int status;
X
X status = (db->delete)( db, (DBT *)&key );
X if ( status ) {
X return(-1);
X } else {
X return(0);
X }
X}
X
X/*
X 0 on success
X <0 failure
X 1 if DBM_INSERT and entry exists
X*/
Xextern int
Xdbm_store(db, key, content, flags)
XDBM *db;
Xdatum key;
Xdatum content;
Xint flags;
X{
X return ((db->put)( db, (DBT *)&key, (DBT *)&content,
X (flags == DBM_INSERT) ? R_NOOVERWRITE : 0 ));
X}
X
Xextern int
Xdbm_error(db)
XDBM *db;
X{
X HTAB *hp;
X
X hp = (HTAB *)db->internal;
X return ( hp->errno );
X}
X
Xextern int
Xdbm_clearerr(db)
XDBM *db;
X{
X HTAB *hp;
X
X hp = (HTAB *)db->internal;
X hp->errno = 0;
X return ( 0 );
X}
@@@End of lq-text/src/ozmahash/ndbm.c
echo x - lq-text/src/ozmahash/ndbm.h 1>&2
sed 's/^X//' >lq-text/src/ozmahash/ndbm.h <<'@@@End of lq-text/src/ozmahash/ndbm.h'
X/*
X * Copyright (c) 1989 The Regents of the University of California.
X * All rights reserved.
X *
X * Redistribution and use in source and binary forms are permitted
X * provided that the above copyright notice and this paragraph are
X * duplicated in all such forms and that any documentation,
X * advertising materials, and other materials related to such
X * distribution and use acknowledge that the software was developed
X * by the University of California, Berkeley. The name of the
X * University may not be used to endorse or promote products derived
X * from this software without specific prior written permission.
X * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
X * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
X * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
X *
X * %W% (Berkeley) %G%
X */
X#include <db.h>
X
X/* Map dbm interface onto hash(3) */
X#define DBM_RDONLY O_RDONLY
X
X/* Flags to dbm_store() */
X#define DBM_INSERT 0
X#define DBM_REPLACE 1
X
Xtypedef struct {
X char *dptr;
X int dsize;
X} datum;
X
Xtypedef DB DBM;
X
X#ifdef __STDC__ || c_plusplus
Xextern DBM *dbm_open(const char *, int, int);
Xextern void dbm_close(DBM *);
Xextern datum dbm_fetch(DBM *, datum);
Xextern datum dbm_firstkey(DBM *);
Xextern datum dbm_nextkey(DBM *);
Xextern long dbm_forder(DBM *, datum);
Xextern int dbm_delete(DBM *, datum);
Xextern int dbm_store(DBM *, datum, datum, int);
X#else
Xextern DBM *dbm_open();
Xextern void dbm_close();
Xextern datum dbm_fetch();
Xextern datum dbm_firstkey();
Xextern datum dbm_nextkey();
Xextern long dbm_forder();
Xextern int dbm_delete();
Xextern int dbm_store();
X#endif
@@@End of lq-text/src/ozmahash/ndbm.h
echo x - lq-text/src/ozmahash/page.c 1>&2
sed 's/^X//' >lq-text/src/ozmahash/page.c <<'@@@End of lq-text/src/ozmahash/page.c'
X/*-
X * Copyright (c) 1990 The Regents of the University of California.
X * All rights reserved.
X *
X * This code is derived from software contributed to Berkeley by
X * Margo Seltzer.
X *
X * %sccs.include.redist.c%
X */
X
X#if defined(LIBC_SCCS) && !defined(lint)
Xstatic char sccsid[] = "%W% (Berkeley) %G%";
X#endif /* LIBC_SCCS and not lint */
X/******************************************************************************
XPACKAGE: hashing
X
XDESCRIPTION:
X Page manipulation for hashing package.
X
XROUTINES:
X External
X get_page
X add_ovflpage
X Internal
X overflow_page
X open_temp
X******************************************************************************/
X
X#include <sys/types.h>
X#include <sys/file.h>
X#include <assert.h>
X#include <errno.h>
X#include <db.h>
X#include <hash.h>
X#include <page.h>
X#include <stdio.h>
X#include <endian.h>
X
X/* Externals */
X/* buf.c */
Xextern BUFHEAD *get_buf();
Xextern void reclaim_buf();
X
X/* big.c */
Xextern int big_split();
Xextern int big_insert();
Xextern int big_delete();
Xextern int find_bigpair();
X
X/* dynahash.c */
Xextern int call_hash();
Xextern int expand_table();
X
X/* my externals */
Xextern int get_page();
Xextern BUFHEAD *add_ovflpage();
Xextern int split_page();
Xextern int addel();
X
X/* my internals */
Xstatic u_short overflow_page();
Xstatic int open_temp();
Xstatic void squeeze_key();
Xstatic void putpair();
X
X#ifdef HASH_STATISTICS
Xextern long hash_accesses, hash_collisions, hash_expansions, hash_overflows;
X#endif
X#define PAGE_INIT(P) \
X{ \
X ((u_short *)P)[0] = 0; \
X ((u_short *)P)[1] = hashp->BSIZE - 3 * sizeof(u_short); \
X ((u_short *)P)[2] = hashp->BSIZE; \
X}
X
X/*
X This is called AFTER we have verified that there is room on the
X page for the pair (PAIRFITS has returned true) so we go right
X ahead and start moving stuff on.
X*/
Xstatic void
Xputpair(p, key, val)
Xchar *p;
XDBT *key;
XDBT *val;
X{
X register u_short n;
X register u_short off;
X register u_short *bp = (u_short *) p;
X
X/* enter the key first */
X n = bp[0];
X
X off = OFFSET(bp) - key->size;
X bcopy( key->data, p+off, key->size );
X bp[++n] = off;
X
X/* now the data */
X off -= val->size;
X bcopy(val->data, p + off, val->size);
X bp[++n] = off;
X
X/* adjust page info */
X bp[0] = n;
X bp[n+1] = off - ((n+3)*sizeof(u_short));
X bp[n+2] = off;
X return;
X}
X/*
X 0 OK
X -1 error
X*/
Xextern int
Xdelpair(bufp, ndx)
XBUFHEAD *bufp;
Xregister int ndx;
X{
X register u_short *bp = (u_short *) bufp->page;
X register int n = bp[0];
X register u_short newoff;
X u_short pairlen;
X
X if ( bp[ndx+1] < REAL_KEY ) return ( big_delete ( bufp, ndx ) );
X if ( ndx != 1 ) newoff = bp[ndx-1];
X else newoff = hashp->BSIZE;
X pairlen = newoff - bp[ndx+1];
X
X if ( ndx != (n-1) ) {
X /* Hard Case -- need to shuffle keys */
X register int i;
X register char *src = bufp->page + (int)OFFSET(bp);
X register char *dst = src + (int)pairlen;
X bcopy ( src, dst, bp[ndx+1] - OFFSET(bp) );
X
X /* Now adjust the pointers */
X for ( i = ndx+2; i <= n; i += 2 ) {
X if ( bp[i+1] == OVFLPAGE ) {
X bp[i-2] = bp[i];
X bp[i-1] = bp[i+1];
X } else {
X bp[i-2] = bp[i] + pairlen;
X bp[i-1] = bp[i+1] + pairlen;
X }
X }
X }
X
X /* Finally adjust the page data */
X bp[n] = OFFSET(bp) + pairlen;
X bp[n-1] = bp[n+1] + pairlen + 2 * sizeof(u_short);
X bp[0] = n-2;
X hashp->NKEYS--;
X
X bufp->flags |= BUF_MOD;
X return (0);
X}
X/*
X -1 ==> Error
X 0 ==> OK
X*/
Xextern int
Xsplit_page(obucket, nbucket)
Xint obucket;
Xint nbucket;
X{
X DBT key;
X DBT val;
X
X register BUFHEAD *new_bufp;
X register BUFHEAD *old_bufp;
X register u_short *ino;
X register char *np;
X char *op;
X
X u_short copyto = (u_short)hashp->BSIZE;
X u_short off = (u_short)hashp->BSIZE;
X int n;
X u_short diff;
X u_short moved;
X int ndx;
X
X old_bufp = get_buf ( obucket, NULL, 0 );
X new_bufp = get_buf ( nbucket, NULL, 0 );
X
X old_bufp->flags |= BUF_MOD;
X new_bufp->flags |= BUF_MOD;
X
X ino = (u_short *)(op = old_bufp->page);
X np = new_bufp->page;
X
X moved = 0;
X
X for (n = 1, ndx = 1; n < ino[0]; n+=2) {
X if ( ino[n+1] < REAL_KEY ) {
X return ( ugly_split( obucket, old_bufp, new_bufp,
X copyto, moved ) );
X }
X key.data = op + ino[n];
X key.size = off - ino[n];
X
X if ( call_hash ( key.data, key.size ) == obucket ) {
X /* Don't switch page */
X diff = copyto - off;
X if ( diff ) {
X copyto = ino[n+1] + diff;
X bcopy ( op + ino[n+1], op + copyto, off-ino[n+1]);
X ino[ndx] = copyto + ino[n] - ino[n+1];
X ino[ndx+1] = copyto;
X } else copyto = ino[n+1];
X ndx += 2;
X } else {
X /* Switch page */
X val.data = op + ino[n+1];
X val.size = ino[n] - ino[n+1];
X putpair( np, &key, &val);
X moved +=2;
X }
X
X off = ino[n+1];
X }
X
X /* Now clean up the page */
X ino[0] -= moved;
X FREESPACE(ino) = copyto - sizeof(u_short) * (ino[0]+3);
X OFFSET(ino) = copyto;
X
X#ifdef DEBUG3
X fprintf(stderr, "split %d/%d\n",
X ((u_short *) np)[0] / 2,
X ((u_short *) op)[0] / 2);
X#endif
X return(0);
X}
X/*
X 0 ==> success
X -1 ==> failure
X
X Called when we encounter an overflow page during split handling.
X this is special cased since we have to begin checking whether
X the key/data pairs fit on their respective pages and because
X we may need overflow pages for both the old and new pages
X*/
Xstatic int
Xugly_split( obucket, old_bufp, new_bufp, copyto, moved )
Xint obucket; /* Same as split_page */
XBUFHEAD *old_bufp;
XBUFHEAD *new_bufp;
Xu_short copyto; /* First byte on page which contains key/data values */
Xint moved; /* number of pairs moved to new page */
X{
X register BUFHEAD *bufp = old_bufp; /* Buffer header for ino */
X register u_short *ino = (u_short *)old_bufp->page;
X /* Page keys come off of */
X register u_short *np = (u_short *)new_bufp->page; /* New page */
X register u_short *op = (u_short *)old_bufp->page;
X /* Page keys go on to if they
X aren't moving */
X
X char *cino; /* Character value of ino */
X BUFHEAD *last_bfp = NULL; /* Last buffer header OVFL which
X needs to be freed */
X u_short ov_addr, last_addr = 0;
X u_short n;
X u_short off;
X
X DBT key, val;
X SPLIT_RETURN ret;
X
X n = ino[0]-1;
X while ( n < ino[0] ) {
X if ( ino[n+1] == OVFLPAGE ) {
X ov_addr = ino[n];
X /*
X Fix up the old page -- the extra 2 are the fields which
X contained the overflow information
X */
X ino[0] -= (moved + 2);
X FREESPACE(ino) = copyto - sizeof(u_short) * (ino[0]+3);
X OFFSET(ino) = copyto;
X
X bufp = get_buf ( ov_addr, bufp, 0 );
X if ( !bufp ) return(-1);
X
X ino = (u_short *)bufp->page;
X n = 1;
X off = copyto = hashp->BSIZE;
X moved = 0;
X
X if ( last_bfp ) {
X free_ovflpage( last_bfp);
X }
X last_bfp = bufp;
X }
X
X if ( (ino[2] < REAL_KEY) && (ino[2] != OVFLPAGE) ) {
X if (big_split (old_bufp, new_bufp, bufp, ov_addr, obucket, &ret)) {
X return(-1);
X }
X old_bufp = ret.oldp;
X if ( !old_bufp ) return(-1);
X op = (u_short *)old_bufp->page;
X new_bufp = ret.newp;
X if ( !new_bufp ) return(-1);
X np = (u_short *)new_bufp->page;
X bufp = ret.nextp;
X if ( !bufp ) return(0);
X cino = (char *)bufp->page;
X ino = (u_short *)cino;
X last_bfp = ret.nextp;
X }
X
X
X for ( n = 1; (n < ino[0]) && (ino[n+1] >= REAL_KEY); n += 2 ) {
X cino = (char *)ino;
X key.data = cino + ino[n];
X key.size = off - ino[n];
X val.data = cino + ino[n+1];
X val.size = ino[n] - ino[n+1];
X off = ino[n+1];
X
X if ( call_hash ( key.data, key.size ) == obucket ) {
X /* Keep on old page */
X if (PAIRFITS(op,(&key),(&val))) putpair((char *)op, &key, &val);
X else {
X old_bufp = add_ovflpage ( old_bufp );
X if ( !old_bufp ) return(-1);
X op = (u_short *)old_bufp->page;
X putpair ((char *)op, &key, &val);
X }
X old_bufp->flags |= BUF_MOD;
X } else {
X /* Move to new page */
X if (PAIRFITS(np,(&key),(&val))) putpair((char *)np, &key, &val);
X else {
X new_bufp = add_ovflpage ( new_bufp );
X if ( !new_bufp )return(-1);
X np = (u_short *)new_bufp->page;
X putpair ((char *)np, &key, &val);
X }
X new_bufp->flags |= BUF_MOD;
X }
X }
X }
X if ( last_bfp ) {
X free_ovflpage(last_bfp);
X }
X
X return (0);
X}
X/*
X Add the given pair to the page
X 1 ==> failure
X 0 ==> OK
X*/
Xextern int
Xaddel(bufp, key, val)
XBUFHEAD *bufp;
XDBT *key;
XDBT *val;
X{
X register u_short *bp = (u_short *)bufp->page;
X register u_short *sop;
X int do_expand;
X
X do_expand = 0;
X while ( bp[0] && (bp[bp[0]] < REAL_KEY) ) {
X /* Exception case */
X if ( bp[2] < REAL_KEY ) {
X /* This is a big-keydata pair */
X bufp = add_ovflpage(bufp);
X if ( !bufp ) {
X return(-1);
X }
X bp = (u_short *)bufp->page;
X } else {
X /* Try to squeeze key on this page */
X if ( FREESPACE(bp) > PAIRSIZE(key,val) ) {
X squeeze_key ( bp, key, val );
X return(0);
X } else {
X bufp = get_buf ( bp[bp[0]-1], bufp, 0 );
X if (!bufp) {
X return(-1);
X }
X bp = (u_short *)bufp->page;
X }
X }
X }
X
X if ( PAIRFITS(bp,key,val) ) putpair (bufp->page, key, val);
X else {
X do_expand = 1;
X bufp = add_ovflpage ( bufp );
X if (!bufp)return(-1);
X sop = (u_short *) bufp->page;
X
X if ( PAIRFITS(sop, key, val) ) putpair ( (char *)sop, key, val );
X else if ( big_insert ( bufp, key, val ) ) {
X return(-1);
X }
X }
X bufp->flags |= BUF_MOD;
X /*
X If the average number of keys per bucket exceeds the fill factor,
X expand the table
X */
X hashp->NKEYS++;
X if (do_expand ||
X (hashp->NKEYS / (hashp->MAX_BUCKET+1) > hashp->FFACTOR) ) {
X return(expand_table());
X }
X return(0);
X}
X
X/*
X returns a pointer, NULL on error
X*/
Xextern BUFHEAD *
Xadd_ovflpage ( bufp )
XBUFHEAD *bufp;
X{
X register u_short *sp = (u_short *)bufp->page;
X
X u_short ovfl_num;
X u_short ndx, newoff;
X char *op;
X DBT okey, oval;
X#ifdef DEBUG1
X int tmp1, tmp2;
X#endif
X
X bufp->flags |= BUF_MOD;
X ovfl_num = overflow_page ();
X#ifdef DEBUG1
X tmp1 = bufp->addr;
X tmp2 = bufp->ovfl?bufp->ovfl->addr:0;
X#endif
X if (!ovfl_num || !(bufp->ovfl = get_buf ( ovfl_num, bufp, 1 ))) {
X return(NULL);
X }
X bufp->ovfl->flags |= BUF_MOD;
X#ifdef DEBUG1
X fprintf ( stderr, "ADDOVFLPAGE: %d->ovfl was %d is now %d\n", tmp1, tmp2,
X bufp->ovfl->addr );
X#endif
X ndx = sp[0];
X /*
X Since a pair is allocated on a page only if there's room
X to add an overflow page, we know that the OVFL information
X will fit on the page
X */
X sp[ndx+4] = OFFSET(sp);
X sp[ndx+3] = FREESPACE(sp) - OVFLSIZE;
X sp[ndx+1] = ovfl_num;
X sp[ndx+2] = OVFLPAGE;
X sp[0] = ndx+2;
X#ifdef HASH_STATISTICS
X hash_overflows++;
X#endif
X return(bufp->ovfl);
X}
X
X/*
X 0 indicates SUCCESS
X -1 indicates FAILURE
X*/
Xextern int
Xget_page ( p, bucket, is_bucket, is_disk, is_bitmap )
Xchar *p;
Xint bucket;
Xint is_bucket;
Xint is_disk;
Xint is_bitmap;
X{
X register int size;
X register int fd;
X register int page;
X u_short *bp;
X int rsize;
X
X fd = hashp->fp;
X size = hashp->BSIZE;
X
X if ( !fd || (hashp->new_file && !is_disk) ) {
X PAGE_INIT(p);
X return(0);
X }
X
X if ( is_bucket) page = BUCKET_TO_PAGE (bucket);
X else page = OADDR_TO_PAGE (bucket);
X if ((lseek ( fd, page << hashp->BSHIFT, L_SET ) == -1) ||
X ((rsize = read ( fd, p, size )) == -1 )) {
X return(-1);
X }
X if ( rsize != size ) {
X errno = EFTYPE;
X return(-1);
X }
X bp = (u_short *)p;
X if (!bp[0]) {
X PAGE_INIT(p);
X } else if ( hashp->LORDER != BYTE_ORDER ) {
X register int i;
X register int max;
X
X if ( is_bitmap ) {
X max = hashp->BSIZE >> 2; /* divide by 4 */
X for ( i=0; i < max; i++ ) {
X BLSWAP(((long *)p)[i]);
X }
X } else {
X BSSWAP(bp[0]);
X max = bp[0] + 2;
X for ( i=1; i <= max; i++ ) {
X BSSWAP(bp[i]);
X }
X }
X }
X return (0);
X}
X
X/*
X Write page p to disk
X -1==>failure
X 0==> OK
X*/
Xextern int
Xput_page ( p, bucket, is_bucket, is_bitmap )
Xchar *p;
Xint bucket;
Xint is_bucket;
Xint is_bitmap;
X{
X register int size;
X register int fd;
X register int page;
X int wsize;
X
X size = hashp->BSIZE;
X if ( !hashp->fp && open_temp() ) return (1);
X fd = hashp->fp;
X
X if ( hashp->LORDER != BYTE_ORDER ) {
X register int i;
X register int max;
X
X if ( is_bitmap ) {
X max = hashp->BSIZE >> 2; /* divide by 4 */
X for ( i=0; i < max; i++ ) {
X BLSWAP(((long *)p)[i]);
X }
X } else {
X max = ((u_short *)p)[0] + 2;
X for ( i=0; i <= max; i++ ) {
X BSSWAP(((u_short *)p)[i]);
X }
X }
X }
X if (is_bucket ) page = BUCKET_TO_PAGE (bucket);
X else page = OADDR_TO_PAGE ( bucket );
X if ((lseek ( fd, page << hashp->BSHIFT, L_SET ) == -1) ||
X ((wsize = write ( fd, p, size )) == -1 )) {
X /* Errno is set */
X return(-1);
X }
X if ( wsize != size ) {
X errno = EFTYPE;
X return(-1);
X }
X return(0);
X}
X#define BYTE_MASK ((1 << INT_BYTE_SHIFT) -1)
X/*
X Initialize a new bitmap page. Bitmap pages are left in memory
X once they are read in.
X*/
Xextern u_long *
Xinit_bitmap(pnum, nbits, ndx)
Xu_short pnum;
Xint nbits;
Xint ndx;
X{
X u_long *ip;
X int clearints;
X int clearbytes;
X
X if ( !(ip = (u_long *)malloc (hashp->BSIZE)) ) return (NULL);
X clearints = ((nbits - 1) >> INT_BYTE_SHIFT) + 1;
X clearbytes = clearints << INT_TO_BYTE;
X memset ((char *)ip, 0, clearbytes );
X memset ( ((char *) ip) + clearbytes, 0xFF,
X hashp->BSIZE-clearbytes );
X ip[clearints-1] = ALL_SET << (nbits & BYTE_MASK);
X SETBIT(ip, 0);
X hashp->BITMAPS[ndx] = pnum;
X hashp->mapp[ndx] = ip;
X return(ip);
X}
Xstatic int
Xfirst_free ( map )
Xu_long map;
X{
X register u_long mask;
X register u_long i;
X
X mask = 0x1;
X for ( i=0; i < BITS_PER_MAP; i++ ) {
X if ( !(mask & map) ) return(i);
X mask = mask << 1;
X }
X return ( i );
X}
X
Xstatic u_short
Xoverflow_page ( )
X{
X register int max_free;
X register int splitnum;
X register u_long *freep;
X register int offset;
X u_short addr;
X int in_use_bits;
X int free_page, free_bit;
X int i, j, bit;
X#ifdef DEBUG2
X int tmp1, tmp2;
X#endif
X
X splitnum = log2(hashp->MAX_BUCKET);
X max_free = hashp->SPARES[splitnum];
X
X free_page = (max_free-1) >> (hashp->BSHIFT + BYTE_SHIFT);
X free_bit = (max_free-1) & ((hashp->BSIZE << BYTE_SHIFT) - 1);
X
X /* Look through all the free maps to find the first free block */
X for ( i = 0; i <= free_page; i++ ) {
X if (!(freep = (u_long *)hashp->mapp[i]) ) return(NULL);
X if ( i == free_page ) in_use_bits = free_bit;
X else in_use_bits = (hashp->BSIZE << BYTE_SHIFT) -1;
X
X for (j = 0, bit = 0; bit <= in_use_bits; j++, bit += BITS_PER_MAP ) {
X if ( freep[j] != ALL_SET ) goto found;
X }
X }
X /* No Free Page Found */
X hashp->SPARES[splitnum]++;
X offset = hashp->SPARES[splitnum] -
X (splitnum ? hashp->SPARES[splitnum-1] : 0);
X
X /* Check if we need to allocate a new bitmap page */
X if ( free_bit == (hashp->BSIZE << BYTE_SHIFT) - 1 ) {
X free_page++;
X if ( free_page >= NCACHED ) {
X fprintf ( stderr,
X "HASH: Out of overflow pages. Increase page size\n" );
X return(NULL);
X }
X /*
X This is tricky. The 1 indicates that you want the
X new page allocated with 1 clear bit. Actually, you
X are going to allocate 2 pages from this map. The first
X is going to be the map page, the second is the overflow
X page we were looking for. The init_bitmap routine
X automatically, sets the first bit of itself to indicate
X that the bitmap itself is in use. We would explicitly
X set the second bit, but don't have to if we tell init_bitmap
X not to leave it clear in the first place.
X */
X init_bitmap ( OADDR_OF(splitnum, offset), 1, free_page );
X hashp->SPARES[splitnum]++;
X#ifdef DEBUG2
X free_bit = 2;
X#endif
X offset++;
X } else {
X /*
X Free_bit addresses the last used bit. Bump it to
X address the first available bit.
X */
X free_bit++;
X SETBIT ( freep, free_bit );
X }
X
X /* Calculate address of the new overflow page */
X if ( offset > SPLITMASK ) {
X fprintf ( stderr,
X "HASH: Out of overflow pages. Increase page size\n" );
X return(NULL);
X }
X addr = OADDR_OF(splitnum, offset);
X#ifdef DEBUG2
X fprintf ( stderr, "OVERFLOW_PAGE: ADDR: %d BIT: %d PAGE %d\n",
X addr, free_bit, free_page );
X#endif
X return(addr);
X
Xfound:
X bit = bit + first_free(freep[j]);
X SETBIT(freep,bit);
X#ifdef DEBUG2
X tmp1 = bit;
X tmp2 = i;
X#endif
X /*
X Bits are addressed starting with 0, but overflow pages are
X addressed beginning at 1. Bit is a bit addressnumber, so we
X need to increment it to convert it to a page number.
X */
X bit = 1 + bit + (i * (hashp->BSIZE << BYTE_SHIFT));
X
X /* Calculate the split number for this page */
X for ( i = 0; (i < splitnum) && (bit > hashp->SPARES[i]); i++ );
X offset =(i ? bit - hashp->SPARES[i-1] : bit );
X if ( offset >= SPLITMASK ) return(NULL);/* Out of overflow pages */
X addr = OADDR_OF(i, offset);
X#ifdef DEBUG2
X fprintf ( stderr, "OVERFLOW_PAGE: ADDR: %d BIT: %d PAGE %d\n",
X addr, tmp1, tmp2 );
X#endif
X
X /* Allocate and return the overflow page */
X return (addr);
X}
X
X/*
X Mark this overflow page as free.
X*/
Xfree_ovflpage ( obufp )
XBUFHEAD *obufp;
X{
X register u_short addr = obufp->addr;
X int free_page, free_bit;
X int bit_address;
X u_short ndx;
X u_long *freep;
X int j;
X
X#ifdef DEBUG1
X fprintf ( stderr, "Freeing %d\n", addr );
X#endif
X ndx = (((u_short)addr) >> SPLITSHIFT);
X bit_address = (ndx ? hashp->SPARES[ndx-1] : 0) + (addr & SPLITMASK) - 1;
X free_page = (bit_address >> (hashp->BSHIFT + BYTE_SHIFT));
X free_bit = bit_address & ((hashp->BSIZE << BYTE_SHIFT) - 1);
X
X freep = hashp->mapp[free_page];
X assert(freep);
X CLRBIT(freep, free_bit);
X#ifdef DEBUG2
X fprintf ( stderr, "FREE_OVFLPAGE: ADDR: %d BIT: %d PAGE %d\n",
X obufp->addr, free_bit, free_page );
X#endif
X reclaim_buf ( obufp );
X return;
X}
X
X/*
X0 success
X-1 failure
X*/
Xstatic int
Xopen_temp()
X{
X char *namestr = "_hashXXXXXX";
X
X if ((hashp->fp = mkstemp ( namestr )) == -1){
X return (-1);
X }
X unlink(namestr); /* Make sure file goes away at process exit*/
X return(0);
X}
X
X/*
X We have to know that the key will fit, but the
X last entry on the page is an overflow pair, so we
X need to shift things.
X*/
Xstatic void
Xsqueeze_key ( sp, key, val )
Xu_short *sp;
XDBT *key;
XDBT *val;
X{
X register char *p = (char *)sp;
X u_short free_space, off;
X u_short pageno, n;
X
X n = sp[0];
X free_space = FREESPACE(sp);
X off = OFFSET(sp);
X
X pageno = sp[n-1];
X off -= key->size;
X sp[n-1] = off;
X bcopy ( key->data, p + off, key->size );
X off -= val->size;
X sp[n] = off;
X bcopy ( val->data, p + off, val->size );
X sp[0] = n+2;
X sp[n+1] = pageno;
X sp[n+2] = OVFLPAGE;
X FREESPACE(sp) = free_space - PAIRSIZE(key,val);
X OFFSET(sp) = off;
X}
X
X#ifdef DEBUG4
Xprint_chain ( addr )
Xshort addr;
X{
X BUFHEAD *bufp;
X short *bp;
X short oaddr;
X
X fprintf ( stderr, "%d ", addr );
X bufp = get_buf ( (int)addr, NULL, 0 );
X bp = (short *)bufp->page;
X while ( bp[0] &&
X ((bp[bp[0]] == OVFLPAGE) ||
X ((bp[0] > 2) && bp[2] < REAL_KEY))) {
X oaddr = bp[bp[0]-1];
X fprintf ( stderr, "%d ", (int)oaddr );
X bufp = get_buf ( (int)oaddr, bufp, 0 );
X bp = (short *)bufp->page;
X }
X fprintf ( stderr, "\n" );
X}
X#endif
@@@End of lq-text/src/ozmahash/page.c
echo x - lq-text/src/ozmahash/page.h 1>&2
sed 's/^X//' >lq-text/src/ozmahash/page.h <<'@@@End of lq-text/src/ozmahash/page.h'
X/*
X * Copyright (c) 1989 The Regents of the University of California.
X * All rights reserved.
X *
X * Redistribution and use in source and binary forms are permitted
X * provided that the above copyright notice and this paragraph are
X * duplicated in all such forms and that any documentation,
X * advertising materials, and other materials related to such
X * distribution and use acknowledge that the software was developed
X * by the University of California, Berkeley. The name of the
X * University may not be used to endorse or promote products derived
X * from this software without specific prior written permission.
X * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
X * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
X * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
X *
X * %W% (Berkeley) %G%
X */
X/*
X RCS INFO
X $header$
X
X Definitions for hashing page file format.
X*/
Xextern HTAB *hashp;
X/*
X * routines dealing with a data page
X *
X * page format:
X * +------------------------------+
X * p | n | keyoff | datoff | keyoff |
X * +------------+--------+--------+
X * | datoff | free | ptr | --> |
X * +--------+---------------------+
X * | F R E E A R E A |
X * +--------------+---------------+
X * | <---- - - - | data |
X * +--------+-----+----+----------+
X * | key | data | key |
X * +--------+----------+----------+
X *
X * Pointer to the free space is always: p[p[0] + 2]
X * Amount of free space on the page is: p[p[0] + 1]
X */
X
X/*
X How many bytes required for this pair?
X 2 shorts in the table at the top of the page +
X room for the key and room for the data
X
X We prohibit entering a pair on a page unless there is also
X room to append an overflow page. The reason for this it that
X you can get in a situation where a single key/data pair fits
X on a page, but you can't append an overflow page and later
X you'd have to split the key/data and handle like a big pair.
X You might as well do this up front.
X
X*/
X#define PAIRSIZE(K,D) (2*sizeof(u_short) + K->size + D->size)
X#define BIGOVERHEAD (4*sizeof(u_short))
X#define KEYSIZE(K) (4*sizeof(u_short) + K->size);
X#define OVFLSIZE (2*sizeof(u_short))
X#define FREESPACE(P) (P[P[0]+1])
X#define OFFSET(P) (P[P[0]+2])
X#define PAIRFITS(P,K,D) ((P[1] >= REAL_KEY) && \
X (PAIRSIZE(K,D) + OVFLSIZE) <= FREESPACE(P))
X#define PAGE_META(N) ((N+3) * sizeof(u_short))
X
X#define MIN(A,B) (A<=B?A:B)
X
Xtypedef struct {
X BUFHEAD *newp;
X BUFHEAD *oldp;
X BUFHEAD *nextp;
X u_short next_addr;
X} SPLIT_RETURN;
X
@@@End of lq-text/src/ozmahash/page.h
echo x - lq-text/src/ozmahash/search.h 1>&2
sed 's/^X//' >lq-text/src/ozmahash/search.h <<'@@@End of lq-text/src/ozmahash/search.h'
X/*-
X * Copyright (c) 1990 The Regents of the University of California.
X * All rights reserved.
X *
X * This code is derived from software contributed to Berkeley by
X * Margo Seltzer.
X *
X * %sccs.include.redist.c%
X *
X * %W% (Berkeley) %G%
X */
X
X/* Backward Compatibility to hsearch interface */
Xtypedef struct entry {
X char *key;
X char *data;
X} ENTRY;
X
Xtypedef enum { FIND, ENTER } ACTION;
@@@End of lq-text/src/ozmahash/search.h
if ! test -d lq-text/src/sdbm
then
cd lq-text/src
sh UseHash
fi
echo End of the last part
exit 0
--
Liam R. E. Quin, lee@sq.com, SoftQuad Inc., Toronto, +1 (416) 963-8337