Source Code 1992 March/Source_Code_CD-ROM_Walnut_Creek_March_1992.iso/usenet/altsrcs/2/2961

Internet Message Format | 1991-03-04 | 42.9 KB

From: [e-mail] (Liam R. E. Quin)
Newsgroups: alt.sources
Subject: lq-text Full Text Retrieval Database Part 13/13
Message-ID: <[e-mail]>
Date: 4 Mar 91 02:12:24 GMT

: 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,  [e-mail], SoftQuad Inc., Toronto, [phone]