⟦6e6742b59⟧

TextFile

/* gdbm.h  -  The include file for dbm.  Defines structure and constants. */

/*  GNU DBM  - DataBase Manager (database subroutines) by Philip A. Nelson
    Copyright (C) 1989  Free Software Foundation, Inc.

    This program is free software; you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program; if not, write to the Free Software
    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.

    You may contact the author by:
       e-mail:  phil@wwu.edu
      us-mail:  Philip A. Nelson
                Computer Science Department
                Western Washington University
                Bellingham, WA 98226
        phone:  (206) 676-3035
       
*************************************************************************/



/* Start with the constant definitions.  */
#define  TRUE    1
#define  FALSE   0
#define  DBM_READER 0
#define  DBM_WRITER 1


/* The type definitions are next.  */

/* The data and key structure.  This structure is defined for compatibility.  */
typedef struct {
	char *dptr;
	int   dsize;
      } datum;



/* The dbm file header keeps track of the current location of the hash directory
   and the free space in the file.  */

#define AVAIL_SIZE 17
#define AVAIL_BITS  3

typedef struct {
	int   dir;		/* File address of hash directory table.  */
	int   dir_size;		/* Size in bytes of the table.  */
	int   dir_bits;		/* The number of address bits used in the table.  */
	int   file_size;	/* The size of the complete file.  */
	int   block_size;	/* The  optimal i/o blocksize from stat. */
	int   bucket_elems;	/* Number of elements in a hash bucket. */
	int   bucket_size;	/* Size in bytes of a hash bucket struct. */
	int   avail_list[AVAIL_SIZE];  /* Addresses of the avail list structure.  */
	int   header_magic;     /* 0x13579ace to make sure the header is good. */
	int   update_state;     /* 0x00000000 indicates no change in progress.
				   0x777777yy indicates a change is in progress.
				   yy is the number of the change.
				   yy - procedure   - update
				   01 - _file_alloc - updating current
				   02 - _file_alloc - allocating at end of file
				   03 - _dbm_free   - adding element to avail
				   04 - _dbm_free   - sharing with previous
				   05 - _dbm_free   - sharing with next
				   06 - _dbm_free   - splitting current
				   07 - gdbm_store  - writing data to file
				   08 - split_current- splitting a bucket
				   09 - gdbm_delete - updating a bucket
				      For more information see dbmopen.c. */
	int  upd_param1;	/* These are update parameters.  Their meanings */
	int  upd_param2;	/* vary with which update is in progress.  For */
	int  upd_param3;	/* full meanings see dbmopen.c where crash  */
	int  upd_param4;	/* recovery uses these values to recover. */
      }  dbm_file_header;


/* The dbm hash bucket element contains the full 31 bit hash value, the "pointer"
   to the key and data (stored together) with their sizes.  It also has a small
   part of the actual key value.  It is used to verify the first part of the key
   has the correct value without having to read the actual key. */

#define SMALL    16

typedef struct {
	int   hash_value;	/* The complete 31 bit value. */
	char  key_start[SMALL];	/* Up to the first SMALL bytes of the key.  */
	int   data_pointer;	/* The file address of the key record. The
				   data record directly follows the key.  */
	int   key_size;		/* Size of key data in the file. */
	int   data_size;	/* Size of associated data in the file. */
      } bucket_element;


/* A bucket is a small hash table.  This one consists of a number of  bucket
   elements plus some bookkeeping fields.  The number of elements depends on
   the optimum blocksize for the storage device.  This bucket takes one block.
   When one of these tables gets full, it is split into two hash buckets.
   The contents are split between them by the use of the first few bits of
   the 31 bit hash function.  The location in a bucket is the hash value modulo
   the size of the bucket.  The in-memory images of the buckets are allocated
   by malloc using a calculated size depending of the file system buffer size. */

typedef struct {
	int   bucket_bits;	   /* The number of uper bits used to get here. */
	int   count;		   /* The number of element buckets full. */
	bucket_element h_table[1]; /* The table.  Make it look like an array. */
      } hash_bucket;


/* To speed up the free space allocation, we store the "avail list" in a table.
   This allows reading/writing of only the "avail list" tables instead of the
   actual avaliable blocks in the file.  The first avail table is 1/2 a file
   system buffer.  All after that are full file sysem buffers. */

/* The following structure is the element of the avaliable table.  */
typedef struct {
  	int  av_size;		/* The size of the available block. */
	int  av_adr;		/* The file address of the available block. */
      } avail_elem;

/* This is the actual table. The in-memory images of the avail blocks are
   allocated by malloc using a calculated size.  */
typedef struct {
	int  size;		/* The number of avail elements in the table. */
	int  count;		/* The number of entries in the table. */
	int  next_block;	/* The file address of the next avail block. */
	int  prev_block;	/* The file address of the previous avail block. */
	avail_elem av_table[1]; /* The table.  Make it look like an array.  */
      } avail_block;



/* This final structure contains all main memory based information for a dbm file.
   This allows multiple dbm files to be opened at the same time by one program. */

typedef struct {
	/* Global variables and pointers to dynamic variables used by dbm.  */

  	/* The complete file name including the ".dbm" extension.  */
	char *name;

	/* The dbm file descriptor which is set in dbminit.  */
	int  desc;

	/* The file header holds information about the database. */
	dbm_file_header header;

	/* The hash table directory from extendible hashing.  See Fagin et al, 
	   ACM Trans on Database Systems, Vol 4, No 3. Sept 1979, 315-344 */
	int  *dir;

	/* The variable to hold one bucket while in use. */
	hash_bucket *bucket;

	/* The address in the file of the current hash bucket. */
	int bucket_adr;

	/* The directory entry used to get the current hash bucket. */
	int bucket_dir;

	/* The current avail block. */
	avail_block *avail;

	/* The file address of the current avail block. */
	int avail_adr;

	/* The reader/writer status. */
	int read_write;

	/* The fatal error handling routine. */
	void (*fatal_err) ();

      } dbm_file_info;
DataMuseum.dk

DKUUG/EUUG Conference tapes

⟦6e6742b59⟧ TextFile

Derivation

TextFile
