Source Code 1992 March

home *** CD-ROM | disk | FTP | other *** search

/ Source Code 1992 March / Source_Code_CD-ROM_Walnut_Creek_March_1992.iso / usenet / altsrcs / 2 / 2960 < prev next >

Wrap

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

From: lee@sq.sq.com (Liam R. E. Quin) Newsgroups: alt.sources Subject: lq-text Full Text Retrieval Database Part 12/13 Message-ID: <1991Mar4.021136.17015@sq.sq.com> Date: 4 Mar 91 02:11:36 GMT : 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