PERFORCE change 120388 for review
Fredrik Lindberg
fli at FreeBSD.org
Fri May 25 16:15:12 UTC 2007
http://perforce.freebsd.org/chv.cgi?CH=120388
Change 120388 by fli at fli_genesis on 2007/05/25 16:14:49
- Make the hash table self-growing
- New pre-allocation scheme
- Various minor optimizations
Affected files ...
.. //depot/projects/soc2007/fli-mdns_sd/mdnsd/hash.c#3 edit
.. //depot/projects/soc2007/fli-mdns_sd/mdnsd/hash.h#3 edit
Differences ...
==== //depot/projects/soc2007/fli-mdns_sd/mdnsd/hash.c#3 (text+ko) ====
@@ -76,7 +76,7 @@
* the return value. Two keys differing by one or two bits will have
* totally different hash values.
*/
-static uint32_t
+static inline uint32_t
hash(const void *key, size_t length, uint32_t initval)
{
uint32_t a, b, c; /* internal state */
@@ -224,25 +224,82 @@
* This chunk is then split into `entries' number of table entries and put
* on the free list.
*/
+static inline struct hashentry *
+alloc_he(struct hashtbl *ht)
+{
+ struct he_pool *hep;
+ struct hashentry *he;
+ uint32_t len;
+
+ if (!SLIST_EMPTY(&ht->ht_free)) {
+ hep = SLIST_FIRST(&ht->ht_free);
+ SLIST_REMOVE_HEAD(&ht->ht_free, hep_next);
+ return ((struct hashentry *)hep);
+ }
+
+ hep = SLIST_FIRST(&ht->ht_new);
+ if (hep == NULL || hep->hep_pos >= hep->hep_size) {
+ len = 1 << ht->ht_alloc_size;
+ hep = malloc(sizeof(struct he_pool) + (sizeof(struct hashentry) * len));
+ hep->hep_size = len;
+ hep->hep_pos = 0;
+ SLIST_INSERT_HEAD(&ht->ht_new, hep, hep_next);
+
+ if (ht->ht_alloc_size < 16)
+ ht->ht_alloc_size++;
+ }
+
+ he = (struct hashentry *)((char *)hep + sizeof(struct he_pool));
+ he = &he[hep->hep_pos];
+ hep->hep_pos++;
+ return (he);
+}
+
+/*
+ * Return an hashentry object for further use
+ */
+static inline void
+free_he(struct hashtbl *ht, struct hashentry *he)
+{
+ struct he_pool *hep;
+
+ /* This cast is safe as long as he_pool is smaller than hashentry */
+ hep = (struct he_pool *)he;
+ SLIST_INSERT_HEAD(&ht->ht_free, hep, hep_next);
+}
+
+/*
+ * Self-grow hash table, called if the number of collisions are too large
+ */
static void
-pre_alloc(struct hashtbl *ht)
+grow(struct hashtbl *ht)
{
- struct hashentry *chunk;
- int i, entries;
-
- entries = ht->ht_entries == 0 ? (ht->ht_tblsz / 2) : ht->ht_entries;
+ struct hashbkt *buckets;
+ struct hashentry *he, *he2;
+ size_t i, len;
+ uint32_t hval;
- ht->ht_chunk = realloc(ht->ht_chunk,
- sizeof(struct hashentry *) * (ht->ht_chunks + 1));
+ len = ht->ht_tblsz;
+ ht->ht_tblsz *= 2;
+ ht->ht_mask = ht->ht_tblsz - 1;
- chunk = ht->ht_chunk[ht->ht_chunks];
- chunk = malloc(sizeof(struct hashentry) * entries);
+ buckets = malloc(sizeof(struct hashbkt) * ht->ht_tblsz);
+ for (i = 0; i < ht->ht_tblsz; i++) {
+ TAILQ_INIT(&buckets[i].hb_table);
+ buckets[i].hb_len = 0;
+ }
- for (i = 0; i < entries; i++) {
- TAILQ_INSERT_TAIL(&ht->ht_free, &chunk[i], he_next);
+ for (i = 0; i < len; i++) {
+ TAILQ_FOREACH_SAFE(he, &ht->ht_buckets[i].hb_table, he_next, he2) {
+ hval = he->he_hash & ht->ht_mask;
+ TAILQ_REMOVE(&ht->ht_buckets[i].hb_table, he, he_next);
+ TAILQ_INSERT_TAIL(&buckets[hval].hb_table, he, he_next);
+ buckets[hval].hb_len++;
+ }
}
- ht->ht_chunk[ht->ht_chunks++] = chunk;
+ free(ht->ht_buckets);
+ ht->ht_buckets = buckets;
}
/*
@@ -251,22 +308,24 @@
* len - table entries, should be a power of 2
*/
int
-hashtbl_init(struct hashtbl *ht, size_t len)
+hashtbl_init(struct hashtbl *ht, size_t len, size_t grow, size_t col)
{
size_t i;
- bzero(ht, sizeof(struct hashtbl));
- ht->ht_table = malloc(sizeof(*ht->ht_table) * len);
+ ht->ht_buckets = malloc(sizeof(struct hashbkt) * len);
ht->ht_tblsz = len;
+ ht->ht_grow = grow;
+ ht->ht_col = col;
ht->ht_mask = len - 1;
- ht->ht_entries = 0;
+ ht->ht_alloc_size = 0;
+ SLIST_INIT(&ht->ht_new);
+ SLIST_INIT(&ht->ht_free);
for (i = 0; i < len; i++) {
- TAILQ_INIT(&ht->ht_table[i]);
+ TAILQ_INIT(&ht->ht_buckets[i].hb_table);
+ ht->ht_buckets[i].hb_len = 0;
}
- TAILQ_INIT(&ht->ht_free);
- pre_alloc(ht);
return (0);
}
@@ -277,18 +336,18 @@
hashtbl_destroy(struct hashtbl *ht)
{
struct hashentry *he;
+ struct he_pool *hep, *hep2;
size_t i;
for (i = 0; i < ht->ht_tblsz; i++) {
- TAILQ_FOREACH(he, &ht->ht_table[i], he_next) {
+ TAILQ_FOREACH(he, &ht->ht_buckets[i].hb_table, he_next) {
free(he->he_key);
}
}
-
- for (i = 0; i < ht->ht_chunks; i++) {
- free(ht->ht_chunk[i]);
+ SLIST_FOREACH_SAFE(hep, &ht->ht_new, hep_next, hep2) {
+ free(hep);
}
- free(ht->ht_table);
+ free(ht->ht_buckets);
}
/*
@@ -303,7 +362,7 @@
{
struct hashentry *he;
- TAILQ_FOREACH(he, &ht->ht_table[hval], he_next) {
+ TAILQ_FOREACH(he, &ht->ht_buckets[hval].hb_table, he_next) {
if (keylen == he->he_keylen) {
if (memcmp(key, he->he_key, keylen) == 0)
break;
@@ -327,25 +386,27 @@
uint32_t hval;
struct hashentry *he;
- hval = hash(key, keylen, time(NULL));
- hval &= ht->ht_mask;
-
- he = find(ht, hval, key, keylen);
+ hval = hash(key, keylen, 0);
+ he = find(ht, hval & ht->ht_mask, key, keylen);
if (he != NULL)
return (-1);
- if (TAILQ_EMPTY(&ht->ht_free)) {
- pre_alloc(ht);
- }
+ he = alloc_he(ht);
- he = TAILQ_FIRST(&ht->ht_free);
- TAILQ_REMOVE(&ht->ht_free, he, he_next);
+ he->he_hash = hval;
+ hval &= ht->ht_mask;
he->he_key = malloc(keylen);
memcpy(he->he_key, key, keylen);
he->he_keylen = keylen;
he->he_data = data;
- TAILQ_INSERT_TAIL(&ht->ht_table[hval], he, he_next);
+ TAILQ_INSERT_TAIL(&ht->ht_buckets[hval].hb_table, he, he_next);
+ ht->ht_buckets[hval].hb_len++;
+
+ /* Attempt to grow table if needed */
+ if ((ht->ht_grow > ht->ht_tblsz) &&
+ (ht->ht_buckets[hval].hb_len >= ht->ht_col))
+ grow(ht);
return (0);
}
@@ -364,16 +425,14 @@
uint32_t hval;
struct hashentry *he;
- hval = hash(key, keylen, time(NULL));
+ hval = hash(key, keylen, 0);
hval &= ht->ht_mask;
he = find(ht, hval, key, keylen);
if (he != NULL) {
- hval = hash(key, keylen, time(NULL));
- hval &= ht->ht_mask;
- TAILQ_REMOVE(&ht->ht_table[hval], he, he_next);
+ TAILQ_REMOVE(&ht->ht_buckets[hval].hb_table, he, he_next);
free(he->he_key);
- TAILQ_INSERT_TAIL(&ht->ht_free, he, he_next);
+ free_he(ht, he);
return (0);
}
return (-1);
@@ -394,7 +453,7 @@
uint32_t hval;
struct hashentry *he;
- hval = hash(key, keylen, time(NULL));
+ hval = hash(key, keylen, 0);
hval &= ht->ht_mask;
he = find(ht, hval, key, keylen);
==== //depot/projects/soc2007/fli-mdns_sd/mdnsd/hash.h#3 (text+ko) ====
@@ -34,25 +34,45 @@
*/
struct hashentry {
TAILQ_ENTRY(hashentry) he_next; /* Next entry */
+ uint32_t he_hash; /* Hash key */
void *he_key; /* Key */
size_t he_keylen; /* Key length */
void *he_data; /* Data object pointer */
};
/*
+ * Hash bucket
+ */
+struct hashbkt {
+ TAILQ_HEAD(, hashentry) hb_table;
+ uint8_t hb_len;
+};
+
+/*
+ * Pre-allocated hashentry objects
+ */
+struct he_pool {
+ SLIST_ENTRY(he_pool) hep_next;
+ uint32_t hep_pos;
+ uint32_t hep_size;
+ /* sizeof(struct hashentry) * hep_size bytes follows */
+};
+
+/*
* Hash table
*/
struct hashtbl {
- TAILQ_HEAD(, hashentry) *ht_table; /* Bucket array */
+ struct hashbkt *ht_buckets; /* Bucket array */
size_t ht_tblsz; /* Size of table */
+ size_t ht_grow; /* Allowed grow size */
+ size_t ht_col; /* Allowed collisions */
uint32_t ht_mask;
- struct hashentry **ht_chunk; /* Chunk array */
- TAILQ_HEAD(, hashentry) ht_free; /* Free list */
- size_t ht_entries; /* Entries per chunk */
- size_t ht_chunks; /* Number of chunks */
+ uint8_t ht_alloc_size;
+ SLIST_HEAD(, he_pool) ht_new; /* new hashentry objs */
+ SLIST_HEAD(, he_pool) ht_free; /* free hashentry objs */
};
-int hashtbl_init(struct hashtbl *, size_t);
+int hashtbl_init(struct hashtbl *, size_t, size_t, size_t);
void hashtbl_destroy(struct hashtbl *);
int hashtbl_add(struct hashtbl *, void *, size_t, void *);
int hashtbl_del(struct hashtbl *, void *, size_t);
More information about the p4-projects
mailing list