X-Git-Url: https://www.chiark.greenend.org.uk/ucgi/~mdw/git/disorder/blobdiff_plain/9faa7a88b7419b2d6151ac2c3fa52261c876ee8d..8ab2aa9fd51a89e06d92a4f7c3792aaa4a08cc71:/lib/hash.c

diff --git a/lib/hash.c b/lib/hash.c
index f38e1d9..9dc3469 100644
--- a/lib/hash.c
+++ b/lib/hash.c
@@ -2,32 +2,30 @@
  * This file is part of DisOrder
  * Copyright (C) 2005-2008 Richard Kettlewell
  *
- * This program is free software; you can redistribute it and/or modify
+ * This program is free software: you can redistribute it and/or modify
  * it under the terms of the GNU General Public License as published by
- * the Free Software Foundation; either version 2 of the License, or
+ * the Free Software Foundation, either version 3 of the License, or
  * (at your option) any later version.
- *
- * 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.
- *
+ * 
+ * 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., 59 Temple Place, Suite 330, Boston, MA 02111-1307
- * USA
+ * along with this program.  If not, see <http://www.gnu.org/licenses/>.
  */
-
-#include <config.h>
-#include "types.h"
-
-#include <string.h>
+/** @file lib/hash.c
+ * @brief A simple hash table
+ */
+#include "common.h"
 
 #include "hash.h"
 #include "mem.h"
 #include "log.h"
 #include "kvp.h"
 
+/** @brief One entry in a hash table */
 struct entry {
   struct entry *next;                   /* next entry same key */
   size_t h;                             /* hash of KEY */
@@ -35,6 +33,7 @@ struct entry {
   void *value;                          /* value of this entry */
 };
 
+/** @brief A hash table */
 struct hash {
   size_t nslots;                        /* number of slots */
   size_t nitems;                        /* total number of entries */
@@ -42,6 +41,10 @@ struct hash {
   size_t valuesize;                     /* size of a value */
 };
 
+/** @brief Hash function
+ * @param key Key to hash
+ * @return Hash code
+ */
 static size_t hashfn(const char *key) {
   size_t i = 0;
 
@@ -50,6 +53,9 @@ static size_t hashfn(const char *key) {
   return i;
 }
 
+/** @brief Expand a hash table
+ * @param h Hash table to expand
+ */
 static void grow(hash *h) {
   size_t n, newnslots;
   struct entry **newslots, *e, *f;
@@ -69,6 +75,10 @@ static void grow(hash *h) {
   h->nslots = newnslots;
 }
 
+/** @brief Create a new hash table
+ * @param valuesize Size of value type
+ * @return Hash table
+ */
 hash *hash_new(size_t valuesize) {
   hash *h = xmalloc(sizeof *h);
 
@@ -78,6 +88,18 @@ hash *hash_new(size_t valuesize) {
   return h;
 }
 
+/** @brief Add an element to a hash table
+ * @param h Hash table
+ * @param key Key
+ * @param value New value (will be shallow-copied)
+ * @param mode Add mode
+ * @return 0 on success, -1 if the value could not be added
+ *
+ * Possible add modes are:
+ * - @ref HASH_INSERT - key must not exist yet
+ * - @ref HASH_REPLACE - key must already exist
+ * - @ref HASH_INSERT_OR_REPLACE - key may or may not exist
+ */
 int hash_add(hash *h, const char *key, const void *value, int mode) {
   size_t n = hashfn(key);
   struct entry *e;
@@ -107,6 +129,11 @@ int hash_add(hash *h, const char *key, const void *value, int mode) {
   }
 }
 
+/** @brief Remove an element from a hash table
+ * @param h Hash table
+ * @param key Key to remove
+ * @return 0 on success, -1 if the key wasn't found
+ */
 int hash_remove(hash *h, const char *key) {
   size_t n = hashfn(key);
   struct entry *e, **ee;
@@ -122,6 +149,13 @@ int hash_remove(hash *h, const char *key) {
     return -1;
 }
 
+/** @brief Find an item in a hash table
+ * @param h Hash table
+ * @param key Key to find
+ * @return Pointer to value or NULL if not found
+ *
+ * The return value points inside the hash table and should not be modified.
+ */
 void *hash_find(hash *h, const char *key) {
   size_t n = hashfn(key);
   struct entry *e;
@@ -132,6 +166,21 @@ void *hash_find(hash *h, const char *key) {
   return 0;
 }
 
+/** @brief Visit every item in a hash table
+ * @param h Hash Table
+ * @param callback Function to call for each item
+ * @param u Passed to @p callback
+ * @return 0 on completion, else last return from @p callback
+ *
+ * @p callback should return 0 to continue or non-0 to stop.  The @p key and @p
+ * value pointers passed to it point into the hash table and should not be
+ * modified.
+ *
+ * It's safe to remove items from inside the callback including the visited
+ * one.  It is not safe to add items from inside the callback.
+ *
+ * No particular ordering is used.
+ */
 int hash_foreach(hash *h,
                  int (*callback)(const char *key, void *value, void *u),
                  void *u) {
@@ -148,10 +197,22 @@ int hash_foreach(hash *h,
   return 0;
 }
 
+/** @brief Count the size of a hash table
+ * @param h Hash table
+ * @return Number of elements in hash table
+ */
 size_t hash_count(hash *h) {
   return h->nitems;
 }
 
+/** @brief Get all the keys of a hash table
+ * @param h Hash table
+ * @return NULL-terminated list of keys
+ *
+ * The keys point into the hash table itself and should not be modified.
+ *
+ * No particular ordering is used.
+ */
 char **hash_keys(hash *h) {
   size_t n;
   char **vec = xcalloc(h->nitems + 1, sizeof (char *)), **vp = vec;