home *** CD-ROM | disk | FTP | other *** search
/ Complete Linux / Complete Linux.iso / docs / apps / database / postgres / postgre4.z / postgre4 / src / lib / H / utils / hsearch.h < prev    next >
Encoding:
C/C++ Source or Header  |  1992-08-27  |  3.9 KB  |  131 lines
  1. /*
  2.  *  hsearch.h --
  3.  *    for hashing in the new buffer manager
  4.  *
  5.  *  Identification:
  6.  *      $Header: /private/postgres/src/lib/H/utils/RCS/hsearch.h,v 1.6 1992/03/30 00:11:43 mer Exp $
  7. */
  8.  
  9. #ifndef HSearchIncluded
  10. #define HSearchIncluded
  11.  
  12. #include "tmp/postgres.h"
  13.  
  14. /*
  15.  * Constants
  16.  */
  17. # define DEF_BUCKET_SIZE    256
  18. # define DEF_BUCKET_SHIFT    8    /* log2(BUCKET) */
  19. # define DEF_SEGSIZE        256
  20. # define DEF_SEGSIZE_SHIFT        8      /* log2(SEGSIZE)     */
  21. # define DEF_DIRSIZE        256
  22. # define PRIME1            37
  23. # define PRIME2            1048583
  24. # define DEF_FFACTOR        1
  25. # define SPLTMAX        8
  26.  
  27.  
  28. /*
  29.  * Hash bucket is actually bigger than this.  Key field can have
  30.  * variable length and a variable length data field follows it.
  31.  */
  32. typedef struct element {
  33.     unsigned int next;           /* secret from user     */
  34.     int key;
  35. } ELEMENT;
  36.  
  37. typedef unsigned int BUCKET_INDEX;
  38. /* segment is an array of bucket pointers  */
  39. typedef BUCKET_INDEX *SEGMENT;
  40. typedef unsigned int SEG_OFFSET;
  41.  
  42. typedef struct hashhdr {
  43.     int bsize;    /* Bucket/Page Size */
  44.     int bshift;    /* Bucket shift */
  45.     int dsize;    /* Directory Size */
  46.     int ssize;    /* Segment Size */
  47.     int sshift;    /* Segment shift */
  48.     int max_bucket;    /* ID of Maximum bucket in use */
  49.     int high_mask;    /* Mask to modulo into entire table */
  50.     int low_mask;    /* Mask to modulo into lower half of table */
  51.     int ffactor;    /* Fill factor */
  52.     int nkeys;    /* Number of keys in hash table */
  53.     int nsegs;    /* Number of allocated segments */
  54.     int keysize;    /* hash key length in bytes */
  55.     int datasize;    /* elem data length in bytes */
  56.     int max_dsize;  /* 'dsize' limit if directory is fixed size */ 
  57.     BUCKET_INDEX freeBucketIndex;
  58.             /* index of first free bucket */
  59. #ifdef HASH_STATISTICS
  60.     int accesses;
  61.     int collisions;
  62. #endif
  63. } HHDR;
  64.  
  65. typedef struct htab {
  66.       HHDR        *hctl;     /* shared control information */
  67.     int         (*hash)(); /* Hash Function */
  68.     char *         segbase;   /* segment base address for 
  69.                     * calculating pointer values */
  70.     SEG_OFFSET    *dir;       /* 'directory' of segm starts */
  71.     int *        (*alloc)();/* memory allocator */
  72.     /* int * for alignment reasons */
  73.  
  74. } HTAB;
  75.  
  76. typedef struct hashctl {
  77.     int bsize;    /* Bucket Size */
  78.     int ssize;    /* Segment Size */
  79.     int dsize;    /* Dirsize Size */
  80.     int ffactor;    /* Fill factor */
  81.     int (*hash)();    /* Hash Function */
  82.     int keysize;    /* hash key length in bytes */
  83.     int datasize;    /* elem data length in bytes */
  84.     int max_size;  /* limit to dsize if directory size is limited */
  85.     int *segbase;  /* base for calculating bucket + seg ptrs */
  86.     int * (*alloc)(); /* memory allocation function */
  87.     int *dir;    /* directory if allocated already */
  88.     int *hctl;    /* location of header information in shd mem */
  89. } HASHCTL;
  90.  
  91. /* Flags to indicate action for hctl */
  92. #define HASH_BUCKET    0x001    /* Setting bucket size */
  93. #define HASH_SEGMENT    0x002    /* Setting segment size */
  94. #define HASH_DIRSIZE    0x004    /* Setting directory size */
  95. #define HASH_FFACTOR    0x008    /* Setting fill factor */
  96. #define HASH_FUNCTION    0x010    /* Set user defined hash function */
  97. #define HASH_ELEM    0x020    /* Setting key/data size */
  98. #define HASH_SHARED_MEM 0x040   /* Setting shared mem const */
  99. #define HASH_ATTACH    0x080   /* Do not initialize hctl */
  100. #define HASH_ALLOC    0x100   /* Setting memory allocator */ 
  101.  
  102.  
  103. /* seg_alloc assumes that INVALID_INDEX is 0*/
  104. #define INVALID_INDEX         (0)
  105. #define NO_MAX_DSIZE         (-1)
  106. /* number of hash buckets allocated at once */
  107. #define BUCKET_ALLOC_INCR    (30)
  108.  
  109. /* hash_search operations */
  110. typedef enum { HASH_FIND, HASH_ENTER, HASH_REMOVE, HASH_FIND_SAVE, HASH_REMOVE_SAVED } HASHACTION;
  111.  
  112. /* entry points */
  113. HTAB *hash_create ARGS((int nelem , HASHCTL *info , int flags ));
  114. void hash_destroy ARGS((HTAB *hashp ));
  115. void hash_stats ARGS((char *where , HTAB *hashp ));
  116. int *hash_seq ARGS((HTAB *hashp ));
  117. int *hash_search ARGS((
  118.     HTAB *hashp,
  119.     char *keyPtr,
  120.     HASHACTION action,
  121.     Boolean *foundPtr
  122. ));
  123.  
  124. /* hash functions from hashfn.c */
  125.  
  126. int string_hash ARGS((char *key, int keysize ));
  127. int tag_hash ARGS((int *key, int keysize ));
  128. int disk_hash ARGS((char *key ));
  129.  
  130. #endif
  131.