1/* 2 * Hash Table Data Type 3 * Copyright (C) 1997 Kaz Kylheku <kaz@ashi.footprints.net> 4 * 5 * Free Software License: 6 * 7 * All rights are reserved by the author, with the following exceptions: 8 * Permission is granted to freely reproduce and distribute this software, 9 * possibly in exchange for a fee, provided that this copyright notice appears 10 * intact. Permission is also granted to adapt this software to produce 11 * derivative works, as long as the modified versions carry this copyright 12 * notice and additional notices stating that the work has been modified. 13 * This source code may be translated into executable form and incorporated 14 * into proprietary software; there is no requirement for such software to 15 * contain a copyright notice related to this source. 16 * 17 * $Id: hash.h,v 1.2 2009-11-19 10:37:44 franklahm Exp $ 18 * $Name: $ 19 */ 20 21#ifndef ATALK_HASH_H 22#define ATALK_HASH_H 23 24#include <limits.h> 25#include <stdint.h> 26 27typedef unsigned long hashcount_t; 28#define HASHCOUNT_T_MAX ULONG_MAX 29 30typedef uint32_t hash_val_t; 31#define HASH_VAL_T_MAX UINT32_MAX 32 33extern int hash_val_t_bit; 34 35#ifndef HASH_VAL_T_BIT 36#define HASH_VAL_T_BIT ((int) hash_val_t_bit) 37#endif 38 39/* 40 * Hash chain node structure. 41 * Notes: 42 * 1. This preprocessing directive is for debugging purposes. The effect is 43 * that if the preprocessor symbol KAZLIB_OPAQUE_DEBUG is defined prior to the 44 * inclusion of this header, then the structure shall be declared as having 45 * the single member int __OPAQUE__. This way, any attempts by the 46 * client code to violate the principles of information hiding (by accessing 47 * the structure directly) can be diagnosed at translation time. However, 48 * note the resulting compiled unit is not suitable for linking. 49 * 2. This is a pointer to the next node in the chain. In the last node of a 50 * chain, this pointer is null. 51 * 3. The key is a pointer to some user supplied data that contains a unique 52 * identifier for each hash node in a given table. The interpretation of 53 * the data is up to the user. When creating or initializing a hash table, 54 * the user must supply a pointer to a function for comparing two keys, 55 * and a pointer to a function for hashing a key into a numeric value. 56 * 4. The value is a user-supplied pointer to void which may refer to 57 * any data object. It is not interpreted in any way by the hashing 58 * module. 59 * 5. The hashed key is stored in each node so that we don't have to rehash 60 * each key when the table must grow or shrink. 61 */ 62 63typedef struct hnode_t { 64 #if defined(HASH_IMPLEMENTATION) || !defined(KAZLIB_OPAQUE_DEBUG) /* 1 */ 65 struct hnode_t *hash_next; /* 2 */ 66 const void *hash_key; /* 3 */ 67 void *hash_data; /* 4 */ 68 hash_val_t hash_hkey; /* 5 */ 69 #else 70 int hash_dummy; 71 #endif 72} hnode_t; 73 74/* 75 * The comparison function pointer type. A comparison function takes two keys 76 * and produces a value of -1 if the left key is less than the right key, a 77 * value of 0 if the keys are equal, and a value of 1 if the left key is 78 * greater than the right key. 79 */ 80 81typedef int (*hash_comp_t)(const void *, const void *); 82 83/* 84 * The hashing function performs some computation on a key and produces an 85 * integral value of type hash_val_t based on that key. For best results, the 86 * function should have a good randomness properties in *all* significant bits 87 * over the set of keys that are being inserted into a given hash table. In 88 * particular, the most significant bits of hash_val_t are most significant to 89 * the hash module. Only as the hash table expands are less significant bits 90 * examined. Thus a function that has good distribution in its upper bits but 91 * not lower is preferrable to one that has poor distribution in the upper bits 92 * but not the lower ones. 93 */ 94 95typedef hash_val_t (*hash_fun_t)(const void *); 96 97/* 98 * allocator functions 99 */ 100 101typedef hnode_t *(*hnode_alloc_t)(void *); 102typedef void (*hnode_free_t)(hnode_t *, void *); 103 104/* 105 * This is the hash table control structure. It keeps track of information 106 * about a hash table, as well as the hash table itself. 107 * Notes: 108 * 1. Pointer to the hash table proper. The table is an array of pointers to 109 * hash nodes (of type hnode_t). If the table is empty, every element of 110 * this table is a null pointer. A non-null entry points to the first 111 * element of a chain of nodes. 112 * 2. This member keeps track of the size of the hash table---that is, the 113 * number of chain pointers. 114 * 3. The count member maintains the number of elements that are presently 115 * in the hash table. 116 * 4. The maximum count is the greatest number of nodes that can populate this 117 * table. If the table contains this many nodes, no more can be inserted, 118 * and the hash_isfull() function returns true. 119 * 5. The high mark is a population threshold, measured as a number of nodes, 120 * which, if exceeded, will trigger a table expansion. Only dynamic hash 121 * tables are subject to this expansion. 122 * 6. The low mark is a minimum population threshold, measured as a number of 123 * nodes. If the table population drops below this value, a table shrinkage 124 * will occur. Only dynamic tables are subject to this reduction. No table 125 * will shrink beneath a certain absolute minimum number of nodes. 126 * 7. This is the a pointer to the hash table's comparison function. The 127 * function is set once at initialization or creation time. 128 * 8. Pointer to the table's hashing function, set once at creation or 129 * initialization time. 130 * 9. The current hash table mask. If the size of the hash table is 2^N, 131 * this value has its low N bits set to 1, and the others clear. It is used 132 * to select bits from the result of the hashing function to compute an 133 * index into the table. 134 * 10. A flag which indicates whether the table is to be dynamically resized. It 135 * is set to 1 in dynamically allocated tables, 0 in tables that are 136 * statically allocated. 137 */ 138 139typedef struct hash_t { 140 #if defined(HASH_IMPLEMENTATION) || !defined(KAZLIB_OPAQUE_DEBUG) 141 struct hnode_t **hash_table; /* 1 */ 142 hashcount_t hash_nchains; /* 2 */ 143 hashcount_t hash_nodecount; /* 3 */ 144 hashcount_t hash_maxcount; /* 4 */ 145 hashcount_t hash_highmark; /* 5 */ 146 hashcount_t hash_lowmark; /* 6 */ 147 hash_comp_t hash_compare; /* 7 */ 148 hash_fun_t hash_function; /* 8 */ 149 hnode_alloc_t hash_allocnode; 150 hnode_free_t hash_freenode; 151 void *hash_context; 152 hash_val_t hash_mask; /* 9 */ 153 int hash_dynamic; /* 10 */ 154 #else 155 int hash_dummy; 156 #endif 157} hash_t; 158 159/* 160 * Hash scanner structure, used for traversals of the data structure. 161 * Notes: 162 * 1. Pointer to the hash table that is being traversed. 163 * 2. Reference to the current chain in the table being traversed (the chain 164 * that contains the next node that shall be retrieved). 165 * 3. Pointer to the node that will be retrieved by the subsequent call to 166 * hash_scan_next(). 167 */ 168 169typedef struct hscan_t { 170 #if defined(HASH_IMPLEMENTATION) || !defined(KAZLIB_OPAQUE_DEBUG) 171 hash_t *hash_table; /* 1 */ 172 hash_val_t hash_chain; /* 2 */ 173 hnode_t *hash_next; /* 3 */ 174 #else 175 int hash_dummy; 176 #endif 177} hscan_t; 178 179 180#endif /* ATALK_HASH_H */ 181