Eneboo - Documentación para desarrolladores
src/libpq/include/utils/hsearch.h
Ir a la documentación de este archivo.
00001 /*-------------------------------------------------------------------------
00002  *
00003  * hsearch.h
00004  *        for hash tables, particularly hash tables in shared memory
00005  *
00006  *
00007  * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group
00008  * Portions Copyright (c) 1994, Regents of the University of California
00009  *
00010  * $PostgreSQL: pgsql/src/include/utils/hsearch.h,v 1.41 2005/10/15 02:49:46 momjian Exp $
00011  *
00012  *-------------------------------------------------------------------------
00013  */
00014 #ifndef HSEARCH_H
00015 #define HSEARCH_H
00016 
00017 
00018 /*
00019  * Hash functions must have this signature.
00020  */
00021 typedef uint32 (*HashValueFunc) (const void *key, Size keysize);
00022 
00023 /*
00024  * Key comparison functions must have this signature.  Comparison functions
00025  * return zero for match, nonzero for no match.  (The comparison function
00026  * definition is designed to allow memcmp() and strncmp() to be used directly
00027  * as key comparison functions.)
00028  */
00029 typedef int (*HashCompareFunc) (const void *key1, const void *key2,
00030                                                                                         Size keysize);
00031 
00032 /*
00033  * Key copying functions must have this signature.      The return value is not
00034  * used.  (The definition is set up to allow memcpy() and strncpy() to be
00035  * used directly.)
00036  */
00037 typedef void *(*HashCopyFunc) (void *dest, const void *src, Size keysize);
00038 
00039 /*
00040  * Space allocation function for a hashtable --- designed to match malloc().
00041  * Note: there is no free function API; can't destroy a hashtable unless you
00042  * use the default allocator.
00043  */
00044 typedef void *(*HashAllocFunc) (Size request);
00045 
00046 /*
00047  * Constants
00048  *
00049  * A hash table has a top-level "directory", each of whose entries points
00050  * to a "segment" of ssize bucket headers.      The maximum number of hash
00051  * buckets is thus dsize * ssize (but dsize may be expansible).  Of course,
00052  * the number of records in the table can be larger, but we don't want a
00053  * whole lot of records per bucket or performance goes down.
00054  *
00055  * In a hash table allocated in shared memory, the directory cannot be
00056  * expanded because it must stay at a fixed address.  The directory size
00057  * should be selected using hash_select_dirsize (and you'd better have
00058  * a good idea of the maximum number of entries!).      For non-shared hash
00059  * tables, the initial directory size can be left at the default.
00060  */
00061 #define DEF_SEGSIZE                        256
00062 #define DEF_SEGSIZE_SHIFT          8    /* must be log2(DEF_SEGSIZE) */
00063 #define DEF_DIRSIZE                        256
00064 #define DEF_FFACTOR                        1    /* default fill factor */
00065 
00066 
00067 /*
00068  * HASHELEMENT is the private part of a hashtable entry.  The caller's data
00069  * follows the HASHELEMENT structure (on a MAXALIGN'd boundary).  The hash key
00070  * is expected to be at the start of the caller's hash entry data structure.
00071  */
00072 typedef struct HASHELEMENT
00073 {
00074         struct HASHELEMENT *link;       /* link to next entry in same bucket */
00075         uint32          hashvalue;              /* hash function result for this entry */
00076 } HASHELEMENT;
00077 
00078 /* A hash bucket is a linked list of HASHELEMENTs */
00079 typedef HASHELEMENT *HASHBUCKET;
00080 
00081 /* A hash segment is an array of bucket headers */
00082 typedef HASHBUCKET *HASHSEGMENT;
00083 
00084 /* Header structure for a hash table --- contains all changeable info */
00085 typedef struct HASHHDR
00086 {
00087         long            dsize;                  /* Directory Size */
00088         long            ssize;                  /* Segment Size --- must be power of 2 */
00089         int                     sshift;                 /* Segment shift = log2(ssize) */
00090         uint32          max_bucket;             /* ID of Maximum bucket in use */
00091         uint32          high_mask;              /* Mask to modulo into entire table */
00092         uint32          low_mask;               /* Mask to modulo into lower half of table */
00093         long            ffactor;                /* Fill factor */
00094         long            nentries;               /* Number of entries in hash table */
00095         long            nsegs;                  /* Number of allocated segments */
00096         Size            keysize;                /* hash key length in bytes */
00097         Size            entrysize;              /* total user element size in bytes */
00098         long            max_dsize;              /* 'dsize' limit if directory is fixed size */
00099         int                     nelem_alloc;    /* number of entries to allocate at once */
00100         HASHELEMENT *freeList;          /* linked list of free elements */
00101 #ifdef HASH_STATISTICS
00102         long            accesses;
00103         long            collisions;
00104 #endif
00105 } HASHHDR;
00106 
00107 /*
00108  * Top control structure for a hashtable --- need not be shared, since
00109  * no fields change at runtime
00110  */
00111 typedef struct HTAB
00112 {
00113         HASHHDR    *hctl;                       /* shared control information */
00114         HASHSEGMENT *dir;                       /* directory of segment starts */
00115         HashValueFunc hash;                     /* hash function */
00116         HashCompareFunc match;          /* key comparison function */
00117         HashCopyFunc keycopy;           /* key copying function */
00118         HashAllocFunc alloc;            /* memory allocator */
00119         MemoryContext hcxt;                     /* memory context if default allocator used */
00120         char       *tabname;            /* table name (for error messages) */
00121         bool            isshared;               /* true if table is in shared memory */
00122 } HTAB;
00123 
00124 /* Parameter data structure for hash_create */
00125 /* Only those fields indicated by hash_flags need be set */
00126 typedef struct HASHCTL
00127 {
00128         long            ssize;                  /* Segment Size */
00129         long            dsize;                  /* (initial) Directory Size */
00130         long            max_dsize;              /* limit to dsize if directory size is limited */
00131         long            ffactor;                /* Fill factor */
00132         Size            keysize;                /* hash key length in bytes */
00133         Size            entrysize;              /* total user element size in bytes */
00134         HashValueFunc hash;                     /* hash function */
00135         HashCompareFunc match;          /* key comparison function */
00136         HashCopyFunc keycopy;           /* key copying function */
00137         HashAllocFunc alloc;            /* memory allocator */
00138         HASHSEGMENT *dir;                       /* directory of segment starts */
00139         HASHHDR    *hctl;                       /* location of header in shared mem */
00140         MemoryContext hcxt;                     /* memory context to use for allocations */
00141 } HASHCTL;
00142 
00143 /* Flags to indicate which parameters are supplied */
00144 #define HASH_SEGMENT    0x002   /* Set segment size */
00145 #define HASH_DIRSIZE    0x004   /* Set directory size */
00146 #define HASH_FFACTOR    0x008   /* Set fill factor */
00147 #define HASH_FUNCTION   0x010   /* Set user defined hash function */
00148 #define HASH_ELEM               0x020   /* Set key/entry size */
00149 #define HASH_SHARED_MEM 0x040   /* Hashtable is in shared memory */
00150 #define HASH_ATTACH             0x080   /* Do not initialize hctl */
00151 #define HASH_ALLOC              0x100   /* Set memory allocator */
00152 #define HASH_CONTEXT    0x200   /* Set explicit memory context */
00153 #define HASH_COMPARE    0x400   /* Set user defined comparison function */
00154 #define HASH_KEYCOPY    0x800   /* Set user defined key-copying function */
00155 
00156 
00157 /* max_dsize value to indicate expansible directory */
00158 #define NO_MAX_DSIZE                    (-1)
00159 /* max number of hash elements allocated at once */
00160 #define HASHELEMENT_ALLOC_MAX   (32)
00161 
00162 /* hash_search operations */
00163 typedef enum
00164 {
00165         HASH_FIND,
00166         HASH_ENTER,
00167         HASH_REMOVE,
00168         HASH_ENTER_NULL
00169 } HASHACTION;
00170 
00171 /* hash_seq status (should be considered an opaque type by callers) */
00172 typedef struct
00173 {
00174         HTAB       *hashp;
00175         uint32          curBucket;              /* index of current bucket */
00176         HASHELEMENT *curEntry;          /* current entry in bucket */
00177 } HASH_SEQ_STATUS;
00178 
00179 /*
00180  * prototypes for functions in dynahash.c
00181  */
00182 extern HTAB *hash_create(const char *tabname, long nelem,
00183                         HASHCTL *info, int flags);
00184 extern void hash_destroy(HTAB *hashp);
00185 extern void hash_stats(const char *where, HTAB *hashp);
00186 extern void *hash_search(HTAB *hashp, const void *keyPtr, HASHACTION action,
00187                         bool *foundPtr);
00188 extern void hash_seq_init(HASH_SEQ_STATUS *status, HTAB *hashp);
00189 extern void *hash_seq_search(HASH_SEQ_STATUS *status);
00190 extern Size hash_estimate_size(long num_entries, Size entrysize);
00191 extern long hash_select_dirsize(long num_entries);
00192 
00193 /*
00194  * prototypes for functions in hashfn.c
00195  */
00196 extern uint32 string_hash(const void *key, Size keysize);
00197 extern uint32 tag_hash(const void *key, Size keysize);
00198 extern uint32 oid_hash(const void *key, Size keysize);
00199 extern uint32 bitmap_hash(const void *key, Size keysize);
00200 extern int      bitmap_match(const void *key1, const void *key2, Size keysize);
00201 
00202 #endif   /* HSEARCH_H */
 Todo Clases Namespaces Archivos Funciones Variables 'typedefs' Enumeraciones Valores de enumeraciones Propiedades Amigas 'defines'