3506ac49 |
/* |
e1cbc270 |
* Copyright (C) 2013-2019 Cisco Systems, Inc. and/or its affiliates. All rights reserved. |
a0e53e41 |
* Copyright (C) 2007-2013 Sourcefire, Inc. |
2023340a |
*
* Authors: Török Edvin |
544fa973 |
* |
6289eda8 |
* Summary: Hash-table and -set data structures. |
544fa973 |
*
* Acknowledgements: hash32shift() is an implementation of Thomas Wang's
* 32-bit integer hash function: |
6289eda8 |
* http://www.cris.com/~Ttwang/tech/inthash.htm |
3506ac49 |
*
* This program is free software; you can redistribute it and/or modify |
2023340a |
* it under the terms of the GNU General Public License version 2 as |
38a00199 |
* published by the Free Software Foundation. |
3506ac49 |
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
* MA 02110-1301, USA.
*/
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include "clamav.h" |
7f8a30ba |
#include "clamav-config.h" |
3506ac49 |
#include "others.h"
#include "hashtab.h"
|
c3671221 |
#define MODULE_NAME "hashtab: " |
3506ac49 |
|
b0b8398b |
static const char DELETED_KEY[] = ""; |
b6540c3d |
#define DELETED_HTU32_KEY ((uint32_t)(-1)) |
3506ac49 |
|
c3671221 |
static unsigned long nearest_power(unsigned long num) |
3506ac49 |
{ |
288057e9 |
unsigned long n = 64; |
c3671221 |
|
288057e9 |
while (n < num) {
n <<= 1;
if (n == 0) {
return num;
}
}
return n; |
3506ac49 |
}
#ifdef PROFILE_HASHTABLE
/* I know, this is ugly, most of these functions get a const s, that gets its const-ness discarded,
* and then these functions modify something the compiler assumes is readonly.
* Please, never use PROFILE_HASHTABLE in production code, and in releases. Use it for development only!*/
|
cc447ac8 |
static inline void PROFILE_INIT(struct cli_hashtable *s) |
3506ac49 |
{ |
288057e9 |
memset(&s->PROFILE_STRUCT, 0, sizeof(s->PROFILE_STRUCT)); |
3506ac49 |
}
|
cc447ac8 |
static inline void PROFILE_CALC_HASH(struct cli_hashtable *s) |
3506ac49 |
{ |
288057e9 |
s->PROFILE_STRUCT.calc_hash++; |
3506ac49 |
}
|
cc447ac8 |
static inline void PROFILE_FIND_ELEMENT(struct cli_hashtable *s) |
3506ac49 |
{ |
288057e9 |
s->PROFILE_STRUCT.find_req++; |
3506ac49 |
}
|
cc447ac8 |
static inline void PROFILE_FIND_NOTFOUND(struct cli_hashtable *s, size_t tries) |
3506ac49 |
{ |
288057e9 |
s->PROFILE_STRUCT.not_found++;
s->PROFILE_STRUCT.not_found_tries += tries; |
3506ac49 |
}
|
cc447ac8 |
static inline void PROFILE_FIND_FOUND(struct cli_hashtable *s, size_t tries) |
3506ac49 |
{ |
288057e9 |
s->PROFILE_STRUCT.found++;
s->PROFILE_STRUCT.found_tries += tries; |
3506ac49 |
}
|
cc447ac8 |
static inline void PROFILE_HASH_EXHAUSTED(struct cli_hashtable *s) |
3506ac49 |
{ |
288057e9 |
s->PROFILE_STRUCT.hash_exhausted++; |
3506ac49 |
}
|
cc447ac8 |
static inline void PROFILE_GROW_START(struct cli_hashtable *s) |
3506ac49 |
{ |
288057e9 |
s->PROFILE_STRUCT.grow++; |
3506ac49 |
}
|
cc447ac8 |
static inline void PROFILE_GROW_FOUND(struct cli_hashtable *s, size_t tries) |
3506ac49 |
{ |
288057e9 |
s->PROFILE_STRUCT.grow_found++;
s->PROFILE_STRUCT.grow_found_tries += tries; |
3506ac49 |
}
|
cc447ac8 |
static inline void PROFILE_GROW_DONE(struct cli_hashtable *s) |
3506ac49 |
{
}
|
cc447ac8 |
static inline void PROFILE_DELETED_REUSE(struct cli_hashtable *s, size_t tries) |
3506ac49 |
{ |
288057e9 |
s->PROFILE_STRUCT.deleted_reuse++;
s->PROFILE_STRUCT.deleted_tries += tries; |
3506ac49 |
}
|
cc447ac8 |
static inline void PROFILE_INSERT(struct cli_hashtable *s, size_t tries) |
3506ac49 |
{ |
288057e9 |
s->PROFILE_STRUCT.inserts++;
s->PROFILE_STRUCT.insert_tries += tries; |
3506ac49 |
}
|
cc447ac8 |
static inline void PROFILE_DATA_UPDATE(struct cli_hashtable *s, size_t tries) |
3506ac49 |
{ |
288057e9 |
s->PROFILE_STRUCT.update++;
s->PROFILE_STRUCT.update_tries += tries; |
3506ac49 |
}
|
cc447ac8 |
static inline void PROFILE_HASH_DELETE(struct cli_hashtable *s) |
3506ac49 |
{ |
288057e9 |
s->PROFILE_STRUCT.deletes++; |
3506ac49 |
}
|
cc447ac8 |
static inline void PROFILE_HASH_CLEAR(struct cli_hashtable *s) |
3506ac49 |
{ |
288057e9 |
s->PROFILE_STRUCT.clear++; |
3506ac49 |
}
|
cc447ac8 |
static inline void PROFILE_REPORT(const struct cli_hashtable *s) |
3506ac49 |
{ |
288057e9 |
size_t lookups, queries, insert_tries, inserts;
cli_dbgmsg("--------Hashtable usage report for %p--------------\n", (const void *)s);
cli_dbgmsg("hash function calculations:%ld\n", s->PROFILE_STRUCT.calc_hash);
cli_dbgmsg("successful finds/total searches: %ld/%ld; lookups: %ld\n", s->PROFILE_STRUCT.found, s->PROFILE_STRUCT.find_req, s->PROFILE_STRUCT.found_tries);
cli_dbgmsg("unsuccessful finds/total searches: %ld/%ld; lookups: %ld\n", s->PROFILE_STRUCT.not_found, s->PROFILE_STRUCT.find_req, s->PROFILE_STRUCT.not_found_tries);
cli_dbgmsg("successful finds during grow:%ld; lookups: %ld\n", s->PROFILE_STRUCT.grow_found, s->PROFILE_STRUCT.grow_found_tries);
lookups = s->PROFILE_STRUCT.found_tries + s->PROFILE_STRUCT.not_found_tries + s->PROFILE_STRUCT.grow_found_tries;
queries = s->PROFILE_STRUCT.find_req + s->PROFILE_STRUCT.grow_found;
cli_dbgmsg("Find Lookups/total queries: %ld/%ld = %3f\n", lookups, queries, lookups * 1.0 / queries);
insert_tries = s->PROFILE_STRUCT.insert_tries + s->PROFILE_STRUCT.update_tries + s->PROFILE_STRUCT.deleted_tries; |
3506ac49 |
|
288057e9 |
cli_dbgmsg("new item insert tries/new items: %ld/%ld\n", s->PROFILE_STRUCT.insert_tries, s->PROFILE_STRUCT.inserts);
cli_dbgmsg("update tries/updates: %ld/%ld\n", s->PROFILE_STRUCT.update_tries, s->PROFILE_STRUCT.update);
cli_dbgmsg("deleted item reuse tries/deleted&reused items: %ld/%ld\n", s->PROFILE_STRUCT.deleted_tries, s->PROFILE_STRUCT.deleted_reuse);
inserts = s->PROFILE_STRUCT.inserts + s->PROFILE_STRUCT.update + s->PROFILE_STRUCT.deleted_reuse;
cli_dbgmsg("Insert tries/total inserts: %ld/%ld = %3f\n", insert_tries, inserts, insert_tries * 1.0 / inserts); |
3506ac49 |
|
288057e9 |
cli_dbgmsg("Grows: %ld, Deletes : %ld, hashtable clears: %ld\n", s->PROFILE_STRUCT.grow, s->PROFILE_STRUCT.deletes, s->PROFILE_STRUCT.clear);
cli_dbgmsg("--------Report end-------------\n"); |
3506ac49 |
}
#else |
288057e9 |
#define PROFILE_INIT(s)
#define PROFILE_CALC_HASH(s)
#define PROFILE_FIND_ELEMENT(s)
#define PROFILE_FIND_NOTFOUND(s, tries) |
3506ac49 |
#define PROFILE_FIND_FOUND(s, tries)
#define PROFILE_HASH_EXHAUSTED(s)
#define PROFILE_GROW_START(s)
#define PROFILE_GROW_FOUND(s, tries)
#define PROFILE_GROW_DONE(s)
#define PROFILE_DELETED_REUSE(s, tries)
#define PROFILE_INSERT(s, tries)
#define PROFILE_DATA_UPDATE(s, tries)
#define PROFILE_HASH_DELETE(s)
#define PROFILE_HASH_CLEAR(s)
#define PROFILE_REPORT(s)
#endif
|
288057e9 |
int cli_hashtab_init(struct cli_hashtable *s, size_t capacity) |
3506ac49 |
{ |
288057e9 |
if (!s)
return CL_ENULLARG; |
3506ac49 |
|
288057e9 |
PROFILE_INIT(s); |
3506ac49 |
|
288057e9 |
capacity = nearest_power(capacity);
s->htable = cli_calloc(capacity, sizeof(*s->htable));
if (!s->htable)
return CL_EMEM;
s->capacity = capacity;
s->used = 0;
s->maxfill = 8 * capacity / 10;
return 0; |
3506ac49 |
}
|
b6540c3d |
int cli_htu32_init(struct cli_htu32 *s, size_t capacity, mpool_t *mempool)
{ |
288057e9 |
if (!s)
return CL_ENULLARG; |
b6540c3d |
|
288057e9 |
PROFILE_INIT(s); |
b6540c3d |
|
288057e9 |
capacity = nearest_power(capacity); |
544fa973 |
s->htable = MPOOL_CALLOC(mempool, capacity, sizeof(*s->htable)); |
288057e9 |
if (!s->htable)
return CL_EMEM;
s->capacity = capacity;
s->used = 0;
s->maxfill = 8 * capacity / 10;
return 0; |
b6540c3d |
}
|
c3671221 |
static inline uint32_t hash32shift(uint32_t key)
{ |
288057e9 |
key = ~key + (key << 15);
key = key ^ (key >> 12);
key = key + (key << 2);
key = key ^ (key >> 4);
key = (key + (key << 3)) + (key << 11);
key = key ^ (key >> 16);
return key; |
c3671221 |
}
|
288057e9 |
static inline size_t hash(const unsigned char *k, const size_t len, const size_t SIZE) |
3506ac49 |
{ |
288057e9 |
size_t Hash = 1;
size_t i;
for (i = 0; i < len; i++) {
/* a simple add is good, because we use the mixing function below */
Hash += k[i];
/* mixing function */
Hash = hash32shift(Hash);
}
/* SIZE is power of 2 */
return Hash & (SIZE - 1); |
3506ac49 |
}
|
b6540c3d |
static inline size_t hash_htu32(uint32_t k, const size_t SIZE)
{ |
288057e9 |
/* mixing function */
size_t Hash = hash32shift(k);
/* SIZE is power of 2 */
return Hash & (SIZE - 1); |
b6540c3d |
}
|
3506ac49 |
/* if returned element has key==NULL, then key was not found in table */ |
288057e9 |
struct cli_element *cli_hashtab_find(const struct cli_hashtable *s, const char *key, const size_t len)
{
struct cli_element *element;
size_t tries = 1;
size_t idx;
if (!s)
return NULL;
PROFILE_CALC_HASH(s);
PROFILE_FIND_ELEMENT(s);
idx = hash((const unsigned char *)key, len, s->capacity);
element = &s->htable[idx];
do {
if (!element->key) {
PROFILE_FIND_NOTFOUND(s, tries);
return NULL; /* element not found, place is empty*/
} else if (element->key != DELETED_KEY && len == element->len && (key == element->key || strncmp(key, element->key, len) == 0)) {
PROFILE_FIND_FOUND(s, tries);
return element; /* found */
} else {
idx = (idx + tries++) & (s->capacity - 1);
element = &s->htable[idx];
}
} while (tries <= s->capacity);
PROFILE_HASH_EXHAUSTED(s);
return NULL; /* not found */ |
3506ac49 |
}
|
b6540c3d |
const struct cli_htu32_element *cli_htu32_find(const struct cli_htu32 *s, uint32_t key)
{ |
288057e9 |
struct cli_htu32_element *element;
size_t tries = 1;
size_t idx;
if (!s)
return NULL;
PROFILE_CALC_HASH(s);
PROFILE_FIND_ELEMENT(s);
idx = hash_htu32(key, s->capacity);
element = &s->htable[idx];
do {
if (!element->key) {
PROFILE_FIND_NOTFOUND(s, tries);
return NULL; /* element not found, place is empty */
} else if (key == element->key) {
PROFILE_FIND_FOUND(s, tries);
return element; /* found */
} else {
idx = (idx + tries++) & (s->capacity - 1);
element = &s->htable[idx];
}
} while (tries <= s->capacity);
PROFILE_HASH_EXHAUSTED(s);
return NULL; /* not found */ |
b6540c3d |
}
|
153388c1 |
/* linear enumeration - start with current = NULL, returns next item if present or NULL if not */ |
288057e9 |
const struct cli_htu32_element *cli_htu32_next(const struct cli_htu32 *s, const struct cli_htu32_element *current)
{
size_t ncur;
if (!s || !s->capacity)
return NULL; |
153388c1 |
|
288057e9 |
if (!current)
ncur = 0;
else {
ncur = current - s->htable;
if (ncur >= s->capacity)
return NULL; |
153388c1 |
|
288057e9 |
ncur++;
}
for (; ncur < s->capacity; ncur++) {
const struct cli_htu32_element *item = &s->htable[ncur & (s->capacity - 1)];
if (item->key && item->key != DELETED_HTU32_KEY)
return item;
}
return NULL; |
153388c1 |
}
|
cc447ac8 |
static int cli_hashtab_grow(struct cli_hashtable *s) |
3506ac49 |
{ |
288057e9 |
const size_t new_capacity = nearest_power(s->capacity + 1);
struct cli_element *htable;
size_t i, idx, used = 0;
cli_dbgmsg("hashtab.c: new capacity: %llu\n", (long long unsigned)new_capacity);
if (new_capacity == s->capacity) {
cli_errmsg("hashtab.c: capacity problem growing from: %llu\n", (long long unsigned)s->capacity);
return CL_EMEM;
}
htable = cli_calloc(new_capacity, sizeof(*s->htable));
if (!htable) {
return CL_EMEM;
}
PROFILE_GROW_START(s);
cli_dbgmsg("hashtab.c: Warning: growing open-addressing hashtables is slow. Either allocate more storage when initializing, or use other hashtable types!\n");
for (i = 0; i < s->capacity; i++) {
if (s->htable[i].key && s->htable[i].key != DELETED_KEY) {
struct cli_element *element;
size_t tries = 1;
PROFILE_CALC_HASH(s);
idx = hash((const unsigned char *)s->htable[i].key, s->htable[i].len, new_capacity);
element = &htable[idx];
while (element->key && tries <= new_capacity) {
idx = (idx + tries++) & (new_capacity - 1);
element = &htable[idx];
}
if (!element->key) {
/* copy element from old hashtable to new */
PROFILE_GROW_FOUND(s, tries);
*element = s->htable[i];
used++;
} else {
cli_errmsg("hashtab.c: Impossible - unable to rehash table");
free(htable);
return CL_EMEM; /* this means we didn't find enough room for all elements in the new table, should never happen */
}
}
}
free(s->htable);
s->htable = htable;
s->used = used;
s->capacity = new_capacity;
s->maxfill = new_capacity * 8 / 10;
cli_dbgmsg("Table %p size after grow:%llu\n", (void *)s, (long long unsigned)s->capacity);
PROFILE_GROW_DONE(s);
return CL_SUCCESS; |
3506ac49 |
}
|
0b82971d |
#ifndef USE_MPOOL
#define cli_htu32_grow(A, B) cli_htu32_grow(A)
#endif
|
b6540c3d |
static int cli_htu32_grow(struct cli_htu32 *s, mpool_t *mempool)
{ |
288057e9 |
const size_t new_capacity = nearest_power(s->capacity + 1); |
544fa973 |
struct cli_htu32_element *htable = MPOOL_CALLOC(mempool, new_capacity, sizeof(*s->htable)); |
288057e9 |
size_t i, idx, used = 0;
cli_dbgmsg("hashtab.c: new capacity: %llu\n", (long long unsigned)new_capacity);
if (new_capacity == s->capacity || !htable)
return CL_EMEM;
PROFILE_GROW_START(s);
for (i = 0; i < s->capacity; i++) {
if (s->htable[i].key && s->htable[i].key != DELETED_HTU32_KEY) {
struct cli_htu32_element *element;
size_t tries = 1;
PROFILE_CALC_HASH(s);
idx = hash_htu32(s->htable[i].key, new_capacity);
element = &htable[idx];
while (element->key && tries <= new_capacity) {
idx = (idx + tries++) & (new_capacity - 1);
element = &htable[idx];
}
if (!element->key) {
/* copy element from old hashtable to new */
PROFILE_GROW_FOUND(s, tries);
*element = s->htable[i];
used++;
} else {
cli_errmsg("hashtab.c: Impossible - unable to rehash table");
return CL_EMEM; /* this means we didn't find enough room for all elements in the new table, should never happen */
}
}
} |
544fa973 |
MPOOL_FREE(mempool, s->htable); |
288057e9 |
s->htable = htable;
s->used = used;
s->capacity = new_capacity;
s->maxfill = new_capacity * 8 / 10;
cli_dbgmsg("Table %p size after grow:%llu\n", (void *)s, (long long unsigned)s->capacity);
PROFILE_GROW_DONE(s);
return CL_SUCCESS;
}
const struct cli_element *cli_hashtab_insert(struct cli_hashtable *s, const char *key, const size_t len, const cli_element_data data)
{
struct cli_element *element;
struct cli_element *deleted_element = NULL;
size_t tries = 1;
size_t idx;
if (!s)
return NULL;
if (s->used > s->maxfill) {
cli_dbgmsg("hashtab.c:Growing hashtable %p, because it has exceeded maxfill, old size:%llu\n", (void *)s, (long long unsigned)s->capacity);
cli_hashtab_grow(s);
}
do {
PROFILE_CALC_HASH(s);
idx = hash((const unsigned char *)key, len, s->capacity);
element = &s->htable[idx];
do {
if (!element->key) {
char *thekey;
/* element not found, place is empty, insert*/
if (deleted_element) {
/* reuse deleted elements*/
element = deleted_element;
PROFILE_DELETED_REUSE(s, tries);
} else {
PROFILE_INSERT(s, tries);
}
thekey = cli_malloc(len + 1);
if (!thekey) { |
241e7eb1 |
cli_errmsg("hashtab.c: Unable to allocate memory for thekey\n"); |
288057e9 |
return NULL; |
241e7eb1 |
} |
288057e9 |
strncpy(thekey, key, len + 1);
thekey[len] = '\0';
element->key = thekey;
element->data = data;
element->len = len;
s->used++;
return element;
} else if (element->key == DELETED_KEY) {
deleted_element = element;
element->key = NULL;
} else if (len == element->len && strncmp(key, element->key, len) == 0) {
PROFILE_DATA_UPDATE(s, tries);
element->data = data; /* key found, update */
return element;
} else {
idx = (idx + tries++) % s->capacity;
element = &s->htable[idx];
}
} while (tries <= s->capacity);
/* no free place found*/
PROFILE_HASH_EXHAUSTED(s);
cli_dbgmsg("hashtab.c: Growing hashtable %p, because its full, old size:%llu.\n", (void *)s, (long long unsigned)s->capacity);
} while (cli_hashtab_grow(s) >= 0);
cli_warnmsg("hashtab.c: Unable to grow hashtable\n");
return NULL; |
3506ac49 |
}
|
b6540c3d |
int cli_htu32_insert(struct cli_htu32 *s, const struct cli_htu32_element *item, mpool_t *mempool)
{ |
288057e9 |
struct cli_htu32_element *element;
struct cli_htu32_element *deleted_element = NULL;
size_t tries = 1;
size_t idx;
int ret;
if (!s)
return CL_ENULLARG;
if (s->used > s->maxfill) {
cli_dbgmsg("hashtab.c:Growing hashtable %p, because it has exceeded maxfill, old size:%llu\n", (void *)s, (long long unsigned)s->capacity);
cli_htu32_grow(s, mempool);
}
do {
PROFILE_CALC_HASH(s);
idx = hash_htu32(item->key, s->capacity);
element = &s->htable[idx];
do {
if (!element->key) {
/* element not found, place is empty, insert*/
if (deleted_element) {
/* reuse deleted elements*/
element = deleted_element;
PROFILE_DELETED_REUSE(s, tries);
} else {
PROFILE_INSERT(s, tries);
}
*element = *item;
s->used++;
return 0;
} else if (element->key == DELETED_HTU32_KEY) {
deleted_element = element;
element->key = 0;
} else if (item->key == element->key) {
PROFILE_DATA_UPDATE(s, tries);
element->data = item->data; /* key found, update */
return 0;
} else {
idx = (idx + tries++) % s->capacity;
element = &s->htable[idx];
}
} while (tries <= s->capacity);
/* no free place found*/
PROFILE_HASH_EXHAUSTED(s);
cli_dbgmsg("hashtab.c: Growing hashtable %p, because its full, old size:%llu.\n", (void *)s, (long long unsigned)s->capacity);
} while ((ret = cli_htu32_grow(s, mempool)) >= 0);
cli_warnmsg("hashtab.c: Unable to grow hashtable\n");
return ret;
}
void cli_hashtab_delete(struct cli_hashtable *s, const char *key, const size_t len) |
7a7365ef |
{
struct cli_element *el = cli_hashtab_find(s, key, len); |
aadccfd1 |
if (!el || el->key == DELETED_KEY) |
288057e9 |
return;
free((void *)el->key); |
7a7365ef |
el->key = DELETED_KEY;
}
|
b6540c3d |
void cli_htu32_delete(struct cli_htu32 *s, uint32_t key)
{ |
288057e9 |
struct cli_htu32_element *el = (struct cli_htu32_element *)cli_htu32_find(s, key);
if (el)
el->key = DELETED_HTU32_KEY; |
b6540c3d |
}
|
cc447ac8 |
void cli_hashtab_clear(struct cli_hashtable *s) |
3506ac49 |
{ |
288057e9 |
size_t i;
PROFILE_HASH_CLEAR(s);
for (i = 0; i < s->capacity; i++) {
if (s->htable[i].key && s->htable[i].key != DELETED_KEY)
free((void *)s->htable[i].key);
}
if (s->htable)
memset(s->htable, 0, s->capacity * sizeof(*s->htable));
s->used = 0; |
3506ac49 |
}
|
b6540c3d |
void cli_htu32_clear(struct cli_htu32 *s)
{ |
288057e9 |
PROFILE_HASH_CLEAR(s);
if (s->htable)
memset(s->htable, 0, s->capacity * sizeof(struct cli_htu32_element));
s->used = 0; |
b6540c3d |
}
|
cc447ac8 |
void cli_hashtab_free(struct cli_hashtable *s) |
2e11bcdf |
{ |
288057e9 |
cli_hashtab_clear(s);
free(s->htable);
s->htable = NULL;
s->capacity = 0; |
2e11bcdf |
} |
3506ac49 |
|
b6540c3d |
void cli_htu32_free(struct cli_htu32 *s, mpool_t *mempool)
{ |
544fa973 |
MPOOL_FREE(mempool, s->htable); |
288057e9 |
s->htable = NULL;
s->capacity = 0; |
b6540c3d |
}
|
288057e9 |
size_t cli_htu32_numitems(struct cli_htu32 *s) |
3506ac49 |
{ |
288057e9 |
if (!s) return 0;
return s->capacity; |
3506ac49 |
}
|
288057e9 |
int cli_hashtab_store(const struct cli_hashtable *s, FILE *out) |
3506ac49 |
{ |
288057e9 |
size_t i;
for (i = 0; i < s->capacity; i++) {
const struct cli_element *e = &s->htable[i];
if (e->key && e->key != DELETED_KEY) {
fprintf(out, "%ld %s\n", e->data, e->key);
}
}
return CL_SUCCESS;
}
int cli_hashtab_generate_c(const struct cli_hashtable *s, const char *name)
{
size_t i;
printf("/* TODO: include GPL headers */\n");
printf("#include <hashtab.h>\n");
printf("static struct cli_element %s_elements[] = {\n", name);
for (i = 0; i < s->capacity; i++) {
const struct cli_element *e = &s->htable[i];
if (!e->key)
printf("\t{NULL,0,0},\n");
else if (e->key == DELETED_KEY)
printf("\t{DELETED_KEY,0,0},\n");
else
printf("\t{\"%s\", %ld, %llu},\n", e->key, e->data, (long long unsigned)e->len);
}
printf("};\n");
printf("const struct cli_hashtable %s = {\n", name);
printf("\t%s_elements, %llu, %llu, %llu", name, (long long unsigned)s->capacity,
(long long unsigned)s->used, (long long unsigned)s->maxfill);
printf("\n};\n"); |
3506ac49 |
|
288057e9 |
PROFILE_REPORT(s);
return 0; |
3506ac49 |
}
|
288057e9 |
int cli_hashtab_load(FILE *in, struct cli_hashtable *s) |
3506ac49 |
{ |
288057e9 |
char line[1024];
while (fgets(line, sizeof(line), in)) {
char l[1024];
int val;
sscanf(line, "%d %1023s", &val, l);
cli_hashtab_insert(s, l, strlen(l), val);
}
return CL_SUCCESS; |
3506ac49 |
}
|
c3671221 |
/* Initialize hashset. @initial_capacity is rounded to nearest power of 2.
* Load factor is between 50 and 99. When capacity*load_factor/100 is reached, the hashset is growed */ |
288057e9 |
int cli_hashset_init(struct cli_hashset *hs, size_t initial_capacity, uint8_t load_factor)
{
if (load_factor < 50 || load_factor > 99) {
cli_dbgmsg(MODULE_NAME "Invalid load factor: %u, using default of 80%%\n", load_factor);
load_factor = 80;
}
initial_capacity = nearest_power(initial_capacity);
hs->limit = initial_capacity * load_factor / 100;
hs->capacity = initial_capacity;
hs->mask = initial_capacity - 1;
hs->count = 0;
hs->keys = cli_malloc(initial_capacity * sizeof(*hs->keys));
hs->mempool = NULL;
if (!hs->keys) { |
7cd9337a |
cli_errmsg("hashtab.c: Unable to allocate memory for hs->keys\n"); |
288057e9 |
return CL_EMEM;
}
hs->bitmap = cli_calloc(initial_capacity >> 5, sizeof(*hs->bitmap));
if (!hs->bitmap) {
free(hs->keys); |
241e7eb1 |
cli_errmsg("hashtab.c: Unable to allocate memory for hs->bitmap\n"); |
288057e9 |
return CL_EMEM;
}
return 0;
}
int cli_hashset_init_pool(struct cli_hashset *hs, size_t initial_capacity, uint8_t load_factor, mpool_t *mempool)
{
if (load_factor < 50 || load_factor > 99) {
cli_dbgmsg(MODULE_NAME "Invalid load factor: %u, using default of 80%%\n", load_factor);
load_factor = 80;
}
initial_capacity = nearest_power(initial_capacity);
hs->limit = initial_capacity * load_factor / 100;
hs->capacity = initial_capacity;
hs->mask = initial_capacity - 1;
hs->count = 0;
hs->mempool = mempool; |
544fa973 |
hs->keys = MPOOL_MALLOC(mempool, initial_capacity * sizeof(*hs->keys)); |
288057e9 |
if (!hs->keys) { |
241e7eb1 |
cli_errmsg("hashtab.c: Unable to allocate memory pool for hs->keys\n"); |
288057e9 |
return CL_EMEM;
} |
544fa973 |
hs->bitmap = MPOOL_CALLOC(mempool, initial_capacity >> 5, sizeof(*hs->bitmap)); |
288057e9 |
if (!hs->bitmap) { |
544fa973 |
MPOOL_FREE(mempool, hs->keys); |
241e7eb1 |
cli_errmsg("hashtab.c: Unable to allocate/initialize memory for hs->keys\n"); |
288057e9 |
return CL_EMEM;
}
return 0; |
355bbc6a |
}
|
288057e9 |
void cli_hashset_destroy(struct cli_hashset *hs) |
c3671221 |
{ |
288057e9 |
cli_dbgmsg(MODULE_NAME "Freeing hashset, elements: %u, capacity: %u\n", hs->count, hs->capacity);
if (hs->mempool) { |
544fa973 |
MPOOL_FREE(hs->mempool, hs->keys);
MPOOL_FREE(hs->mempool, hs->bitmap); |
288057e9 |
} else {
free(hs->keys);
free(hs->bitmap);
}
hs->keys = hs->bitmap = NULL;
hs->capacity = 0; |
c3671221 |
}
|
2b64ecb6 |
#define BITMAP_CONTAINS(bmap, val) ((bmap)[(val) >> 5] & ((uint64_t) 1 << ((val)&0x1f)))
#define BITMAP_INSERT(bmap, val) ((bmap)[(val) >> 5] |= ((uint64_t) 1 << ((val)&0x1f)))
#define BITMAP_REMOVE(bmap, val) ((bmap)[(val) >> 5] &= ~((uint64_t) 1 << ((val)&0x1f))) |
c3671221 |
/*
* searches the hashset for the @key.
* Returns the position the key is at, or a candidate position where it could be inserted.
*/ |
288057e9 |
static inline size_t cli_hashset_search(const struct cli_hashset *hs, const uint32_t key) |
c3671221 |
{ |
288057e9 |
/* calculate hash value for this key, and map it to our table */
size_t idx = hash32shift(key) & (hs->mask);
size_t tries = 1; |
c3671221 |
|
288057e9 |
/* check whether the entry is used, and if the key matches */
while (BITMAP_CONTAINS(hs->bitmap, idx) && (hs->keys[idx] != key)) {
/* entry used, key different -> collision */
idx = (idx + tries++) & (hs->mask);
/* quadratic probing, with c1 = c2 = 1/2, guaranteed to walk the entire table |
c3671221 |
* for table sizes power of 2.*/ |
288057e9 |
}
/* we have either found the key, or a candidate insertion position */
return idx; |
c3671221 |
}
|
288057e9 |
static void cli_hashset_addkey_internal(struct cli_hashset *hs, const uint32_t key) |
c3671221 |
{ |
288057e9 |
const size_t idx = cli_hashset_search(hs, key);
/* we know hashtable is not full, when this method is called */ |
c3671221 |
|
288057e9 |
if (!BITMAP_CONTAINS(hs->bitmap, idx)) {
/* add new key */
BITMAP_INSERT(hs->bitmap, idx);
hs->keys[idx] = key;
hs->count++;
} |
c3671221 |
}
|
cc447ac8 |
static int cli_hashset_grow(struct cli_hashset *hs) |
c3671221 |
{ |
288057e9 |
struct cli_hashset new_hs;
size_t i;
int rc; |
c3671221 |
|
288057e9 |
/* in-place growing is not possible, since the new keys |
c3671221 |
* will hash to different locations. */ |
288057e9 |
cli_dbgmsg(MODULE_NAME "Growing hashset, used: %u, capacity: %u\n", hs->count, hs->capacity);
/* create a bigger hashset */
if (hs->mempool)
rc = cli_hashset_init_pool(&new_hs, hs->capacity << 1, hs->limit * 100 / hs->capacity, hs->mempool);
else
rc = cli_hashset_init(&new_hs, hs->capacity << 1, hs->limit * 100 / hs->capacity);
if (rc != 0)
return rc;
/* and copy keys */
for (i = 0; i < hs->capacity; i++) {
if (BITMAP_CONTAINS(hs->bitmap, i)) {
const size_t key = hs->keys[i];
cli_hashset_addkey_internal(&new_hs, key);
}
}
cli_hashset_destroy(hs);
/* replace old hashset with new one */
*hs = new_hs;
return 0;
}
int cli_hashset_addkey(struct cli_hashset *hs, const uint32_t key)
{
/* check that we didn't reach the load factor. |
c3671221 |
* Even if we don't know yet whether we'd add this key */ |
288057e9 |
if (hs->count + 1 > hs->limit) {
int rc = cli_hashset_grow(hs);
if (rc) {
return rc;
}
}
cli_hashset_addkey_internal(hs, key);
return 0; |
c3671221 |
}
|
288057e9 |
int cli_hashset_removekey(struct cli_hashset *hs, const uint32_t key) |
ded1cddc |
{
const size_t idx = cli_hashset_search(hs, key);
if (BITMAP_CONTAINS(hs->bitmap, idx)) { |
288057e9 |
BITMAP_REMOVE(hs->bitmap, idx);
hs->keys[idx] = 0;
hs->count--;
return 0; |
ded1cddc |
} |
36106d89 |
return -1; |
ded1cddc |
}
|
288057e9 |
int cli_hashset_contains(const struct cli_hashset *hs, const uint32_t key) |
c3671221 |
{ |
288057e9 |
const size_t idx = cli_hashset_search(hs, key);
return BITMAP_CONTAINS(hs->bitmap, idx); |
c3671221 |
}
|
288057e9 |
ssize_t cli_hashset_toarray(const struct cli_hashset *hs, uint32_t **array) |
c3671221 |
{ |
288057e9 |
size_t i, j;
uint32_t *arr; |
c3671221 |
|
288057e9 |
if (!array) {
return CL_ENULLARG;
}
*array = arr = cli_malloc(hs->count * sizeof(*arr));
if (!arr) { |
241e7eb1 |
cli_errmsg("hashtab.c: Unable to allocate memory for array\n"); |
288057e9 |
return CL_EMEM;
} |
c3671221 |
|
288057e9 |
for (i = 0, j = 0; i < hs->capacity && j < hs->count; i++) {
if (BITMAP_CONTAINS(hs->bitmap, i)) {
arr[j++] = hs->keys[i];
}
}
return j; |
c3671221 |
} |
1739b81e |
void cli_hashset_init_noalloc(struct cli_hashset *hs)
{ |
91689e9b |
memset(hs, 0, sizeof(*hs)); |
1739b81e |
}
int cli_hashset_contains_maybe_noalloc(const struct cli_hashset *hs, const uint32_t key)
{
if (!hs->keys) |
288057e9 |
return 0; |
1739b81e |
return cli_hashset_contains(hs, key);
} |
7a7365ef |
int cli_map_init(struct cli_map *m, int32_t keysize, int32_t valuesize, |
288057e9 |
int32_t capacity) |
7a7365ef |
{
if (keysize <= 0 || valuesize < 0 || capacity <= 0) |
288057e9 |
return -CL_EARG; |
7a7365ef |
memset(m, 0, sizeof(*m));
cli_hashtab_init(&m->htab, 16); |
288057e9 |
m->keysize = keysize;
m->valuesize = valuesize; |
7a7365ef |
m->last_insert = -1; |
288057e9 |
m->last_find = -1; |
7a7365ef |
return 0;
}
|
288057e9 |
int cli_map_addkey(struct cli_map *m, const void *key, int32_t keysize) |
7a7365ef |
{
unsigned n;
struct cli_element *el;
if (m->keysize != keysize) |
288057e9 |
return -CL_EARG; |
7a7365ef |
el = cli_hashtab_find(&m->htab, key, keysize);
if (el) { |
288057e9 |
m->last_insert = el->data;
return 0; |
7a7365ef |
}
n = m->nvalues + 1;
if (m->valuesize) { |
288057e9 |
void *v;
v = cli_realloc(m->u.sized_values, n * m->valuesize);
if (!v)
return -CL_EMEM;
m->u.sized_values = v;
memset((char *)m->u.sized_values + (n - 1) * m->valuesize, 0, m->valuesize); |
7a7365ef |
} else { |
288057e9 |
struct cli_map_value *v;
v = cli_realloc(m->u.unsized_values, n * sizeof(*m->u.unsized_values));
if (!v)
return -CL_EMEM;
m->u.unsized_values = v;
memset(&m->u.unsized_values[n - 1], 0, sizeof(*m->u.unsized_values)); |
7a7365ef |
}
m->nvalues = n; |
288057e9 |
if (!cli_hashtab_insert(&m->htab, key, keysize, n - 1))
return -CL_EMEM;
m->last_insert = n - 1; |
7a7365ef |
return 1;
}
|
288057e9 |
int cli_map_removekey(struct cli_map *m, const void *key, int32_t keysize) |
7a7365ef |
{
struct cli_element *el;
if (m->keysize != keysize) |
288057e9 |
return -CL_EARG; |
7a7365ef |
el = cli_hashtab_find(&m->htab, key, keysize);
if (!el) |
288057e9 |
return 0; |
7a7365ef |
if (el->data >= m->nvalues || el->data < 0) |
288057e9 |
return -CL_EARG; |
7a7365ef |
if (!m->valuesize) { |
288057e9 |
struct cli_map_value *v = &m->u.unsized_values[el->data];
free(v->value);
v->value = NULL;
v->valuesize = 0; |
7a7365ef |
} else { |
288057e9 |
char *v = (char *)m->u.sized_values + el->data * m->valuesize;
memset(v, 0, m->valuesize); |
7a7365ef |
}
cli_hashtab_delete(&m->htab, key, keysize);
return 1;
}
|
288057e9 |
int cli_map_setvalue(struct cli_map *m, const void *value, int32_t valuesize) |
7a7365ef |
{ |
288057e9 |
if ((m->valuesize && m->valuesize != valuesize) || (uint32_t)(m->last_insert) >= m->nvalues || m->last_insert < 0)
return -CL_EARG; |
7a7365ef |
if (m->valuesize) { |
288057e9 |
memcpy((char *)m->u.sized_values + m->last_insert * m->valuesize,
value, valuesize); |
7a7365ef |
} else { |
288057e9 |
struct cli_map_value *v = &m->u.unsized_values[m->last_insert];
if (v->value)
free(v->value);
v->value = cli_malloc(valuesize);
if (!v->value) {
cli_errmsg("hashtab.c: Unable to allocate memory for v->value\n");
return -CL_EMEM;
}
memcpy(v->value, value, valuesize);
v->valuesize = valuesize; |
7a7365ef |
}
return 0;
}
|
288057e9 |
int cli_map_find(struct cli_map *m, const void *key, int32_t keysize) |
7a7365ef |
{
struct cli_element *el;
if (m->keysize != keysize) |
288057e9 |
return -CL_EARG; |
7a7365ef |
el = cli_hashtab_find(&m->htab, key, keysize);
if (!el) |
288057e9 |
return 0; |
7a7365ef |
m->last_find = el->data;
return 1;
}
|
288057e9 |
int cli_map_getvalue_size(struct cli_map *m) |
7a7365ef |
{
if (m->valuesize) |
288057e9 |
return m->valuesize; |
cd94be7a |
if (m->last_find < 0 || (uint32_t)(m->last_find) >= m->nvalues) |
288057e9 |
return -CL_EARG; |
7a7365ef |
return m->u.unsized_values[m->last_find].valuesize;
}
|
288057e9 |
void *cli_map_getvalue(struct cli_map *m) |
7a7365ef |
{ |
cd94be7a |
if (m->last_find < 0 || (uint32_t)(m->last_find) >= m->nvalues) |
288057e9 |
return NULL; |
7a7365ef |
if (m->valuesize) |
288057e9 |
return (char *)m->u.sized_values + m->last_find * m->valuesize; |
e01a81ba |
return m->u.unsized_values[m->last_find].value; |
7a7365ef |
}
void cli_map_delete(struct cli_map *m)
{
cli_hashtab_free(&m->htab);
if (!m->valuesize) { |
288057e9 |
unsigned i;
for (i = 0; i < m->nvalues; i++)
free(m->u.unsized_values[i].value);
free(m->u.unsized_values); |
aadccfd1 |
} else { |
288057e9 |
free(m->u.sized_values); |
7a7365ef |
}
memset(m, 0, sizeof(*m));
} |