===================================================================
@@ -17,15 +17,9 @@
*
*/
-
-
-
-
#include "main.h"
#include "hash.h"
-
-
/* clears the hash */
void hash_init(struct hashtable_t *hash)
{
@@ -37,9 +31,9 @@
hash->table[i] = NULL;
}
-/* remove the hash structure. if hashdata_free_cb != NULL,
- * this function will be called to remove the elements inside of the hash.
- * if you don't remove the elements, memory might be leaked. */
+/* remove the hash structure. if hashdata_free_cb != NULL, this function will be
+ * called to remove the elements inside of the hash. if you don't remove the
+ * elements, memory might be leaked. */
void hash_delete(struct hashtable_t *hash, hashdata_free_cb free_cb)
{
struct element_t *bucket, *last_bucket;
@@ -56,7 +50,6 @@
bucket = bucket->next;
kfree(last_bucket);
}
-
}
hash_destroy(hash);
@@ -69,9 +62,10 @@
kfree(hash);
}
-/* iterate though the hash. first element is selected with iter_in NULL.
- * use the returned iterator to access the elements until hash_it_t returns NULL. */
-struct hash_it_t *hash_iterate(struct hashtable_t *hash, struct hash_it_t *iter_in)
+/* iterate though the hash. first element is selected with iter_in NULL. use
+ * the returned iterator to access the elements until hash_it_t returns NULL. */
+struct hash_it_t *hash_iterate(struct hashtable_t *hash,
+ struct hash_it_t *iter_in)
{
struct hash_it_t *iter;
@@ -81,19 +75,22 @@
iter->bucket = NULL;
iter->prev_bucket = NULL;
} else {
- iter= iter_in;
+ iter = iter_in;
}
- /* sanity checks first (if our bucket got deleted in the last iteration): */
+ /* sanity checks first (if our bucket got deleted in the last
+ * iteration): */
if (iter->bucket != NULL) {
if (iter->first_bucket != NULL) {
- /* we're on the first element and it got removed after the last iteration. */
+ /* we're on the first element and it got removed after
+ * the last iteration. */
if ((*iter->first_bucket) != iter->bucket) {
/* there are still other elements in the list */
if ((*iter->first_bucket) != NULL) {
iter->prev_bucket = NULL;
iter->bucket = (*iter->first_bucket);
- iter->first_bucket = &hash->table[iter->index];
+ iter->first_bucket =
+ &hash->table[iter->index];
return iter;
} else {
iter->bucket = NULL;
@@ -101,9 +98,10 @@
}
} else if (iter->prev_bucket != NULL) {
/*
- * we're not on the first element, and the bucket got removed after the last iteration.
- * the last bucket's next pointer is not pointing to our actual bucket anymore.
- * select the next.
+ * we're not on the first element, and the bucket got
+ * removed after the last iteration. the last bucket's
+ * next pointer is not pointing to our actual bucket
+ * anymore. select the next.
*/
if (iter->prev_bucket->next != iter->bucket)
iter->bucket = iter->prev_bucket;
@@ -120,11 +118,12 @@
}
}
- /* if not returned yet, we've reached the last one on the index and have to search forward */
+ /* if not returned yet, we've reached the last one on the index and have
+ * to search forward */
iter->index++;
/* go through the entries of the hash table */
while (iter->index < hash->size) {
- if ((hash->table[iter->index]) != NULL){
+ if ((hash->table[iter->index]) != NULL) {
iter->prev_bucket = NULL;
iter->bucket = hash->table[iter->index];
iter->first_bucket = &hash->table[iter->index];
@@ -140,7 +139,8 @@
}
/* allocates and clears the hash */
-struct hashtable_t *hash_new(int size, hashdata_compare_cb compare, hashdata_choose_cb choose)
+struct hashtable_t *hash_new(int size, hashdata_compare_cb compare,
+ hashdata_choose_cb choose)
{
struct hashtable_t *hash;
@@ -183,7 +183,7 @@
}
/* found the tail of the list, add new element */
- bucket = kmalloc(sizeof(struct element_t),GFP_ATOMIC);
+ bucket = kmalloc(sizeof(struct element_t), GFP_ATOMIC);
if (bucket == NULL)
return -1;
@@ -201,7 +201,8 @@
return 0;
}
-/* finds data, based on the key in keydata. returns the found data on success, or NULL on error */
+/* finds data, based on the key in keydata. returns the found data on success,
+ * or NULL on error */
void *hash_find(struct hashtable_t *hash, void *keydata)
{
int index;
@@ -220,9 +221,10 @@
return NULL;
}
-/* remove bucket (this might be used in hash_iterate() if you already found the bucket
- * you want to delete and don't need the overhead to find it again with hash_remove().
- * But usually, you don't want to use this function, as it fiddles with hash-internals. */
+/* remove bucket (this might be used in hash_iterate() if you already found the
+ * bucket you want to delete and don't need the overhead to find it again with
+ * hash_remove(). But usually, you don't want to use this function, as it
+ * fiddles with hash-internals. */
void *hash_remove_bucket(struct hashtable_t *hash, struct hash_it_t *hash_it_t)
{
void *data_save;
@@ -240,10 +242,10 @@
return data_save;
}
-/* removes data from hash, if found. returns pointer do data on success,
- * so you can remove the used structure yourself, or NULL on error .
- * data could be the structure you use with just the key filled,
- * we just need the key for comparing. */
+/* removes data from hash, if found. returns pointer do data on success, so you
+ * can remove the used structure yourself, or NULL on error . data could be the
+ * structure you use with just the key filled, we just need the key for
+ * comparing. */
void *hash_remove(struct hashtable_t *hash, void *data)
{
struct hash_it_t hash_it_t;
@@ -254,18 +256,22 @@
while (hash_it_t.bucket != NULL) {
if (hash->compare(hash_it_t.bucket->data, data)) {
- hash_it_t.first_bucket = (hash_it_t.bucket == hash->table[hash_it_t.index] ? &hash->table[ hash_it_t.index ] : NULL);
+ hash_it_t.first_bucket =
+ (hash_it_t.bucket ==
+ hash->table[hash_it_t.index] ?
+ &hash->table[hash_it_t.index] : NULL);
return hash_remove_bucket(hash, &hash_it_t);
}
hash_it_t.prev_bucket = hash_it_t.bucket;
- hash_it_t.bucket= hash_it_t.bucket->next;
+ hash_it_t.bucket = hash_it_t.bucket->next;
}
return NULL;
}
-/* resize the hash, returns the pointer to the new hash or NULL on error. removes the old hash on success. */
+/* resize the hash, returns the pointer to the new hash or NULL on
+ * error. removes the old hash on success. */
struct hashtable_t *hash_resize(struct hashtable_t *hash, int size)
{
struct hashtable_t *new_hash;
@@ -288,7 +294,8 @@
}
}
- /* remove hash and eventual overflow buckets but not the content itself. */
+ /* remove hash and eventual overflow buckets but not the content
+ * itself. */
hash_delete(hash, NULL);
return new_hash;
===================================================================
@@ -17,22 +17,16 @@
*
*/
-
-
-
-
#ifndef _BATMAN_HASH_H
#define _BATMAN_HASH_H
-
-
typedef int (*hashdata_compare_cb)(void *, void *);
typedef int (*hashdata_choose_cb)(void *, int);
typedef void (*hashdata_free_cb)(void *);
struct element_t {
- void *data; /* pointer to the data */
- struct element_t *next; /* overflow bucket pointer */
+ void *data; /* pointer to the data */
+ struct element_t *next; /* overflow bucket pointer */
};
struct hash_it_t {
@@ -43,56 +37,61 @@
};
struct hashtable_t {
- struct element_t **table; /* the hashtable itself, with the buckets */
- int elements; /* number of elements registered */
- int size; /* size of hashtable */
- hashdata_compare_cb compare; /* callback to a compare function.
- * should compare 2 element datas for their keys,
- * return 0 if same and not 0 if not same */
- hashdata_choose_cb choose; /* the hashfunction, should return an index based
- * on the key in the data of the first argument
- * and the size the second */
+ struct element_t **table; /* the hashtable itself, with the buckets */
+ int elements; /* number of elements registered */
+ int size; /* size of hashtable */
+ hashdata_compare_cb compare;/* callback to a compare function. should
+ * compare 2 element datas for their keys,
+ * return 0 if same and not 0 if not
+ * same */
+ hashdata_choose_cb choose; /* the hashfunction, should return an index
+ * based on the key in the data of the first
+ * argument and the size the second */
};
/* clears the hash */
-void hash_init(struct hashtable_t *hash);
+void hash_init(struct hashtable_t *hash);
/* allocates and clears the hash */
-struct hashtable_t *hash_new(int size, hashdata_compare_cb compare, hashdata_choose_cb choose);
+struct hashtable_t *hash_new(int size, hashdata_compare_cb compare,
+ hashdata_choose_cb choose);
-/* remove bucket (this might be used in hash_iterate() if you already found the bucket
- * you want to delete and don't need the overhead to find it again with hash_remove().
- * But usually, you don't want to use this function, as it fiddles with hash-internals. */
-void *hash_remove_bucket(struct hashtable_t *hash, struct hash_it_t *hash_it_t);
+/* remove bucket (this might be used in hash_iterate() if you already found the
+ * bucket you want to delete and don't need the overhead to find it again with
+ * hash_remove(). But usually, you don't want to use this function, as it
+ * fiddles with hash-internals. */
+void *hash_remove_bucket(struct hashtable_t *hash, struct hash_it_t *hash_it_t);
-/* remove the hash structure. if hashdata_free_cb != NULL,
- * this function will be called to remove the elements inside of the hash.
- * if you don't remove the elements, memory might be leaked. */
-void hash_delete(struct hashtable_t *hash, hashdata_free_cb free_cb);
+/* remove the hash structure. if hashdata_free_cb != NULL, this function will be
+ * called to remove the elements inside of the hash. if you don't remove the
+ * elements, memory might be leaked. */
+void hash_delete(struct hashtable_t *hash, hashdata_free_cb free_cb);
/* free only the hashtable and the hash itself. */
-void hash_destroy(struct hashtable_t *hash);
+void hash_destroy(struct hashtable_t *hash);
/* adds data to the hashtable. returns 0 on success, -1 on error */
-int hash_add(struct hashtable_t *hash, void *data);
+int hash_add(struct hashtable_t *hash, void *data);
-/* removes data from hash, if found. returns pointer do data on success,
- * so you can remove the used structure yourself, or NULL on error .
- * data could be the structure you use with just the key filled,
- * we just need the key for comparing. */
-void *hash_remove(struct hashtable_t *hash, void *data);
+/* removes data from hash, if found. returns pointer do data on success, so you
+ * can remove the used structure yourself, or NULL on error . data could be the
+ * structure you use with just the key filled, we just need the key for
+ * comparing. */
+void *hash_remove(struct hashtable_t *hash, void *data);
-/* finds data, based on the key in keydata. returns the found data on success, or NULL on error */
-void *hash_find(struct hashtable_t *hash, void *keydata);
+/* finds data, based on the key in keydata. returns the found data on success,
+ * or NULL on error */
+void *hash_find(struct hashtable_t *hash, void *keydata);
-/* resize the hash, returns the pointer to the new hash or NULL on error. removes the old hash on success */
-struct hashtable_t *hash_resize(struct hashtable_t *hash, int size);
+/* resize the hash, returns the pointer to the new hash or NULL on
+ * error. removes the old hash on success */
+struct hashtable_t *hash_resize(struct hashtable_t *hash, int size);
-/* print the hash table for debugging */
-void hash_debug( struct hashtable_t *hash);
+/* iterate though the hash. first element is selected with iter_in NULL. use
+ * the returned iterator to access the elements until hash_it_t returns NULL. */
+struct hash_it_t *hash_iterate(struct hashtable_t *hash,
+ struct hash_it_t *iter_in);
-/* iterate though the hash. first element is selected with iter_in NULL.
- * use the returned iterator to access the elements until hash_it_t returns NULL. */
-struct hash_it_t *hash_iterate(struct hashtable_t *hash, struct hash_it_t *iter_in);
-
+/* print the hash table for debugging */
+void hash_debug(struct hashtable_t *hash);
#endif