summaryrefslogtreecommitdiff
path: root/src/hashmap.c
diff options
context:
space:
mode:
authorMukund Sivaraman <muks@banu.com>2009-09-15 01:11:25 +0530
committerMukund Sivaraman <muks@banu.com>2009-09-15 01:11:25 +0530
commit7b9234f394b688991a5b601ff1e487a19de29870 (patch)
treeccdb923e457666c174311bdf0f2ca4370e27e70c /src/hashmap.c
parent2cb677759236fe54c24c1ce099a61f54bace3f73 (diff)
downloadtinyproxy-7b9234f394b688991a5b601ff1e487a19de29870.tar.gz
tinyproxy-7b9234f394b688991a5b601ff1e487a19de29870.zip
Indent code to Tinyproxy coding style
The modified files were indented with GNU indent using the following command: indent -npro -kr -i8 -ts8 -sob -l80 -ss -cs -cp1 -bs -nlps -nprs -pcs \ -saf -sai -saw -sc -cdw -ce -nut -il0 No other changes of any sort were made.
Diffstat (limited to '')
-rw-r--r--src/hashmap.c597
1 files changed, 283 insertions, 314 deletions
diff --git a/src/hashmap.c b/src/hashmap.c
index 4b16941..74eb9c1 100644
--- a/src/hashmap.c
+++ b/src/hashmap.c
@@ -37,26 +37,23 @@
* internal use. It stores the number of buckets the hashmap was created
* with.
*/
-struct hashentry_s
-{
- char *key;
- void *data;
- size_t len;
+struct hashentry_s {
+ char *key;
+ void *data;
+ size_t len;
- struct hashentry_s *prev, *next;
+ struct hashentry_s *prev, *next;
};
-struct hashbucket_s
-{
- struct hashentry_s *head, *tail;
+struct hashbucket_s {
+ struct hashentry_s *head, *tail;
};
-struct hashmap_s
-{
- unsigned int size;
- hashmap_iter end_iterator;
+struct hashmap_s {
+ unsigned int size;
+ hashmap_iter end_iterator;
- struct hashbucket_s *buckets;
+ struct hashbucket_s *buckets;
};
/*
@@ -68,27 +65,25 @@ struct hashmap_s
*
* If any of the arguments are invalid a negative number is returned.
*/
-static int
-hashfunc (const char *key, unsigned int size)
+static int hashfunc (const char *key, unsigned int size)
{
- uint32_t hash;
+ uint32_t hash;
- if (key == NULL)
- return -EINVAL;
- if (size == 0)
- return -ERANGE;
+ if (key == NULL)
+ return -EINVAL;
+ if (size == 0)
+ return -ERANGE;
- for (hash = tolower (*key++); *key != '\0'; key++)
- {
- uint32_t bit = (hash & 1) ? (1 << (sizeof (uint32_t) - 1)) : 0;
+ for (hash = tolower (*key++); *key != '\0'; key++) {
+ uint32_t bit = (hash & 1) ? (1 << (sizeof (uint32_t) - 1)) : 0;
- hash >>= 1;
+ hash >>= 1;
- hash += tolower (*key) + bit;
- }
+ hash += tolower (*key) + bit;
+ }
- /* Keep the hash within the table limits */
- return hash % size;
+ /* Keep the hash within the table limits */
+ return hash % size;
}
/*
@@ -98,31 +93,30 @@ hashfunc (const char *key, unsigned int size)
*
* NULLs are also returned if memory could not be allocated for hashmap.
*/
-hashmap_t
-hashmap_create (unsigned int nbuckets)
+hashmap_t hashmap_create (unsigned int nbuckets)
{
- struct hashmap_s *ptr;
-
- if (nbuckets == 0)
- return NULL;
-
- ptr = (struct hashmap_s *)safecalloc (1, sizeof (struct hashmap_s));
- if (!ptr)
- return NULL;
-
- ptr->size = nbuckets;
- ptr->buckets = (struct hashbucket_s *)safecalloc (nbuckets,
- sizeof (struct hashbucket_s));
- if (!ptr->buckets)
- {
- safefree (ptr);
- return NULL;
- }
+ struct hashmap_s *ptr;
+
+ if (nbuckets == 0)
+ return NULL;
+
+ ptr = (struct hashmap_s *) safecalloc (1, sizeof (struct hashmap_s));
+ if (!ptr)
+ return NULL;
+
+ ptr->size = nbuckets;
+ ptr->buckets = (struct hashbucket_s *) safecalloc (nbuckets,
+ sizeof (struct
+ hashbucket_s));
+ if (!ptr->buckets) {
+ safefree (ptr);
+ return NULL;
+ }
- /* This points to "one" past the end of the hashmap. */
- ptr->end_iterator = 0;
+ /* This points to "one" past the end of the hashmap. */
+ ptr->end_iterator = 0;
- return ptr;
+ return ptr;
}
/*
@@ -132,28 +126,26 @@ hashmap_create (unsigned int nbuckets)
* Returns: 0 if the function completed successfully
* negative number is returned if "entry" was NULL
*/
-static inline int
-delete_hashbucket (struct hashbucket_s *bucket)
+static inline int delete_hashbucket (struct hashbucket_s *bucket)
{
- struct hashentry_s *nextptr;
- struct hashentry_s *ptr;
+ struct hashentry_s *nextptr;
+ struct hashentry_s *ptr;
- if (bucket == NULL || bucket->head == NULL)
- return -EINVAL;
+ if (bucket == NULL || bucket->head == NULL)
+ return -EINVAL;
- ptr = bucket->head;
- while (ptr)
- {
- nextptr = ptr->next;
+ ptr = bucket->head;
+ while (ptr) {
+ nextptr = ptr->next;
- safefree (ptr->key);
- safefree (ptr->data);
- safefree (ptr);
+ safefree (ptr->key);
+ safefree (ptr->data);
+ safefree (ptr);
- ptr = nextptr;
- }
+ ptr = nextptr;
+ }
- return 0;
+ return 0;
}
/*
@@ -162,26 +154,23 @@ delete_hashbucket (struct hashbucket_s *bucket)
* Returns: 0 on success
* negative if a NULL "map" was supplied
*/
-int
-hashmap_delete (hashmap_t map)
+int hashmap_delete (hashmap_t map)
{
- unsigned int i;
+ unsigned int i;
- if (map == NULL)
- return -EINVAL;
+ if (map == NULL)
+ return -EINVAL;
- for (i = 0; i != map->size; i++)
- {
- if (map->buckets[i].head != NULL)
- {
- delete_hashbucket (&map->buckets[i]);
+ for (i = 0; i != map->size; i++) {
+ if (map->buckets[i].head != NULL) {
+ delete_hashbucket (&map->buckets[i]);
+ }
}
- }
- safefree (map->buckets);
- safefree (map);
+ safefree (map->buckets);
+ safefree (map);
- return 0;
+ return 0;
}
/*
@@ -197,67 +186,65 @@ hashmap_delete (hashmap_t map)
int
hashmap_insert (hashmap_t map, const char *key, const void *data, size_t len)
{
- struct hashentry_s *ptr;
- int hash;
- char *key_copy;
- void *data_copy;
-
- assert (map != NULL);
- assert (key != NULL);
- assert (data != NULL);
- assert (len > 0);
-
- if (map == NULL || key == NULL)
- return -EINVAL;
- if (!data || len < 1)
- return -ERANGE;
-
- hash = hashfunc (key, map->size);
- if (hash < 0)
- return hash;
-
- /*
- * First make copies of the key and data in case there is a memory
- * problem later.
- */
- key_copy = safestrdup (key);
- if (!key_copy)
- return -ENOMEM;
-
- data_copy = safemalloc (len);
- if (!data_copy)
- {
- safefree (key_copy);
- return -ENOMEM;
- }
- memcpy (data_copy, data, len);
-
- ptr = (struct hashentry_s *)safemalloc (sizeof (struct hashentry_s));
- if (!ptr)
- {
- safefree (key_copy);
- safefree (data_copy);
- return -ENOMEM;
- }
-
- ptr->key = key_copy;
- ptr->data = data_copy;
- ptr->len = len;
-
- /*
- * Now add the entry to the end of the bucket chain.
- */
- ptr->next = NULL;
- ptr->prev = map->buckets[hash].tail;
- if (map->buckets[hash].tail)
- map->buckets[hash].tail->next = ptr;
-
- map->buckets[hash].tail = ptr;
- if (!map->buckets[hash].head)
- map->buckets[hash].head = ptr;
-
- map->end_iterator++;
- return 0;
+ struct hashentry_s *ptr;
+ int hash;
+ char *key_copy;
+ void *data_copy;
+
+ assert (map != NULL);
+ assert (key != NULL);
+ assert (data != NULL);
+ assert (len > 0);
+
+ if (map == NULL || key == NULL)
+ return -EINVAL;
+ if (!data || len < 1)
+ return -ERANGE;
+
+ hash = hashfunc (key, map->size);
+ if (hash < 0)
+ return hash;
+
+ /*
+ * First make copies of the key and data in case there is a memory
+ * problem later.
+ */
+ key_copy = safestrdup (key);
+ if (!key_copy)
+ return -ENOMEM;
+
+ data_copy = safemalloc (len);
+ if (!data_copy) {
+ safefree (key_copy);
+ return -ENOMEM;
+ }
+ memcpy (data_copy, data, len);
+
+ ptr = (struct hashentry_s *) safemalloc (sizeof (struct hashentry_s));
+ if (!ptr) {
+ safefree (key_copy);
+ safefree (data_copy);
+ return -ENOMEM;
+ }
+
+ ptr->key = key_copy;
+ ptr->data = data_copy;
+ ptr->len = len;
+
+ /*
+ * Now add the entry to the end of the bucket chain.
+ */
+ ptr->next = NULL;
+ ptr->prev = map->buckets[hash].tail;
+ if (map->buckets[hash].tail)
+ map->buckets[hash].tail->next = ptr;
+
+ map->buckets[hash].tail = ptr;
+ if (!map->buckets[hash].head)
+ map->buckets[hash].head = ptr;
+
+ map->end_iterator++;
+ return 0;
}
/*
@@ -265,18 +252,17 @@ hashmap_insert (hashmap_t map, const char *key, const void *data, size_t len)
*
* Returns: an negative value upon error.
*/
-hashmap_iter
-hashmap_first (hashmap_t map)
+hashmap_iter hashmap_first (hashmap_t map)
{
- assert (map != NULL);
+ assert (map != NULL);
- if (!map)
- return -EINVAL;
+ if (!map)
+ return -EINVAL;
- if (map->end_iterator == 0)
- return -1;
- else
- return 0;
+ if (map->end_iterator == 0)
+ return -1;
+ else
+ return 0;
}
/*
@@ -285,19 +271,18 @@ hashmap_first (hashmap_t map)
* Returns: 1 if it is the end
* 0 otherwise
*/
-int
-hashmap_is_end (hashmap_t map, hashmap_iter iter)
+int hashmap_is_end (hashmap_t map, hashmap_iter iter)
{
- assert (map != NULL);
- assert (iter >= 0);
+ assert (map != NULL);
+ assert (iter >= 0);
- if (!map || iter < 0)
- return -EINVAL;
+ if (!map || iter < 0)
+ return -EINVAL;
- if (iter == map->end_iterator)
- return 1;
- else
- return 0;
+ if (iter == map->end_iterator)
+ return 1;
+ else
+ return 0;
}
/*
@@ -308,41 +293,37 @@ hashmap_is_end (hashmap_t map, hashmap_iter iter)
* an "iterator" pointing at the first key
* an "end-iterator" if the key wasn't found
*/
-hashmap_iter
-hashmap_find (hashmap_t map, const char *key)
+hashmap_iter hashmap_find (hashmap_t map, const char *key)
{
- unsigned int i;
- hashmap_iter iter = 0;
- struct hashentry_s *ptr;
-
- assert (map != NULL);
- assert (key != NULL);
-
- if (!map || !key)
- return -EINVAL;
-
- /*
- * Loop through all the keys and look for the first occurrence
- * of a particular key.
- */
- for (i = 0; i != map->size; i++)
- {
- ptr = map->buckets[i].head;
-
- while (ptr)
- {
- if (strcasecmp (ptr->key, key) == 0)
- {
- /* Found it, so return the current count */
- return iter;
- }
-
- iter++;
- ptr = ptr->next;
+ unsigned int i;
+ hashmap_iter iter = 0;
+ struct hashentry_s *ptr;
+
+ assert (map != NULL);
+ assert (key != NULL);
+
+ if (!map || !key)
+ return -EINVAL;
+
+ /*
+ * Loop through all the keys and look for the first occurrence
+ * of a particular key.
+ */
+ for (i = 0; i != map->size; i++) {
+ ptr = map->buckets[i].head;
+
+ while (ptr) {
+ if (strcasecmp (ptr->key, key) == 0) {
+ /* Found it, so return the current count */
+ return iter;
+ }
+
+ iter++;
+ ptr = ptr->next;
+ }
}
- }
- return iter;
+ return iter;
}
/*
@@ -352,41 +333,37 @@ hashmap_find (hashmap_t map, const char *key)
* negative upon error
*/
ssize_t
-hashmap_return_entry (hashmap_t map, hashmap_iter iter, char **key,
- void **data)
+hashmap_return_entry (hashmap_t map, hashmap_iter iter, char **key, void **data)
{
- unsigned int i;
- struct hashentry_s *ptr;
- hashmap_iter count = 0;
-
- assert (map != NULL);
- assert (iter >= 0);
- assert (iter != map->end_iterator);
- assert (key != NULL);
- assert (data != NULL);
-
- if (!map || iter < 0 || !key || !data)
- return -EINVAL;
-
- for (i = 0; i != map->size; i++)
- {
- ptr = map->buckets[i].head;
- while (ptr)
- {
- if (count == iter)
- {
- /* This is the data so return it */
- *key = ptr->key;
- *data = ptr->data;
- return ptr->len;
- }
-
- ptr = ptr->next;
- count++;
+ unsigned int i;
+ struct hashentry_s *ptr;
+ hashmap_iter count = 0;
+
+ assert (map != NULL);
+ assert (iter >= 0);
+ assert (iter != map->end_iterator);
+ assert (key != NULL);
+ assert (data != NULL);
+
+ if (!map || iter < 0 || !key || !data)
+ return -EINVAL;
+
+ for (i = 0; i != map->size; i++) {
+ ptr = map->buckets[i].head;
+ while (ptr) {
+ if (count == iter) {
+ /* This is the data so return it */
+ *key = ptr->key;
+ *data = ptr->data;
+ return ptr->len;
+ }
+
+ ptr = ptr->next;
+ count++;
+ }
}
- }
- return -EFAULT;
+ return -EFAULT;
}
/*
@@ -396,33 +373,31 @@ hashmap_return_entry (hashmap_t map, hashmap_iter iter, char **key,
* zero if no key is found
* count found
*/
-ssize_t
-hashmap_search (hashmap_t map, const char *key)
+ssize_t hashmap_search (hashmap_t map, const char *key)
{
- int hash;
- struct hashentry_s *ptr;
- ssize_t count = 0;
+ int hash;
+ struct hashentry_s *ptr;
+ ssize_t count = 0;
- if (map == NULL || key == NULL)
- return -EINVAL;
+ if (map == NULL || key == NULL)
+ return -EINVAL;
- hash = hashfunc (key, map->size);
- if (hash < 0)
- return hash;
+ hash = hashfunc (key, map->size);
+ if (hash < 0)
+ return hash;
- ptr = map->buckets[hash].head;
+ ptr = map->buckets[hash].head;
- /* All right, there is an entry here, now see if it's the one we want */
- while (ptr)
- {
- if (strcasecmp (ptr->key, key) == 0)
- ++count;
+ /* All right, there is an entry here, now see if it's the one we want */
+ while (ptr) {
+ if (strcasecmp (ptr->key, key) == 0)
+ ++count;
- /* This entry didn't contain the key; move to the next one */
- ptr = ptr->next;
- }
+ /* This entry didn't contain the key; move to the next one */
+ ptr = ptr->next;
+ }
- return count;
+ return count;
}
/*
@@ -433,33 +408,30 @@ hashmap_search (hashmap_t map, const char *key)
* zero if no entry is found
* length of data for the entry
*/
-ssize_t
-hashmap_entry_by_key (hashmap_t map, const char *key, void **data)
+ssize_t hashmap_entry_by_key (hashmap_t map, const char *key, void **data)
{
- int hash;
- struct hashentry_s *ptr;
+ int hash;
+ struct hashentry_s *ptr;
- if (!map || !key || !data)
- return -EINVAL;
+ if (!map || !key || !data)
+ return -EINVAL;
- hash = hashfunc (key, map->size);
- if (hash < 0)
- return hash;
+ hash = hashfunc (key, map->size);
+ if (hash < 0)
+ return hash;
- ptr = map->buckets[hash].head;
+ ptr = map->buckets[hash].head;
- while (ptr)
- {
- if (strcasecmp (ptr->key, key) == 0)
- {
- *data = ptr->data;
- return ptr->len;
- }
+ while (ptr) {
+ if (strcasecmp (ptr->key, key) == 0) {
+ *data = ptr->data;
+ return ptr->len;
+ }
- ptr = ptr->next;
- }
+ ptr = ptr->next;
+ }
- return 0;
+ return 0;
}
/*
@@ -470,56 +442,53 @@ hashmap_entry_by_key (hashmap_t map, const char *key, void **data)
* 0 if the key was not found
* positive count of entries deleted
*/
-ssize_t
-hashmap_remove (hashmap_t map, const char *key)
+ssize_t hashmap_remove (hashmap_t map, const char *key)
{
- int hash;
- struct hashentry_s *ptr, *next;
- short int deleted = 0;
-
- if (map == NULL || key == NULL)
- return -EINVAL;
-
- hash = hashfunc (key, map->size);
- if (hash < 0)
- return hash;
-
- ptr = map->buckets[hash].head;
- while (ptr)
- {
- if (strcasecmp (ptr->key, key) == 0)
- {
- /*
- * Found the data, now need to remove everything
- * and update the hashmap.
- */
- next = ptr->next;
-
- if (ptr->prev)
- ptr->prev->next = ptr->next;
- if (ptr->next)
- ptr->next->prev = ptr->prev;
-
- if (map->buckets[hash].head == ptr)
- map->buckets[hash].head = ptr->next;
- if (map->buckets[hash].tail == ptr)
- map->buckets[hash].tail = ptr->prev;
-
- safefree (ptr->key);
- safefree (ptr->data);
- safefree (ptr);
-
- ++deleted;
- --map->end_iterator;
-
- ptr = next;
- continue;
+ int hash;
+ struct hashentry_s *ptr, *next;
+ short int deleted = 0;
+
+ if (map == NULL || key == NULL)
+ return -EINVAL;
+
+ hash = hashfunc (key, map->size);
+ if (hash < 0)
+ return hash;
+
+ ptr = map->buckets[hash].head;
+ while (ptr) {
+ if (strcasecmp (ptr->key, key) == 0) {
+ /*
+ * Found the data, now need to remove everything
+ * and update the hashmap.
+ */
+ next = ptr->next;
+
+ if (ptr->prev)
+ ptr->prev->next = ptr->next;
+ if (ptr->next)
+ ptr->next->prev = ptr->prev;
+
+ if (map->buckets[hash].head == ptr)
+ map->buckets[hash].head = ptr->next;
+ if (map->buckets[hash].tail == ptr)
+ map->buckets[hash].tail = ptr->prev;
+
+ safefree (ptr->key);
+ safefree (ptr->data);
+ safefree (ptr);
+
+ ++deleted;
+ --map->end_iterator;
+
+ ptr = next;
+ continue;
+ }
+
+ /* This entry didn't contain the key; move to the next one */
+ ptr = ptr->next;
}
- /* This entry didn't contain the key; move to the next one */
- ptr = ptr->next;
- }
-
- /* The key was not found, so return 0 */
- return deleted;
+ /* The key was not found, so return 0 */
+ return deleted;
}