lee@sq.sq.com (Liam R. E. Quin) (03/04/91)
: cut here --- cut here --
: To unbundle, sh this file
#! /bin/sh
: part 12
echo x - lq-text/src/ozmahash/db.3 1>&2
sed 's/^X//' >lq-text/src/ozmahash/db.3 <<'@@@End of lq-text/src/ozmahash/db.3'
X.\" Copyright (c) 1990 The Regents of the University of California.
X.\" All rights reserved.
X.\"
X.\" Redistribution and use in source and binary forms are permitted provided
X.\" that: (1) source distributions retain this entire copyright notice and
X.\" comment, and (2) distributions including binaries display the following
X.\" acknowledgement: ``This product includes software developed by the
X.\" University of California, Berkeley and its contributors'' in the
X.\" documentation or other materials provided with the distribution and in
X.\" all advertising materials mentioning features or use of this software.
X.\" Neither the name of the University nor the names of its contributors may
X.\" be used to endorse or promote products derived from this software without
X.\" specific prior written permission.
X.\" THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR IMPLIED
X.\" WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF
X.\" MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
X.\"
X.\" @(#)db.3 5.13 (Berkeley) 1/7/91
X.\"
X.TH DB 3 "January 7, 1991"
X.UC 7
X.SH NAME
Xbtree_open, hash_open, recno_open \- database access methods
X.SH SYNOPSIS
X.nf
X.ft B
X#include <sys/types.h>
X#include <db.h>
X
XDB *
Xbtree_open(const char *file, int flags, int mode, const BTREEINFO * openinfo);
X
XDB *
Xhash_open(const char *file, int flags, int mode, const HASHINFO * openinfo);
X
XDB *
Xrecno_open(const char *file, int flags, int mode, const RECNOINFO * openinfo);
X.ft R
X.fi
X.SH DESCRIPTION
X.IR Btree_open ,
X.IR hash_open ,
Xand
X.I recno_open
Xare access method interfaces to database files in btree, hashed, and
Xflat-file formats, respectively.
XThe btree format is a representation of a sorted, balanced tree structure.
XThe hashed format is an extensible, dynamic hashing scheme.
XThe flat-file format is a UNIX file with fixed or variable length
Xlines.
XThese formats are described in more detail below.
X.PP
XAccess to all file types is based on key/data pairs.
X.PP
XEach routine opens
X.I file
Xfor reading and/or writing.
XDatabases never intended to be preserved on disk may be created by setting
Xthe file parameter to NULL.
XThe
X.I flags
Xand
X.I mode arguments
Xare as specified to the
X.IR open (2)
Xroutine, however, only the O_CREAT, O_EXCL, O_RDONLY, O_RDWR, O_TRUNC
Xand O_WRONLY flags are meaningful.
XThe argument
X.I openinfo
Xis a pointer to an access method specific structure described below.
X.PP
XThe open routines return a pointer to a DB structure on success and NULL
Xon error.
XThe DB structure contains at least the following fields:
X.PP
Xtypedef struct {
X.RS
Xvoid *openinfo;
X.br
Xint (*close)(const DB *db);
X.br
Xint (*delete)(const DB *db, const DBT *key, u_long flag);
X.br
Xint (*get)(const DB *db, DBT *key, DBT *data, u_long flag);
X.br
Xint (*put)(const DB *db, const DBT *key, const DBT *data, u_long flag);
X.br
Xint (*seq)(const DB *db, DBT *key, DBT *data, u_long flag);
X.br
Xint (*sync)(const DB *db);
X.RE
X} DB;
X.PP
XThe elements of this structure consist of a pointer to an access method
Xspecific structure and a set of routines which perform various functions.
XAll of these routines take a pointer to a structure as returned by
Xone of the open routines, one or more pointers to key/data structures,
Xand, optionally, a flag value.
X.TP
Xopeninfo
XA pointer to an internal structure specific to the access method.
X.TP
Xclose
XA pointer to a routine to flush any cached information to disk, free any
Xallocated resources, and close the database file.
XSince key/data pairs may be cached in memory, failing to close the
Xfile with a
X.I close
Xroutine may result in inconsistent or lost information.
X.I Close
Xroutines return -1 on error (setting
X.IR errno )
Xand 0 on success.
X.TP
Xdelete
XA pointer to a routine to remove key/data pairs from the database.
X.I Delete
Xroutines return -1 on error (setting
X.IR errno ),
X0 on success, and 1 if the specified
X.I key
Xwas not in the file.
X.TP
Xget
XA pointer to a routine which is the interface for keyed retrieval from
Xthe database.
XThe address and length of the data associated with the specified
X.I key
Xare returned in the structure referenced by
X.IR data .
X.I Get
Xroutines return -1 on error (setting
X.IR errno ),
X0 on success, and 1 if the
X.I key
Xwas not in the file.
X.TP
Xput
XA pointer to a routine to store key/data pairs in the database.
X.IP
XThe parameter
X.I flag
Xmust be set to one of the following values:
X.RS
X.TP
XR_IAFTER
XAppend the data immediately after the data referenced by
X.IR key ,
Xcreating a new key/data pair.
X(This implies that the access method is able to create new keys,
Xi.e. the keys are ordered and independent, for example, record numbers.
XApplicable only to the
X.B RECNO
Xaccess method.)
X.TP
XR_IBEFORE
XInsert the data immediately before the data referenced by
X.IR key ,
Xcreating a new key/data pair.
X(This implies that the access method is able to create new keys,
Xi.e. the keys are ordered and independent, for example, record numbers.
XApplicable only to the
X.B RECNO
Xaccess method.)
X.TP
XR_NOOVERWRITE
XEnter the new key/data pair only if the key does not previously exist.
X.TP
XR_PUT
XEnter the new key/data pair and replace any previously existing key.
X.RE
X.IP
X.I Put
Xroutines return -1 on error (setting
X.IR errno ),
X0 on success, and 1 if the R_NOOVERWRITE
X.I flag
Xwas set and the key already exists in the file.
X.TP
Xseq
XA pointer to a routine which is the interface for sequential
Xretrieval from the database.
XThe address and length of the key are returned in the structure
Xreferenced by
X.IR key ,
Xand the address and length of the data are returned in the
Xstructure referenced
Xby
X.IR data .
X.IP
XSequential key/data pair retrieval may begin at any time, and the
Xposition of the ``cursor'' is not affected by calls to the
X.IR delete ,
X.IR get ,
X.IR put ,
Xor
X.I sync
Xroutines.
XModifications to the database during a sequential scan will be reflected
Xin the scan, i.e. records inserted behind the cursor will not be returned
Xwhile records inserted in front of the cursor will be returned.
X.IP
XThe flag value must be set to one of the following values:
X.RS
X.TP
XR_CURSOR
XThe data associated with the specified key is returned.
XThis differs from the
X.I get
Xroutines in that it sets the ``cursor'' to the location of the
Xkey as well.
X(This implies that the access method has a implicit order which does
Xnot change.
XApplicable only to the
X.B BTREE
Xand
X.B RECNO
Xaccess methods.)
X.TP
XR_FIRST
XThe first key/data pair of the database is returned.
X.TP
XR_LAST
XThe last key/data pair of the database is returned.
X(This implies that the access method has a implicit order which does
Xnot change.
XApplicable only to the
X.B BTREE
Xand
X.B RECNO
Xaccess methods.)
X.TP
XR_NEXT
XRetrieve the key/data pair immediately after the key/data pair most recently
Xretrieved using the
X.I seq
Xroutine.
XThe cursor is moved to the returned key/data pair.
XIf
X.I flag
Xis set to R_NEXT the first time the
X.I seq
Xroutine is called, the first key/data pair of the database is returned.
X.TP
XR_PREV
XRetrieve the key/data pair immediately before the key/data pair most recently
Xretrieved using the
X.I seq
Xroutine.
XThe cursor is moved to the returned key/data pair.
XIf
X.I flag
Xis set to R_PREV the first time the
X.I seq
Xroutine is called, the last key/data pair of the database is returned.
X(This implies that the access method has a implicit order which does
Xnot change.
XApplicable only to the
X.B BTREE
Xand
X.B RECNO
Xaccess methods.)
X.RE
X.IP
X.I Seq
Xroutines return -1 on error (setting
X.IR errno ),
X0 on success, 1 if there are no more key/data pairs available.
XIf the
X.B RECNO
Xaccess method is being used, and if the database file is a character special
Xfile and no complete key/data pairs are currently available, the
X.I seq
Xroutines return 2.
X.TP
Xsync
XA pointer to a routine to flush any cached information to disk.
XIf the database is in memory only, the
X.I sync
Xroutine has no effect and will always succeed.
X.I Sync
Xroutines return -1 on error (setting
X.IR errno )
Xand 0 on success.
X.SH "KEY/DATA PAIRS"
XAccess to all file types is based on key/data pairs.
XBoth keys and data are represented by the following data structure:
X.PP
Xtypedef struct {
X.RS
Xu_char *data;
X.br
Xsize_t size;
X.RE
X} DBT;
X.PP
XThe elements of the DBT structure are defined as follows:
X.TP
Xdata
XA pointer to a byte string.
X.TP
Xsize
XThe length of the byte string.
X.PP
XKey/data strings must fit into available memory.
X.SH BTREE
XOne of the access methods is a btree: a sorted, balanced tree structure
Xwith associated key/data pairs.
X.PP
XThe access method specific data structure provided to
X.I btree_open
Xis as follows:
X.PP
Xtypedef struct {
X.RS
Xu_long flags;
X.br
Xu_int psize;
X.br
Xu_int cachesize;
X.br
Xint (*compare)(const void *, const void *);
X.br
Xint lorder;
X.RE
X} BTREEINFO;
X.PP
XThe elements of this structure are defined as follows:
X.TP
Xflags
XThe flag value is specified by
X.IR or 'ing
Xany of the following values:
X.RS
X.TP
XR_DUP
XOn insertion,
Xif the key to be inserted already exists,
Xpermit insertion anyway.
XThis flag permits duplicate keys in the tree.
XBy default,
Xduplicates are not permitted,
Xand attempts to insert them will fail.
XNote, the order of retrieval of key/data pairs with duplicate keys is
Xundefined.
X.RE
X.TP
Xcachesize
XA suggested maximum size, in bytes, of the memory cache.
XSetting this value to zero specifies that an appropriate amount of memory
Xshould be used.
XSince every search examines the root page of the tree, caching the most
Xrecently used pages substantially improves access time.
XIn addition, physical writes are delayed as long as possible, so a moderate
Xcache can reduce the number of I/O operations significantly.
XObviously, using a cache increases the likelihood of corruption or lost data
Xif the system crashes while a tree is being modified.
XHowever, caching 10
Xpages decreases the creation time of a large tree by between two and three
Xorders of magnitude.
X.TP
Xcompare
XCompare is a user defined comparison function.
XIt must return an integer less than, equal to, or greater than zero if the
Xfirst argument is considered to be respectively less than, equal to, or
Xgreater than the second.
XThe same comparison function must be used on a given tree every time it
Xis opened.
XIf no comparison function is specified,
X.IR strcmp (3)
Xis used.
X.TP
Xlorder
XThe byte order for 4-byte integers in the stored database metadata.
XThe number should represent the order as an integer; for example,
Xbig endian order would be the number 4,321.
XIf
X.I lorder
Xis 0 (no order is specified) the current host order is used.
XIf the file already exists, the specified value is ignored and the
Xvalue specified when the tree was created is used.
X(Obviously, portability of the data forming the key/data pairs is the
Xconcern of the application program.)
X.TP
Xpsize
XPage size is the size in bytes of the pages used for nodes in the tree.
XIf the file already exists, the specified value is ignored and the
Xvalue specified when the tree was created is used.
XIf
X.I psize
Xis zero, an appropriate page size is chosen (based on the system memory
Xand/or file system constraints), but will never be less than 512 bytes.
X.PP
XIf the pointer to the
X.I openinfo
Xdata structure is NULL, the
X.I btree_open
Xroutine will use appropriate values.
X.PP
XIf the database file already exists, and the O_TRUNC flag is not specified
Xto
X.IR btree_open ,
Xthe parameter
X.I psize
Xignored.
X.PP
XKey structures may reference byte strings of slightly less than one-half the
Xtree's page size only (see
X.IR psize ).
XData structures may reference byte strings of essentially unlimited length.
X.PP
XSearches, insertions, and deletions in a btree will all complete in
XO lg N.
X.PP
XForward sequential scans of a tree are from the least key to the greatest.
X.PP
XSpace freed up by deleting key/data pairs from a btree is never reclaimed,
Xalthough it is normally made available for reuse.
XThe exception to this is that space occupied by large data items (those
Xgreater than one quarter the size of a page) is neither reclaimed nor reused.
XThis means that the btree storage structure is grow-only.
XThe only solutions are to avoid excessive deletions, or to create a fresh
Xtree periodically from a scan of an existing one.
X.SH HASH
XOne of the access methods is hashed access and storage.
XThe access method specific data structure provided to
X.I hash_open
Xis as follows:
X.sp
Xtypedef struct {
X.RS
Xint bsize;
X.br
Xu_int cachesize;
X.br
Xint ffactor;
X.br
Xint nelem;
X.br
Xu_long (*hash)(const void *, const size_t);
X.br
Xint lorder;
X.RE
X} HASHINFO;
X.PP
XThe elements of this structure are defined as follows:
X.TP
Xbsize
X.I Bsize
Xdefines the hash table bucket size, and is, by default, 256 bytes.
XIt may be preferable to increase the page size for disk-resident tables and
Xtables with large data items.
X.TP
Xcachesize
XA suggested maximum size, in bytes, of the memory cache.
XSetting this value to zero specifies that an appropriate amount of memory
Xshould be used.
X.TP
Xffactor
X.I Ffactor
Xindicates a desired density within the hash table.
XIt is an approximation of the number of keys allowed to accumulate in any
Xone bucket, determining when the hash table grows or shrinks.
XThe default value is 8.
X.TP
Xhash
X.I Hash
Xis a user defined hash function.
XSince no hash function performs equally well on all possible data, the
Xuser may find that the built-in hash function does poorly on a particular
Xdata set.
XUser specified hash functions must take two arguments (a pointer to a byte
Xstring and a length) and return an u_long to be used as the hash value.
X.TP
Xlorder
XThe byte order for 4-byte integers in the stored database metadata.
XThe number should represent the order as an integer; for example,
Xbig endian order would be the number 4,321.
XIf
X.I lorder
Xis 0 (no order is specified) the current host order is used.
XIf the file already exists, the specified value is ignored and the
Xvalue specified when the tree was created is used.
X(Obviously, portability of the data forming the key/data pairs is the
Xconcern of the application program.)
X.TP
Xnelem
X.I Nelem
Xis an estimate of the final size of the hash table.
XIf not set, the default value is 1.
XIf not set or set too low, hash tables will expand gracefully as keys
Xare entered, although a slight performance degradation may be noticed.
X.PP
XIf the pointer to the
X.I openinfo
Xdata structure is NULL, the
X.I hash_open
Xroutine will use appropriate values.
X.PP
XIf the hash table already exists, and the O_TRUNC flag is not
Xspecified to
X.IR hash_open ,
Xthe parameters
X.IR bsize ,
X.IR ffactor ,
Xand
X.I nelem
Xare ignored.
X.PP
XIf a hash function is specified,
X.I hash_open
Xwill attempt to determine if the hash function specified is the same as
Xthe one with which the database was created, and will fail if it is not.
X.PP
XBoth key and data structures may reference byte strings of essentially
Xunlimited length.
X.PP
XBackward compatible interfaces to the routines described in
X.IR dbm (3),
X.IR hsearch (3),
Xand
X.IR ndbm (3)
Xare provided, however, these interfaces are not compatible with
Xprevious file formats.
X.SH RECNO
XOne of the access methods is either variable or fixed-length records,
Xthe former delimited by a specific byte value.
XThe access method specific data structure provided to
X.I recno_open
Xis as follows:
X.sp
Xtypedef struct {
X.RS
Xu_long flags;
X.br
Xu_int cachesize;
X.br
Xsize_t reclen;
X.br
Xu_char bval;
X.RE
X} RECNOINFO;
X.PP
XThe elements of this structure are defined as follows:
X.TP
Xflags
XThe flag value is specified by
X.IR or 'ing
Xany of the following values:
X.RS
X.TP
XR_FIXEDLEN
XThe records are fixed-length, not byte delimited.
XThe structure element
X.I reclen
Xspecifies the length of the record, and the structure element
X.I bval
Xis used as the pad character.
X.TP
XR_SNAPSHOT
XThis flag requires that a snapshot of the file be taken when
X.I recno_open
Xis called, instead of permitting any unmodified records to be
Xread from the original file.
X.RE
X.TP
Xcachesize
XA suggested maximum size, in bytes, of the memory cache.
XSetting this value to zero specifies that an appropriate amount of memory
Xshould be used.
X.TP
Xreclen
XThe length of a fixed-length record.
X.TP
Xbval
XThe delimiting byte to be used to mark the end of a record for
Xvariable-length records, and the pad character for fixed-length
Xrecords.
X.PP
XVariable-length and fixed-length data files require
X.I key
Xstructures to reference the following structure:
X.sp
Xtypedef struct {
X.RS
Xu_long length;
X.br
Xu_long number;
X.br
Xu_long offset;
X.br
Xu_char valid;
X.RE
X} RECNOKEY;
X.PP
XThe elements of this structure are defined as follows:
X.TP
Xlength
XThe length of the record.
X.TP
Xnumber
XThe record number.
X.TP
Xoffset
XThe offset in the file at which the record is located.
X.TP
Xvalid
XA flag value which indicates the validity of the other fields in the
Xstructure.
XThe flag value is specified by
X.IR or 'ing
Xone or more of the following values:
X.RS
X.TP
XR_LENGTH
XThe record length is valid.
X.TP
XR_NUMBER
XThe record number is valid.
X.TP
XR_OFFSET
XThe byte offset is valid.
X.RE
X.PP
XIf the record retrieval is successful, the record number, byte offset and
Xrecord length are set in the RECNOKEY structure referenced by the caller's
X.I key
Xstructure.
X.PP
XData structures may reference byte strings of essentially unlimited length.
X.SH ERRORS
XThe
X.I open
Xroutines may fail and set
X.I errno
Xfor any of the errors specified for the library routines
X.IR open (2)
Xand
X.IR malloc (3)
Xor the following:
X.TP
X[EINVAL]
XA parameter has been specified (hash function, pad byte etc.) that is
Xincompatible with the current file specification or there is a mismatch
Xbetween the version number of file and the software.
X.TP
X[EBADFORMAT]
XA file used by one of the
X.I open
Xroutines is incorrectly formatted.
X.PP
XThe
X.I close
Xroutines may fail and set
X.I errno
Xfor any of the errors specified for the library routines
X.IR close (2),
X.IR read (2),
X.IR write (2),
X.IR free (3),
Xor
X.IR fsync (2).
X.PP
XThe
X.IR delete ,
X.IR get ,
X.I put
Xand
X.I seq
Xroutines may fail and set
X.I errno
Xfor any of the errors specified for the library routines
X.IR read (2),
X.IR write (2),
X.IR free (3)
Xor
X.IR malloc (3).
X.PP
XThe
X.I sync
Xroutines may fail and set
X.I errno
Xfor any of the errors specified for the library routine
X.IR fsync (2).
X.SH "SEE ALSO"
X.IR "Dynamic Hash Tables" ,
XPer-Ake Larson, Communications of the ACM, April 1988.
X.br
X.IR "A New Hash Package for UNIX" ,
XMargo Seltzer, USENIX Proceedings, Winter 1991.
X.SH BUGS
XThe typedef DBT is a mnemonic for ``data base thang'', and was used
Xbecause noone could think of a reasonable name that wasn't already used.
X.PP
XNone of the access methods provide any form of concurrent access,
Xlocking, or transactions.
X.PP
XOnly big and little endian byte order is supported.
@@@End of lq-text/src/ozmahash/db.3
echo x - lq-text/src/ozmahash/db.h 1>&2
sed 's/^X//' >lq-text/src/ozmahash/db.h <<'@@@End of lq-text/src/ozmahash/db.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/* REMOVE THIS WHEN THIS GETS PUT ON A SYSTEM THAT HAS EFTYPE defined */
X#define EFTYPE EINVAL
X
X/* Magic Numbers */
X#define HASHMAGIC 0x61561
X
X/* flags for DB.put() call */
X#define R_APPEND 1 /* RECNO */
X#define R_DUP 2 /* BTREE */
X#define R_INSERT 3 /* RECNO */
X#define R_NOOVERWRITE 4 /* BTREE, HASH, RECNO */
X
X/* flags for DB.seq() call */
X#define R_CURSOR 1 /* BTREE, RECNO */
X#define R_FIRST 2 /* BTREE, HASH, RECNO */
X#define R_LAST 3 /* BTREE, RECNO */
X#define R_NEXT 4 /* BTREE, HASH, RECNO */
X#define R_PREV 5 /* BTREE, RECNO */
X
X/*
X Swap between big/little endian
X*/
X
X#define BLSWAP(a) { \
X long _tmp = a; \
X ((char *)&(a))[0] = ((char *)&_tmp)[3]; \
X ((char *)&(a))[1] = ((char *)&_tmp)[2]; \
X ((char *)&(a))[2] = ((char *)&_tmp)[1]; \
X ((char *)&(a))[3] = ((char *)&_tmp)[0]; \
X}
X
X#define BLSWAP_COPY(a,b) { \
X ((char *)&(b))[0] = ((char *)&(a))[3]; \
X ((char *)&(b))[1] = ((char *)&(a))[2]; \
X ((char *)&(b))[2] = ((char *)&(a))[1]; \
X ((char *)&(b))[3] = ((char *)&(a))[0]; \
X}
X#define BSSWAP(a) { \
X u_short _tmp = (a); \
X ((char *)&(a))[0] = ((char *)&_tmp)[1]; \
X ((char *)&(a))[1] = ((char *)&_tmp)[0]; \
X}
X#define BSSWAP_COPY(a,b) { \
X ((char *)&(b))[0] = ((char *)&(a))[1]; \
X ((char *)&(b))[1] = ((char *)&(a))[0]; \
X}
X
X/* key/data structure -- a data-base thang */
Xtypedef struct {
X char *data;
X int size;
X} DBT;
X
X/* access method description structure */
Xtypedef struct {
X char *internal; /* access method private; really void * */
X int (*close)();
X int (*delete)();
X int (*get)();
X int (*put)();
X int (*seq)();
X int (*sync)();
X} DB;
X
X/* structure used to pass parameters to the hashing routines */
Xtypedef struct {
X int bsize; /* bucket size */
X int ffactor; /* fill factor */
X int nelem; /* number of elements */
X int ncached; /* bytes to cache */
X int (*hash)(); /* hash function */
X int lorder; /* byte order */
X} HASHINFO;
X
X/* structure used to pass parameters to the btree routines */
Xtypedef struct {
X int cachesize; /* bytes to cache */
X int psize; /* page size */
X int (*compare); /* compare function */
X} BTREEINFO;
X
X/* structure used to pass parameters to the record routines */
Xtypedef struct {
X#define R_FIXEDLEN 0x01 /* fixed-length records */
X u_long flags;
X int cachesize; /* bytes to cache */
X size_t reclen; /* record length (fixed-length records) */
X u_char bval; /* delimiting byte (variable-length records */
X} RECNOINFO;
X
X/* key structure for the record routines */
Xtypedef struct {
X u_long number;
X u_long offset;
X u_long length;
X#define R_LENGTH 0x01 /* length is valid */
X#define R_NUMBER 0x02 /* record number is valid */
X#define R_OFFSET 0x04 /* offset is valid */
X u_char valid;
X} RECNOKEY;
X
X#if __STDC__ || c_plusplus
XDB *btree_open(const char *file, int flags, int mode, const BTREEINFO *private);
XDB *hash_open(const char *file, int flags, int mode, const HASHINFO *private);
XDB *recno_open(const char *file, int flags, int mode, const RECNOINFO *private);
X#else
XDB *btree_open();
XDB *hash_open();
XDB *recno_open();
X#endif
@@@End of lq-text/src/ozmahash/db.h
echo x - lq-text/src/ozmahash/dynahash.c 1>&2
sed 's/^X//' >lq-text/src/ozmahash/dynahash.c <<'@@@End of lq-text/src/ozmahash/dynahash.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/types.h>
X#include <sys/file.h>
X#include <sys/stat.h>
X#include <errno.h>
X#include <assert.h>
X#include <string.h>
X#include <db.h>
X#include <hash.h>
X#include <stdio.h>
X#include <endian.h>
X
X/* For systems that do not haev O_ACCMODE */
X#ifndef O_ACCMODE
X#define O_ACCMODE (O_RDONLY|O_WRONLY|O_RDWR)
X#endif
X
X/* Fast arithmetic, relying on powers of 2, */
X
X#define MOD(x,y) ((x) & ((y)-1))
X#define RETURN_ERROR(ERR,LOC) { save_errno = ERR; goto LOC; }
X
X/* Return values */
X
X#define SUCCESS 0
X#define ERROR -1
X#define ABNORMAL 1
X
X/* external routines */
Xextern char *calloc();
X
X/* page.c */
Xextern int get_page();
Xextern int split_page();
Xextern int addel();
Xextern int delpair();
Xextern u_long *init_bitmap();
X
X/* big.c */
Xextern void big_return();
Xextern int big_keydata();
Xextern u_short find_last_page();
X
X/* buf.c */
Xextern BUFHEAD *get_buf();
Xextern void buf_init();
Xextern int buf_free();
X
X/* hash function */
Xextern int (*default_hash)();
X
X/* My externals */
Xextern int expand_table();
Xextern int call_hash();
X
X/* Internal routines */
Xstatic HTAB *init_hash();
Xstatic int hash_access();
Xstatic int flush_meta();
Xstatic int alloc_segs();
Xstatic int init_htab();
Xstatic char *hash_realloc();
Xstatic int hdestroy();
Xstatic int hash_put();
Xstatic int hash_delete();
Xstatic int hash_get();
Xstatic int hash_sync();
Xstatic int hash_close();
Xstatic int hash_seq();
Xstatic void swap_header_copy();
Xstatic void swap_header();
X
X/* Local data */
X
XHTAB *hashp = NULL;
X
X#ifdef HASH_STATISTICS
Xlong hash_accesses, hash_collisions, hash_expansions, hash_overflows;
X#endif
X
X/************************** INTERFACE ROUTINES **********************/
X/* OPEN/CLOSE */
X
Xextern DB *
Xhash_open ( file, flags, mode, info )
Xchar *file;
Xint flags;
Xint mode;
XHASHINFO *info; /* Special directives for create */
X{
X int buckets;
X int bpages;
X int hdrsize;
X int i;
X int new_table = 0;
X int nkey;
X int nsegs;
X int save_errno;
X struct stat statbuf;
X DB *dbp;
X
X
X if ( !(hashp = (HTAB *) calloc( 1, sizeof(HTAB) ))) {
X /* calloc should set errno */
X return(0);
X }
X /*
X Select flags relevant to us.
X Even if user wants write only, we need to be able to read
X the actual file, so we need to open it read/write. But, the
X field in the hashp structure needs to be accurate so that
X we can check accesses.
X */
X flags = flags & (O_CREAT | O_EXCL | O_RDONLY | O_RDWR | O_TRUNC | O_WRONLY);
X hashp->flags = flags;
X if ( flags & O_WRONLY ) flags = (flags & ~O_WRONLY) | O_RDWR;
X
X if ( !file ||
X (flags & O_TRUNC) ||
X (stat ( file, &statbuf ) && (errno == ENOENT)) ) {
X new_table = 1;
X }
X
X if ( file && ((hashp->fp = open ( file, flags, mode )) == -1)) {
X RETURN_ERROR (errno, error0);
X }
X
X if ( new_table ) {
X if ( !(hashp = init_hash( info )) ) {
X RETURN_ERROR(errno,error1);
X }
X } else {
X /* Table already exists */
X if ( info && info->hash ) hashp->hash = info->hash;
X else hashp->hash = default_hash;
X
X hdrsize = read ( hashp->fp, &hashp->hdr, sizeof(HASHHDR) );
X#if BYTE_ORDER == LITTLE_ENDIAN
X swap_header ( );
X#endif
X if ( hdrsize == -1 ) {
X RETURN_ERROR(errno, error1);
X }
X if ( hdrsize != sizeof(HASHHDR) ) {
X RETURN_ERROR(EFTYPE, error1);
X }
X
X /* Verify file type, versions and hash function */
X if ( hashp->MAGIC != HASHMAGIC )
X RETURN_ERROR ( EFTYPE, error1 );
X if ( hashp->VERSION != VERSION_NO )
X RETURN_ERROR ( EFTYPE, error1 );
X if (hashp->hash ( CHARKEY, sizeof(CHARKEY) ) != hashp->H_CHARKEY ) {
X RETURN_ERROR ( EFTYPE, error1 );
X }
X
X /*
X Figure out how many segments we need.
X */
X nsegs = (hashp->MAX_BUCKET + hashp->SGSIZE -1)/ hashp->SGSIZE;
X hashp->nsegs = 0;
X if (alloc_segs( nsegs )) {
X /*
X If alloc_segs fails, table will have been destroyed
X and errno will have been set.
X */
X return( (DB *) NULL );
X }
X
X /* Read in bitmaps */
X bpages = (hashp->SPARES[log2(hashp->MAX_BUCKET)] +
X (hashp->BSIZE << BYTE_SHIFT) - 1) >>
X (hashp->BSHIFT + BYTE_SHIFT);
X
X hashp->mapp[0] = (u_long *)malloc(bpages<<hashp->BSHIFT);
X if ( !hashp->mapp[0] ) {
X RETURN_ERROR(errno, error2);
X }
X for ( i = 0; i < bpages; i++ ) {
X hashp->mapp[i] = &hashp->mapp[0][i<<hashp->BSHIFT];
X if (get_page ((char *)hashp->mapp[i], hashp->BITMAPS[i], 0, 1, 1)){
X RETURN_ERROR(errno, error2);
X }
X }
X
X }
X
X /* Initialize Buffer Manager */
X if ( info && info->ncached ) {
X buf_init (info->ncached);
X } else {
X buf_init (DEF_BUFSIZE);
X }
X
X hashp->new_file = new_table;
X hashp->save_file = (file != NULL);
X hashp->cbucket = -1;
X if ( !(dbp = (DB *)malloc ( sizeof (DB) )) ) {
X save_errno = errno;
X hdestroy();
X errno = save_errno;
X return ( NULL );
X }
X dbp->internal = (char *)hashp;
X dbp->close = hash_close;
X dbp->delete = hash_delete;
X dbp->get = hash_get;
X dbp->put = hash_put;
X dbp->seq = hash_seq;
X dbp->sync = hash_sync;
X
X#ifdef DEBUG
X (void)fprintf(stderr, "%s\n%s%x\n%s%d\n%s%d\n%s%d\n%s%d\n%s%d\n%s%d\n%s%d\n%s%x\n%s%x\n%s%d\n%s%d\n",
X "init_htab:",
X "TABLE POINTER ", hashp,
X "BUCKET SIZE ", hashp->BSIZE,
X "BUCKET SHIFT ", hashp->BSHIFT,
X "DIRECTORY SIZE ", hashp->DSIZE,
X "SEGMENT SIZE ", hashp->SGSIZE,
X "SEGMENT SHIFT ", hashp->SSHIFT,
X "FILL FACTOR ", hashp->FFACTOR,
X "MAX BUCKET ", hashp->MAX_BUCKET,
X "HIGH MASK ", hashp->HIGH_MASK,
X "LOW MASK ", hashp->LOW_MASK,
X "NSEGS ", hashp->nsegs,
X "NKEYS ", hashp->NKEYS );
X#endif
X#ifdef HASH_STATISTICS
X hash_overflows = hash_accesses = hash_collisions = hash_expansions = 0;
X#endif
X return (dbp);
X
Xerror2:
X (void)hdestroy();
X errno = save_errno;
X hashp->errno = errno;
X return ( (DB *)NULL );
X
Xerror1:
X (void) close ( hashp->fp );
X
Xerror0:
X free ( hashp );
X errno = save_errno;
X hashp->errno = errno;
X return ( (DB *) NULL );
X}
X
Xstatic int
Xhash_close (dbp)
XDB *dbp;
X{
X if ( !dbp ) {
X return(ERROR);
X }
X hashp = (HTAB *)dbp->internal;
X return (hdestroy());
X}
X
X
X/************************** LOCAL CREATION ROUTINES **********************/
Xstatic HTAB *
Xinit_hash( info )
XHASHINFO *info;
X{
X int nelem;
X
X nelem = 1;
X
X hashp->LORDER = BYTE_ORDER;
X hashp->BSIZE = DEF_BUCKET_SIZE;
X hashp->BSHIFT = DEF_BUCKET_SHIFT;
X hashp->SGSIZE = DEF_SEGSIZE;
X hashp->SSHIFT = DEF_SEGSIZE_SHIFT;
X hashp->DSIZE = DEF_DIRSIZE;
X hashp->FFACTOR = DEF_FFACTOR;
X hashp->hash = default_hash;
X bzero (hashp->SPARES, sizeof (hashp->SPARES));
X
X if ( info ) {
X if ( info->bsize ) {
X /* Round pagesize up to power of 2 */
X hashp->BSHIFT = log2(info->bsize);
X hashp->BSIZE = 1 << hashp->BSHIFT;
X if ( hashp->BSIZE > MAX_BSIZE ) {
X errno = EINVAL;
X return(0);
X }
X }
X if ( info->ffactor ) hashp->FFACTOR = info->ffactor;
X if ( info->hash ) hashp->hash = info->hash;
X if ( info->nelem ) nelem = info->nelem;
X if ( info->lorder ) {
X if ( info->lorder != BIG_ENDIAN &&
X info->lorder != LITTLE_ENDIAN) {
X errno = EINVAL;
X return(0);
X }
X hashp->LORDER = info->lorder;
X }
X }
X
X /* init_htab should destroy the table and set errno if it fails */
X if ( init_htab ( nelem ) ) {
X return(0);
X } else {
X return(hashp);
X }
X}
X
X/*
X This calls alloc_segs which may run out of memory.
X Alloc_segs will destroy the table and set errno,
X so we just pass the error information along.
X
X Returns 0 on No Error
X
X*/
Xstatic int
Xinit_htab ( nelem )
Xint nelem;
X{
X register SEGMENT *segp;
X register int nbuckets;
X register int nsegs;
X int l2;
X
X /*
X * Divide number of elements by the fill factor and determine a desired
X * number of buckets. Allocate space for the next greater power of
X * two number of buckets
X */
X nelem = (nelem - 1) / hashp->FFACTOR + 1;
X
X l2 = log2(nelem);
X nbuckets = 1 << l2;
X nbuckets = MAX ( nbuckets, 2 );
X
X hashp->SPARES[l2] = l2 + 1;
X hashp->SPARES[l2+1] = l2 + 1;
X /*
X First bitmap page is at:
X splitpoint l2
X page offset 1
X */
X init_bitmap ( OADDR_OF(l2,1), l2+1, 0 );
X
X hashp->MAX_BUCKET = hashp->LOW_MASK = nbuckets - 1;
X hashp->HIGH_MASK = (nbuckets << 1) - 1;
X hashp->HDRPAGES = ((MAX(sizeof(HASHHDR),MINHDRSIZE) - 1) >>
X hashp->BSHIFT) + 1;
X
X nsegs = (nbuckets - 1) / hashp->SGSIZE + 1;
X nsegs = 1 << log2(nsegs);
X
X if ( nsegs > hashp->DSIZE ) {
X hashp->DSIZE = nsegs;
X }
X
X return (alloc_segs ( nsegs ) );
X}
X
X/********************** DESTROY/CLOSE ROUTINES ************************/
X
X/*
X Flushes any changes to the file if necessary and
X destroys the hashp structure, freeing all allocated
X space.
X*/
Xstatic int
Xhdestroy()
X{
X int save_errno;
X int i;
X
X save_errno = 0;
X
X if (hashp != NULL) {
X#ifdef HASH_STATISTICS
X (void) fprintf(stderr, "hdestroy: accesses %ld collisions %ld\n",
X hash_accesses, hash_collisions);
X (void) fprintf(stderr, "hdestroy: expansions %ld\n",
X hash_expansions);
X (void) fprintf(stderr, "hdestroy: overflows %ld\n",
X hash_overflows);
X (void) fprintf(stderr, "keys %ld maxp %d segmentcount %d\n",
X hashp->NKEYS, hashp->MAX_BUCKET, hashp->nsegs);
X
X for ( i = 0; i < NCACHED; i++ ) {
X (void) fprintf ( stderr, "spares[%d] = %d\n", i, hashp->SPARES[i] );
X }
X#endif
X
X /*
X Call on buffer manager to free buffers, and if
X required, write them to disk
X */
X if (buf_free(1, hashp->save_file)) {
X save_errno = errno;
X }
X if ( hashp->dir ) {
X (void)free(*hashp->dir); /* Free initial segments */
X /* Free extra segments */
X while ( hashp->exsegs-- ) {
X (void)free ( hashp->dir[--hashp->nsegs] );
X }
X (void)free(hashp->dir);
X }
X if (flush_meta() && !save_errno) {
X save_errno = errno;
X }
X if ( hashp->save_file ) (void)close (hashp->fp);
X (void)free(hashp);
X hashp = NULL;
X }
X if ( save_errno ) {
X errno = save_errno;
X return(ERROR);
X } else {
X return(SUCCESS);
X }
X}
X
X/*
X Write modified pages to disk
X 0 == OK
X -1 ERROR
X*/
Xstatic int
Xhash_sync(dbp)
XDB *dbp;
X{
X if ( !dbp ) {
X return (ERROR);
X }
X
X hashp = (HTAB *)dbp->internal;
X
X if (!hashp->save_file) return(0);
X if ( buf_free ( 0, 1 ) || flush_meta()) {
X return(ERROR);
X }
X hashp->new_file = 0;
X return(0);
X}
X
X/*
X0 == OK
X-1 indicates that errno should be set
X*/
Xstatic int
Xflush_meta()
X{
X int fp;
X int hdrsize;
X int i;
X int wsize;
X HASHHDR *whdrp;
X HASHHDR whdr;
X
X if (!hashp->save_file) return(0);
X hashp->MAGIC = HASHMAGIC;
X hashp->VERSION = VERSION_NO;
X hashp->H_CHARKEY = hashp->hash ( CHARKEY, sizeof(CHARKEY));
X
X fp = hashp->fp;
X whdrp = &hashp->hdr;
X#if BYTE_ORDER == LITTLE_ENDIAN
X whdrp = &whdr;
X swap_header_copy( &hashp->hdr, whdrp );
X#endif
X if ( (lseek (fp, 0, L_SET) == -1 ) ||
X ((wsize = write ( fp, whdrp, sizeof(HASHHDR))) == -1)) {
X return(-1);
X } else if ( wsize != sizeof(HASHHDR) ) {
X errno = EFTYPE;
X hashp->errno = errno;
X return(-1);
X }
X for ( i = 0; i < NCACHED; i++ ) {
X if ( hashp->mapp[i] ) {
X if (!put_page((char *)hashp->mapp[i], hashp->BITMAPS[i], 0, 1)){
X return(-1);
X }
X }
X }
X return(0);
X}
X/*******************************SEARCH ROUTINES *****************************/
X/*
X All the access routines return
X 0 on SUCCESS
X 1 to indicate an external ERROR (i.e. key not found, etc)
X -1 to indicate an internal ERROR (i.e. out of memory, etc)
X*/
Xstatic int
Xhash_get ( dbp, key, data )
XDB *dbp;
XDBT *key, *data;
X{
X if ( !dbp ) {
X return (ERROR);
X }
X hashp = (HTAB *)dbp->internal;
X if ( hashp->flags & O_WRONLY ) {
X errno = EBADF;
X hashp->errno = errno;
X return ( ERROR );
X }
X return ( hash_access ( HASH_GET, key, data ) );
X}
X
Xstatic int
Xhash_put ( dbp, key, data, flag )
XDB *dbp;
XDBT *key, *data;
Xint flag;
X{
X if ( !dbp ) {
X return (ERROR);
X }
X hashp = (HTAB *)dbp->internal;
X if ( (hashp->flags & O_ACCMODE) == O_RDONLY ) {
X errno = EBADF;
X hashp->errno = errno;
X return ( ERROR );
X }
X if ( flag == R_NOOVERWRITE ) {
X return ( hash_access ( HASH_PUTNEW, key, data ) );
X } else {
X return ( hash_access ( HASH_PUT, key, data ) );
X }
X}
X
Xstatic int
Xhash_delete ( dbp, key, flags )
XDB *dbp;
XDBT *key;
Xint flags; /* Ignored */
X{
X if ( !dbp ) {
X return (ERROR);
X }
X hashp = (HTAB *)dbp->internal;
X if ( (hashp->flags & O_ACCMODE) == O_RDONLY ) {
X errno = EBADF;
X hashp->errno = errno;
X return ( ERROR );
X }
X return ( hash_access ( HASH_DELETE, key, NULL ) );
X}
X
X/*
X Assume that hashp has been set in wrapper routine
X*/
Xstatic int
Xhash_access(action, key, val)
XACTION action;
XDBT *key, *val;
X{
X register BUFHEAD *rbufp;
X register u_short *bp;
X register int ndx;
X register int n;
X register int off = hashp->BSIZE;
X register int size;
X register char *kp;
X BUFHEAD *bufp;
X u_short pageno;
X
X#ifdef HASH_STATISTICS
X hash_accesses++;
X#endif
X
X size = key->size;
X kp = key->data;
X rbufp = get_buf ( call_hash(key->data, size), NULL, 0 );
X if ( !rbufp ) return(ERROR);
X
X for ( bp = (u_short *)rbufp->page, n = *bp++, ndx = 1; ndx < n; ) {
X if ( bp[1] >= REAL_KEY ) {
X /* Real key/data pair */
X if (size == off - *bp &&
X bcmp(kp, rbufp->page + *bp, size) == 0) {
X goto found;
X }
X off = bp[1];
X#ifdef HASH_STATISTICS
X hash_collisions++;
X#endif
X bp += 2;
X ndx += 2;
X } else if ( bp[1] == OVFLPAGE ) {
X rbufp = get_buf ( *bp, rbufp, 0 );
X if ( !rbufp ) return (ERROR);
X /* FOR LOOP INIT */
X bp = (u_short *)rbufp->page;
X n = *bp++;
X ndx = 1;
X off = hashp->BSIZE;
X } else if ( bp[1] < REAL_KEY ) {
X if ( (ndx = find_bigpair(rbufp, ndx, kp, size )) > 0 ) {
X goto found;
X } else if ( ndx == -2 ) {
X bufp = rbufp;
X if ( !(pageno = find_last_page ( &bufp )) ) {
X ndx = 0;
X rbufp = bufp;
X break; /* FOR */
X }
X rbufp = get_buf ( pageno, bufp, 0 );
X if ( !rbufp ) return (ERROR);
X /* FOR LOOP INIT */
X bp = (u_short *)rbufp->page;
X n = *bp++;
X ndx = 1;
X off = hashp->BSIZE;
X } else {
X return(ERROR);
X }
X }
X }
X
X /* Not found */
X switch ( action ) {
X case HASH_PUT:
X case HASH_PUTNEW:
X if (addel(rbufp, key, val)) {
X return(ERROR);
X } else {
X return(SUCCESS);
X }
X case HASH_GET:
X return ( ABNORMAL );
X case HASH_DELETE:
X return ( ABNORMAL );
X default:
X return(ABNORMAL);
X }
X
Xfound:
X switch (action) {
X case HASH_PUTNEW:
X return(ABNORMAL);
X case HASH_GET:
X bp = (u_short *)rbufp->page;
X if (bp[ndx+1] < REAL_KEY) big_return(rbufp, ndx, val, 0);
X else {
X val->data = rbufp->page + (int) bp[ndx + 1];
X val->size = bp[ndx] - bp[ndx + 1];
X }
X break;
X case HASH_PUT:
X if (delpair (rbufp, ndx))return(ERROR);
X if (addel (rbufp, key, val)) return(ERROR);
X break;
X case HASH_DELETE:
X if (delpair (rbufp, ndx))return(ERROR);
X break;
X }
X return (SUCCESS);
X}
X
Xstatic int
Xhash_seq(dbp, key, data, flag)
XDB *dbp;
XDBT *key, *data;
Xint flag;
X{
X register int bucket;
X register BUFHEAD *bufp;
X u_short *bp;
X u_short ndx;
X u_short pageno;
X
X if ( !dbp ) {
X return (ERROR);
X }
X
X hashp = (HTAB *)dbp->internal;
X if ( hashp->flags & O_WRONLY ) {
X errno = EBADF;
X hashp->errno = errno;
X return ( ERROR );
X }
X#ifdef HASH_STATISTICS
X hash_accesses++;
X#endif
X
X if ( (hashp->cbucket < 0) || (flag == R_FIRST) ) {
X hashp->cbucket = 0;
X hashp->cndx = 1;
X hashp->cpage = NULL;
X }
X
X if ( !(bufp = hashp->cpage) ) {
X for (bucket = hashp->cbucket;
X bucket < hashp->MAX_BUCKET;
X bucket++, hashp->cndx = 1 ) {
X
X bufp = get_buf ( bucket, NULL, 0 );
X if (!bufp) return(ERROR);
X hashp->cpage = bufp;
X bp = (u_short *)bufp->page;
X if (bp[0]) break;
X }
X hashp->cbucket = bucket;
X if ( hashp->cbucket >= hashp->MAX_BUCKET ) {
X hashp->cbucket = -1;
X return ( ABNORMAL );
X }
X } else {
X bp = (u_short *)hashp->cpage->page;
X }
X
X#ifdef DEBUG
X assert (bp);
X assert (bufp);
X#endif
X while ( bp[hashp->cndx+1] == OVFLPAGE ) {
X bufp = hashp->cpage = get_buf ( bp[hashp->cndx], bufp, 0 );
X if (!bufp) return(ERROR);
X bp = (u_short *)(bufp->page);
X hashp->cndx = 1;
X }
X ndx = hashp->cndx;
X if (bp[ndx+1] < REAL_KEY) {
X if (big_keydata(bufp, ndx, key, data, 1)) {
X return(ERROR);
X }
X } else {
X key->data = hashp->cpage->page + bp[ndx];
X key->size = (ndx > 1 ? bp[ndx-1] : hashp->BSIZE) - bp[ndx];
X data->data = hashp->cpage->page + bp[ndx + 1];
X data->size = bp[ndx] - bp[ndx + 1];
X ndx += 2;
X if ( ndx > bp[0] ) {
X hashp->cpage = NULL;
X hashp->cbucket++;
X hashp->cndx=1;
X } else hashp->cndx = ndx;
X }
X return (SUCCESS);
X}
X
X/********************************* UTILITIES ************************/
X/*
X 0 ==> OK
X -1 ==> Error
X*/
Xextern int
Xexpand_table()
X{
X int old_bucket, new_bucket;
X int new_segnum;
X int dirsize;
X int spare_ndx;
X register char **old, **new;
X#ifdef HASH_STATISTICS
X hash_expansions++;
X#endif
X
X new_bucket = ++hashp->MAX_BUCKET;
X old_bucket = (hashp->MAX_BUCKET & hashp->LOW_MASK);
X
X new_segnum = new_bucket >> hashp->SSHIFT;
X
X /* Check if we need a new segment */
X if ( new_segnum >= hashp->nsegs ) {
X
X /* Check if we need to expand directory */
X if ( new_segnum >= hashp->DSIZE ) {
X
X /* Reallocate directory */
X dirsize = hashp->DSIZE * sizeof ( SEGMENT * );
X if (!hash_realloc ( &hashp->dir, dirsize, (dirsize << 1 ) )) {
X return(-1);
X }
X hashp->DSIZE = dirsize << 1;
X }
X if (!(hashp->dir[new_segnum] =
X (SEGMENT)calloc ( hashp->SGSIZE, sizeof(SEGMENT)))) {
X return(-1);
X }
X hashp->exsegs++;
X hashp->nsegs++;
X }
X
X /*
X If the split point is increasing (MAX_BUCKET's log
X base 2 increases), we need to copy the current contents
X of the spare split bucket to the next bucket
X */
X spare_ndx = log2(hashp->MAX_BUCKET);
X if ( spare_ndx != (log2(hashp->MAX_BUCKET - 1))) {
X hashp->SPARES[spare_ndx] = hashp->SPARES[spare_ndx-1];
X }
X
X if ( new_bucket > hashp->HIGH_MASK ) {
X /* Starting a new doubling */
X hashp->LOW_MASK = hashp->HIGH_MASK;
X hashp->HIGH_MASK = new_bucket | hashp->LOW_MASK;
X }
X
X /*
X * Relocate records to the new bucket
X */
X return(split_page ( old_bucket, new_bucket ));
X}
X/*
X If realloc guarantees that the pointer is not destroyed
X if the realloc fails, then this routine can go away
X*/
Xstatic char *
Xhash_realloc ( p_ptr, oldsize, newsize )
Xchar **p_ptr;
Xint oldsize;
Xint newsize;
X{
X register char *p;
X
X if (p = (char *)malloc ( newsize ) ) {
X bcopy ( *p_ptr, p, oldsize );
X bzero ( *p_ptr + oldsize, newsize-oldsize );
X free(*p_ptr);
X *p_ptr = p;
X }
X return (p);
X}
X
Xextern int
Xcall_hash ( k, len )
Xchar *k;
Xint len;
X{
X int n, bucket;
X n = hashp->hash(k, len);
X
X bucket = n & hashp->HIGH_MASK;
X if ( bucket > hashp->MAX_BUCKET ) {
X bucket = bucket & hashp->LOW_MASK;
X }
X
X return(bucket);
X}
X
X/*
X Allocate segment table. On error, destroy the table
X and set errno.
X
X Returns 0 on success
X*/
Xstatic int
Xalloc_segs ( nsegs )
Xint nsegs;
X{
X register int i;
X register SEGMENT store;
X
X int save_errno;
X
X if (!(hashp->dir = (SEGMENT *)calloc(hashp->DSIZE, sizeof(SEGMENT *)))) {
X save_errno = errno;
X (void)hdestroy();
X errno = save_errno;
X return(-1);
X }
X
X /* Allocate segments */
X store = (SEGMENT)calloc ( nsegs << hashp->SSHIFT, sizeof (SEGMENT) );
X if ( !store ) {
X save_errno = errno;
X (void)hdestroy();
X errno = save_errno;
X return(-1);
X }
X
X for ( i=0; i < nsegs; i++, hashp->nsegs++ ) {
X hashp->dir[i] = &store[i<<hashp->SSHIFT];
X }
X return(0);
X}
X
X/*
X Hashp->hdr needs to be byteswapped.
X*/
Xstatic void
Xswap_header_copy ( srcp, destp )
XHASHHDR *srcp;
XHASHHDR *destp;
X{
X int i;
X
X BLSWAP_COPY(srcp->magic, destp->magic);
X BLSWAP_COPY(srcp->version, destp->version);
X BLSWAP_COPY(srcp->lorder, destp->lorder);
X BLSWAP_COPY(srcp->bsize, destp->bsize);
X BLSWAP_COPY(srcp->bshift, destp->bshift);
X BLSWAP_COPY(srcp->dsize, destp->dsize);
X BLSWAP_COPY(srcp->ssize, destp->ssize);
X BLSWAP_COPY(srcp->sshift, destp->sshift);
X BLSWAP_COPY(srcp->max_bucket, destp->max_bucket);
X BLSWAP_COPY(srcp->high_mask, destp->high_mask);
X BLSWAP_COPY(srcp->low_mask, destp->low_mask);
X BLSWAP_COPY(srcp->ffactor, destp->ffactor);
X BLSWAP_COPY(srcp->nkeys, destp->nkeys);
X BLSWAP_COPY(srcp->hdrpages, destp->hdrpages);
X BLSWAP_COPY(srcp->h_charkey, destp->h_charkey);
X for ( i=0; i < NCACHED; i++ ) {
X BLSWAP_COPY ( srcp->spares[i] , destp->spares[i]);
X BSSWAP_COPY ( srcp->bitmaps[i] , destp->bitmaps[i]);
X }
X return;
X}
X
Xstatic void
Xswap_header ( )
X{
X HASHHDR *hdrp;
X int i;
X
X hdrp = &hashp->hdr;
X
X BLSWAP(hdrp->magic);
X BLSWAP(hdrp->version);
X BLSWAP(hdrp->lorder);
X BLSWAP(hdrp->bsize);
X BLSWAP(hdrp->bshift);
X BLSWAP(hdrp->dsize);
X BLSWAP(hdrp->ssize);
X BLSWAP(hdrp->sshift);
X BLSWAP(hdrp->max_bucket);
X BLSWAP(hdrp->high_mask);
X BLSWAP(hdrp->low_mask);
X BLSWAP(hdrp->ffactor);
X BLSWAP(hdrp->nkeys);
X BLSWAP(hdrp->hdrpages);
X BLSWAP(hdrp->h_charkey);
X for ( i=0; i < NCACHED; i++ ) {
X BLSWAP ( hdrp->spares[i] );
X BSSWAP ( hdrp->bitmaps[i] );
X }
X return;
X}
@@@End of lq-text/src/ozmahash/dynahash.c
echo x - lq-text/src/ozmahash/endian.h 1>&2
sed 's/^X//' >lq-text/src/ozmahash/endian.h <<'@@@End of lq-text/src/ozmahash/endian.h'
X/*
X * Copyright (c) 1987 Regents of the University of California.
X * All rights reserved.
X *
X * Redistribution and use in source and binary forms are permitted provided
X * that: (1) source distributions retain this entire copyright notice and
X * comment, and (2) distributions including binaries display the following
X * acknowledgement: ``This product includes software developed by the
X * University of California, Berkeley and its contributors'' in the
X * documentation or other materials provided with the distribution and in
X * all advertising materials mentioning features or use of this software.
X * Neither the name of the University nor the names of its contributors may
X * be used to endorse or promote products derived from this software without
X * specific prior written permission.
X * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR IMPLIED
X * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF
X * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
X *
X * @(#)endian.h 7.5 (Berkeley) 5/8/90
X */
X
X/*
X * Definitions for byte order,
X * according to byte significance from low address to high.
X */
X#define LITTLE_ENDIAN 1234 /* least-significant byte first (vax) */
X#define BIG_ENDIAN 4321 /* most-significant byte first (IBM, net) */
X#define PDP_ENDIAN 3412 /* LSB first in word, MSW first in long (pdp) */
X
X#define BYTE_ORDER LITTLE_ENDIAN /* byte order on DECSTATION */
X
X/*
X * Macros for network/external number representation conversion.
X */
X#if BYTE_ORDER == BIG_ENDIAN && !defined(lint)
X#define ntohl(x) (x)
X#define ntohs(x) (x)
X#define htonl(x) (x)
X#define htons(x) (x)
X
X#define NTOHL(x) (x)
X#define NTOHS(x) (x)
X#define HTONL(x) (x)
X#define HTONS(x) (x)
X
X#else
X
Xunsigned short ntohs(), htons();
Xunsigned long ntohl(), htonl();
X
X#define NTOHL(x) (x) = ntohl(x)
X#define NTOHS(x) (x) = ntohs(x)
X#define HTONL(x) (x) = htonl(x)
X#define HTONS(x) (x) = htons(x)
X#endif
X
@@@End of lq-text/src/ozmahash/endian.h
echo end of part 12
--
Liam R. E. Quin, lee@sq.com, SoftQuad Inc., Toronto, +1 (416) 963-8337