Mercurial > hg > octave-lojdl > gnulib-hg
annotate lib/hash.h @ 1032:0b6b7e10fe5f
use HASH_H, not _hash_h_ in #ifndef
fix comment: hash_rehash does *not* use hash_key_freer
(HASH_INSERT_NEW_ITEM): Take new arg: Failp.
| author | Jim Meyering <jim@meyering.net> |
|---|---|
| date | Wed, 17 Sep 1997 17:04:21 +0000 |
| parents | e34b8e81638f |
| children | aa231bb87550 |
| rev | line source |
|---|---|
|
1032
0b6b7e10fe5f
use HASH_H, not _hash_h_ in #ifndef
Jim Meyering <jim@meyering.net>
parents:
1031
diff
changeset
|
1 #ifndef HASH_H |
|
0b6b7e10fe5f
use HASH_H, not _hash_h_ in #ifndef
Jim Meyering <jim@meyering.net>
parents:
1031
diff
changeset
|
2 # define HASH_H 1 |
|
0b6b7e10fe5f
use HASH_H, not _hash_h_ in #ifndef
Jim Meyering <jim@meyering.net>
parents:
1031
diff
changeset
|
3 |
|
0b6b7e10fe5f
use HASH_H, not _hash_h_ in #ifndef
Jim Meyering <jim@meyering.net>
parents:
1031
diff
changeset
|
4 # if HAVE_CONFIG_H |
|
0b6b7e10fe5f
use HASH_H, not _hash_h_ in #ifndef
Jim Meyering <jim@meyering.net>
parents:
1031
diff
changeset
|
5 # include <config.h> |
|
0b6b7e10fe5f
use HASH_H, not _hash_h_ in #ifndef
Jim Meyering <jim@meyering.net>
parents:
1031
diff
changeset
|
6 # endif |
| 1031 | 7 |
| 8 # include <stdio.h> | |
| 9 # include <assert.h> | |
| 10 | |
|
1032
0b6b7e10fe5f
use HASH_H, not _hash_h_ in #ifndef
Jim Meyering <jim@meyering.net>
parents:
1031
diff
changeset
|
11 # ifdef STDC_HEADERS |
|
0b6b7e10fe5f
use HASH_H, not _hash_h_ in #ifndef
Jim Meyering <jim@meyering.net>
parents:
1031
diff
changeset
|
12 # include <stdlib.h> |
|
0b6b7e10fe5f
use HASH_H, not _hash_h_ in #ifndef
Jim Meyering <jim@meyering.net>
parents:
1031
diff
changeset
|
13 # else |
|
0b6b7e10fe5f
use HASH_H, not _hash_h_ in #ifndef
Jim Meyering <jim@meyering.net>
parents:
1031
diff
changeset
|
14 void free (); |
|
0b6b7e10fe5f
use HASH_H, not _hash_h_ in #ifndef
Jim Meyering <jim@meyering.net>
parents:
1031
diff
changeset
|
15 char *malloc (); |
|
0b6b7e10fe5f
use HASH_H, not _hash_h_ in #ifndef
Jim Meyering <jim@meyering.net>
parents:
1031
diff
changeset
|
16 # endif |
|
0b6b7e10fe5f
use HASH_H, not _hash_h_ in #ifndef
Jim Meyering <jim@meyering.net>
parents:
1031
diff
changeset
|
17 |
|
0b6b7e10fe5f
use HASH_H, not _hash_h_ in #ifndef
Jim Meyering <jim@meyering.net>
parents:
1031
diff
changeset
|
18 # define USE_OBSTACK |
| 1031 | 19 # ifdef USE_OBSTACK |
| 20 # include "obstack.h" | |
| 21 # endif | |
| 22 | |
|
1032
0b6b7e10fe5f
use HASH_H, not _hash_h_ in #ifndef
Jim Meyering <jim@meyering.net>
parents:
1031
diff
changeset
|
23 # define obstack_chunk_alloc malloc |
| 1031 | 24 # define obstack_chunk_free free |
| 25 | |
| 26 struct hash_ent | |
| 27 { | |
| 28 void *key; | |
| 29 struct hash_ent *next; | |
| 30 }; | |
| 31 typedef struct hash_ent HASH_ENT; | |
| 32 | |
| 33 /* This is particularly useful to cast uses in hash_initialize of the | |
| 34 system free function. */ | |
| 35 typedef void (*Hash_key_freer_type) (void *key); | |
| 36 | |
| 37 struct HT | |
| 38 { | |
| 39 /* User-supplied function for freeing keys. It is specified in | |
|
1032
0b6b7e10fe5f
use HASH_H, not _hash_h_ in #ifndef
Jim Meyering <jim@meyering.net>
parents:
1031
diff
changeset
|
40 hash_initialize. If non-null, it is used by hash_free and |
|
0b6b7e10fe5f
use HASH_H, not _hash_h_ in #ifndef
Jim Meyering <jim@meyering.net>
parents:
1031
diff
changeset
|
41 hash_clear. You should specify `free' here only if you want |
|
0b6b7e10fe5f
use HASH_H, not _hash_h_ in #ifndef
Jim Meyering <jim@meyering.net>
parents:
1031
diff
changeset
|
42 these functions to free all of your `key' data. This is typically |
|
0b6b7e10fe5f
use HASH_H, not _hash_h_ in #ifndef
Jim Meyering <jim@meyering.net>
parents:
1031
diff
changeset
|
43 the case when your key is simply an auxilliary struct that you |
|
0b6b7e10fe5f
use HASH_H, not _hash_h_ in #ifndef
Jim Meyering <jim@meyering.net>
parents:
1031
diff
changeset
|
44 have malloc'd to aggregate several values. */ |
| 1031 | 45 Hash_key_freer_type hash_key_freer; |
| 46 | |
| 47 /* User-supplied hash function that hashes entry E to an integer | |
| 48 in the range 0..TABLE_SIZE-1. */ | |
| 49 unsigned int (*hash_hash) (const void *e, unsigned int table_size); | |
| 50 | |
| 51 /* User-supplied function that determines whether a new entry is | |
| 52 unique by comparing the new entry to entries that hashed to the | |
| 53 same bucket index. It should return zero for a pair of entries | |
| 54 that compare equal, non-zero otherwise. */ | |
| 55 | |
| 56 int (*hash_key_comparator) (const void *, const void *); | |
| 57 | |
| 58 HASH_ENT **hash_table; | |
| 59 unsigned int hash_table_size; | |
| 60 unsigned int hash_n_slots_used; | |
| 61 unsigned int hash_max_chain_length; | |
| 62 | |
| 63 /* Gets set when an entry is deleted from a chain of length | |
| 64 hash_max_chain_length. Indicates that hash_max_chain_length | |
| 65 may no longer be valid. */ | |
| 66 unsigned int hash_dirty_max_chain_length; | |
| 67 | |
| 68 /* Sum of lengths of all chains (not counting any dummy | |
| 69 header entries). */ | |
| 70 unsigned int hash_n_keys; | |
| 71 | |
| 72 /* A linked list of freed HASH_ENT structs. | |
| 73 FIXME: Perhaps this is unnecessary and we should simply free | |
| 74 and reallocate such structs. */ | |
| 75 HASH_ENT *hash_free_entry_list; | |
| 76 | |
| 77 /* FIXME: comment. */ | |
| 78 # ifdef USE_OBSTACK | |
| 79 struct obstack ht_obstack; | |
| 80 # endif | |
| 81 }; | |
| 82 | |
| 83 typedef struct HT HT; | |
| 84 | |
| 85 unsigned int | |
| 86 hash_get_n_slots_used (const HT *ht); | |
| 87 | |
| 88 unsigned int | |
| 89 hash_get_max_chain_length (HT *ht); | |
| 90 | |
| 91 int | |
| 92 hash_rehash (HT *ht, unsigned int new_table_size); | |
| 93 | |
| 94 unsigned int | |
| 95 hash_get_table_size (const HT *ht); | |
| 96 | |
| 97 HT * | |
| 98 hash_initialize (unsigned int table_size, | |
| 99 void (*key_freer) (void *key), | |
| 100 unsigned int (*hash) (const void *, unsigned int), | |
| 101 int (*equality_tester) (const void *, const void *)); | |
| 102 | |
| 103 unsigned int | |
| 104 hash_get_n_keys (const HT *ht); | |
| 105 | |
| 106 int | |
| 107 hash_query_in_table (const HT *ht, const void *e); | |
| 108 | |
| 109 void * | |
| 110 hash_lookup (const HT *ht, const void *e); | |
| 111 | |
| 112 void * | |
| 113 hash_insert_if_absent (HT *ht, const void *e, int *failed); | |
| 114 | |
| 115 void * | |
| 116 hash_delete_if_present (HT *ht, const void *e); | |
| 117 | |
| 118 void | |
| 119 hash_print_statistics (const HT *ht, FILE *stream); | |
| 120 | |
| 121 int | |
| 122 hash_get_statistics (const HT *ht, unsigned int *n_slots_used, | |
| 123 unsigned int *n_keys, | |
| 124 unsigned int *max_chain_length); | |
| 125 | |
| 126 int | |
| 127 hash_table_ok (HT *ht); | |
| 128 | |
| 129 void | |
| 130 hash_do_for_each (HT *ht, void (*f) (void *e, void *aux), void *aux); | |
| 131 | |
| 132 int | |
| 133 hash_do_for_each_2 (HT *ht, int (*f) (void *e, void *aux), void *aux); | |
| 134 | |
| 135 int | |
| 136 hash_do_for_each_in_selected_bucket (HT *ht, const void *key, | |
| 137 int (*f) (const void *bucket_key, | |
| 138 void *e, void *aux), | |
| 139 void *aux); | |
| 140 | |
| 141 void | |
| 142 hash_clear (HT *ht); | |
| 143 | |
| 144 void | |
| 145 hash_free (HT *ht); | |
| 146 | |
| 147 void | |
| 148 hash_get_key_list (const HT *ht, unsigned int bufsize, void **buf); | |
| 149 | |
| 150 void * | |
| 151 hash_get_first (const HT *ht); | |
| 152 | |
| 153 void * | |
| 154 hash_get_next (const HT *ht, const void *e); | |
| 155 | |
| 156 /* This interface to hash_insert_if_absent is used frequently enough to | |
| 157 merit a macro here. */ | |
| 158 | |
|
1032
0b6b7e10fe5f
use HASH_H, not _hash_h_ in #ifndef
Jim Meyering <jim@meyering.net>
parents:
1031
diff
changeset
|
159 # define HASH_INSERT_NEW_ITEM(Ht, Item, Failp) \ |
| 1031 | 160 do \ |
| 161 { \ | |
|
1032
0b6b7e10fe5f
use HASH_H, not _hash_h_ in #ifndef
Jim Meyering <jim@meyering.net>
parents:
1031
diff
changeset
|
162 void *_already; \ |
|
0b6b7e10fe5f
use HASH_H, not _hash_h_ in #ifndef
Jim Meyering <jim@meyering.net>
parents:
1031
diff
changeset
|
163 _already = hash_insert_if_absent ((Ht), (Item), Failp); \ |
|
0b6b7e10fe5f
use HASH_H, not _hash_h_ in #ifndef
Jim Meyering <jim@meyering.net>
parents:
1031
diff
changeset
|
164 assert (_already == NULL); \ |
| 1031 | 165 } \ |
| 166 while (0) | |
| 167 | |
|
1032
0b6b7e10fe5f
use HASH_H, not _hash_h_ in #ifndef
Jim Meyering <jim@meyering.net>
parents:
1031
diff
changeset
|
168 #endif /* HASH_H */ |