summaryrefslogtreecommitdiff
path: root/src/libstrongswan/utils/hashtable.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/libstrongswan/utils/hashtable.c')
-rw-r--r--src/libstrongswan/utils/hashtable.c152
1 files changed, 83 insertions, 69 deletions
diff --git a/src/libstrongswan/utils/hashtable.c b/src/libstrongswan/utils/hashtable.c
index 6d33d023b..02c225833 100644
--- a/src/libstrongswan/utils/hashtable.c
+++ b/src/libstrongswan/utils/hashtable.c
@@ -30,12 +30,12 @@ struct pair_t {
* Key of a hash table item.
*/
void *key;
-
+
/**
* Value of a hash table item.
*/
void *value;
-
+
/**
* Cached hash (used in case of a resize).
*/
@@ -48,11 +48,11 @@ struct pair_t {
pair_t *pair_create(void *key, void *value, u_int hash)
{
pair_t *this = malloc_thing(pair_t);
-
+
this->key = key;
this->value = value;
this->hash = hash;
-
+
return this;
}
@@ -67,37 +67,37 @@ struct private_hashtable_t {
* Public part of hash table.
*/
hashtable_t public;
-
+
/**
- * The number of items in the hash table.
+ * The number of items in the hash table.
*/
u_int count;
-
+
/**
* The current capacity of the hash table (always a power of 2).
*/
u_int capacity;
-
+
/**
- * The current mask to calculate the row index (capacity - 1).
+ * The current mask to calculate the row index (capacity - 1).
*/
u_int mask;
-
+
/**
* The load factor.
*/
float load_factor;
-
+
/**
* The actual table.
*/
linked_list_t **table;
-
+
/**
* The hashing function.
*/
hashtable_hash_t hash;
-
+
/**
* The equality function.
*/
@@ -115,17 +115,17 @@ struct private_enumerator_t {
* implements enumerator interface
*/
enumerator_t enumerator;
-
+
/**
* associated hash table
*/
private_hashtable_t *table;
-
+
/**
* current row index
*/
u_int row;
-
+
/**
* enumerator for the current row
*/
@@ -149,6 +149,7 @@ static inline bool pair_equals(pair_t *pair, private_hashtable_t *this, void *ke
static u_int get_nearest_powerof2(u_int n)
{
u_int i;
+
--n;
for (i = 1; i < sizeof(u_int) * 8; i <<= 1)
{
@@ -166,7 +167,7 @@ static void init_hashtable(private_hashtable_t *this, u_int capacity)
this->capacity = get_nearest_powerof2(capacity);
this->mask = this->capacity - 1;
this->load_factor = 0.75;
-
+
this->table = calloc(this->capacity, sizeof(linked_list_t*));
}
@@ -175,30 +176,37 @@ static void init_hashtable(private_hashtable_t *this, u_int capacity)
*/
static void rehash(private_hashtable_t *this)
{
- u_int row;
- u_int old_capacity = this->capacity;
- linked_list_t **old_table = this->table;
-
- if (old_capacity >= MAX_CAPACITY)
+ linked_list_t **old_table;
+ u_int row, old_capacity;
+
+ if (this->capacity < MAX_CAPACITY)
{
return;
}
-
+
+ old_capacity = this->capacity;
+ old_table = this->table;
+
init_hashtable(this, old_capacity << 1);
-
- for (row = 0; row < old_capacity; ++row)
+
+ for (row = 0; row < old_capacity; row++)
{
- linked_list_t *list;
- if ((list = old_table[row]) != NULL)
+ enumerator_t *enumerator;
+ linked_list_t *list, *new_list;
+ pair_t *pair;
+ u_int new_row;
+
+ list = old_table[row];
+ if (list)
{
- pair_t *pair;
- enumerator_t *enumerator = list->create_enumerator(list);
+ enumerator = list->create_enumerator(list);
while (enumerator->enumerate(enumerator, &pair))
{
- linked_list_t *new_list;
- u_int new_row = pair->hash & this->mask;
+ new_row = pair->hash & this->mask;
+
list->remove_at(list, enumerator);
- if ((new_list = this->table[new_row]) == NULL)
+ new_list = this->table[new_row];
+ if (!new_list)
{
new_list = this->table[new_row] = linked_list_create();
}
@@ -216,15 +224,20 @@ static void rehash(private_hashtable_t *this)
*/
static void *put(private_hashtable_t *this, void *key, void *value)
{
- linked_list_t *list;
void *old_value = NULL;
- u_int hash = this->hash(key);
- u_int row = hash & this->mask;
-
- if ((list = this->table[row]) != NULL)
+ linked_list_t *list;
+ u_int hash;
+ u_int row;
+
+ hash = this->hash(key);
+ row = hash & this->mask;
+ list = this->table[row];
+ if (list)
{
+ enumerator_t *enumerator;
pair_t *pair;
- enumerator_t *enumerator = list->create_enumerator(list);
+
+ enumerator = list->create_enumerator(list);
while (enumerator->enumerate(enumerator, &pair))
{
if (pair_equals(pair, this, key))
@@ -240,43 +253,39 @@ static void *put(private_hashtable_t *this, void *key, void *value)
{
list = this->table[row] = linked_list_create();
}
-
if (!old_value)
{
list->insert_last(list, pair_create(key, value, hash));
this->count++;
}
-
if (this->count >= this->capacity * this->load_factor)
{
rehash(this);
}
-
return old_value;
}
-
+
/**
- * Implementation of hashtable_t.get
+ * Implementation of hashtable_t.get
*/
static void *get(private_hashtable_t *this, void *key)
{
void *value = NULL;
linked_list_t *list;
- u_int row = this->hash(key) & this->mask;
-
- if ((list = this->table[row]) != NULL)
+ pair_t *pair;
+
+ list = this->table[this->hash(key) & this->mask];
+ if (list)
{
- pair_t *pair;
if (list->find_first(list, (linked_list_match_t)pair_equals,
- (void**)&pair, this, key) == SUCCESS)
+ (void**)&pair, this, key) == SUCCESS)
{
value = pair->value;
}
}
-
return value;
}
-
+
/**
* Implementation of hashtable_t.remove
*/
@@ -284,12 +293,14 @@ static void *remove_(private_hashtable_t *this, void *key)
{
void *value = NULL;
linked_list_t *list;
- u_int row = this->hash(key) & this->mask;
-
- if ((list = this->table[row]) != NULL)
+
+ list = this->table[this->hash(key) & this->mask];
+ if (list)
{
+ enumerator_t *enumerator;
pair_t *pair;
- enumerator_t *enumerator = list->create_enumerator(list);
+
+ enumerator = list->create_enumerator(list);
while (enumerator->enumerate(enumerator, &pair))
{
if (pair_equals(pair, this, key))
@@ -303,10 +314,9 @@ static void *remove_(private_hashtable_t *this, void *key)
}
enumerator->destroy(enumerator);
}
-
return value;
}
-
+
/**
* Implementation of hashtable_t.get_count
*/
@@ -325,7 +335,7 @@ static bool enumerate(private_enumerator_t *this, void **key, void **value)
if (this->current)
{
pair_t *pair;
-
+
if (this->current->enumerate(this->current, &pair))
{
if (key)
@@ -344,8 +354,9 @@ static bool enumerate(private_enumerator_t *this, void **key, void **value)
else
{
linked_list_t *list;
-
- if ((list = this->table->table[this->row]) != NULL)
+
+ list = this->table->table[this->row];
+ if (list)
{
this->current = list->create_enumerator(list);
continue;
@@ -374,26 +385,28 @@ static void enumerator_destroy(private_enumerator_t *this)
static enumerator_t* create_enumerator(private_hashtable_t *this)
{
private_enumerator_t *enumerator = malloc_thing(private_enumerator_t);
-
+
enumerator->enumerator.enumerate = (void*)enumerate;
enumerator->enumerator.destroy = (void*)enumerator_destroy;
enumerator->table = this;
enumerator->row = 0;
enumerator->current = NULL;
-
+
return &enumerator->enumerator;
}
-
+
/**
* Implementation of hashtable_t.destroy
*/
static void destroy(private_hashtable_t *this)
{
+ linked_list_t *list;
u_int row;
- for (row = 0; row < this->capacity; ++row)
+
+ for (row = 0; row < this->capacity; row++)
{
- linked_list_t *list;
- if ((list = this->table[row]) != NULL)
+ list = this->table[row];
+ if (list)
{
list->destroy_function(list, free);
}
@@ -411,12 +424,12 @@ hashtable_t *hashtable_create(hashtable_hash_t hash, hashtable_equals_t equals,
private_hashtable_t *this = malloc_thing(private_hashtable_t);
this->public.put = (void*(*)(hashtable_t*,void*,void*))put;
- this->public.get = (void*(*)(hashtable_t*,void*))get;
+ this->public.get = (void*(*)(hashtable_t*,void*))get;
this->public.remove = (void*(*)(hashtable_t*,void*))remove_;
this->public.get_count = (u_int(*)(hashtable_t*))get_count;
this->public.create_enumerator = (enumerator_t*(*)(hashtable_t*))create_enumerator;
this->public.destroy = (void(*)(hashtable_t*))destroy;
-
+
this->count = 0;
this->capacity = 0;
this->mask = 0;
@@ -424,8 +437,9 @@ hashtable_t *hashtable_create(hashtable_hash_t hash, hashtable_equals_t equals,
this->table = NULL;
this->hash = hash;
this->equals = equals;
-
+
init_hashtable(this, capacity);
-
+
return &this->public;
}
+
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-10 05:36:55 +0000