Date: Fri, 25 May 2007 16:15:11 GMT From: Fredrik Lindberg <fli@FreeBSD.org> To: Perforce Change Reviews <perforce@FreeBSD.org> Subject: PERFORCE change 120388 for review Message-ID: <200705251615.l4PGFBjJ008131@repoman.freebsd.org>
next in thread | raw e-mail | index | archive | help
http://perforce.freebsd.org/chv.cgi?CH=120388 Change 120388 by fli@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);
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?200705251615.l4PGFBjJ008131>