code cleanup: better use of BLI_array_* (grow in larger steps where possible), includ...
[blender.git] / source / blender / blenlib / BLI_ghash.h
index f394f5a5e2e4331beddec9156ee02552eb5fff8b..457f098bff7a085d6c6d7dee87d5eee7ba641e69 100644 (file)
@@ -1,8 +1,4 @@
-/**
- * A general (pointer -> pointer) hash table ADT
- * 
- * $Id$
- *
+/*
  * ***** BEGIN GPL LICENSE BLOCK *****
  *
  * This program is free software; you can redistribute it and/or
@@ -17,7 +13,7 @@
  *
  * 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.
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
  *
  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
  * All rights reserved.
  * ***** END GPL LICENSE BLOCK *****
  */
  
-#ifndef BLI_GHASH_H
-#define BLI_GHASH_H
-
-#include "stdio.h"
-#include "stdlib.h"
-#include "string.h"
+#ifndef __BLI_GHASH_H__
+#define __BLI_GHASH_H__
 
-#include "BKE_utildefines.h"
-
-#include "BLI_mempool.h"
-#include "BLI_blenlib.h"
+/** \file BLI_ghash.h
+ *  \ingroup bli
+ *  \brief A general (pointer -> pointer) hash table ADT
+ */
 
 #ifdef __cplusplus
-extern "C"
-{
+extern "C" {
 #endif
 
-typedef unsigned int   (*GHashHashFP)          (void *key);
-typedef int                            (*GHashCmpFP)           (void *a, void *b);
+typedef unsigned int   (*GHashHashFP)          (const void *key);
+typedef int                            (*GHashCmpFP)           (const void *a, const void *b);
 typedef        void                    (*GHashKeyFreeFP)       (void *key);
 typedef void                   (*GHashValFreeFP)       (void *val);
 
 typedef struct Entry {
        struct Entry *next;
-       
+
        void *key, *val;
 } Entry;
 
 typedef struct GHash {
        GHashHashFP     hashfp;
        GHashCmpFP      cmpfp;
-       
+
        Entry **buckets;
        struct BLI_mempool *entrypool;
        int nbuckets, nentries, cursize;
@@ -72,15 +63,15 @@ typedef struct GHashIterator {
        struct Entry *curEntry;
 } GHashIterator;
 
-GHash* BLI_ghash_new(GHashHashFP hashfp, GHashCmpFP cmpfp);
-void BLI_ghash_free(GHash *gh, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp);
-
-//BM_INLINE void       BLI_ghash_insert        (GHash *gh, void *key, void *val);
-//BM_INLINE int                BLI_ghash_remove        (GHash *gh, void *key, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp);
-//BM_INLINE void*      BLI_ghash_lookup        (GHash *gh, void *key);
-//BM_INLINE int                BLI_ghash_haskey        (GHash *gh, void *key);
+/* *** */
 
-int            BLI_ghash_size          (GHash *gh);
+GHash* BLI_ghash_new   (GHashHashFP hashfp, GHashCmpFP cmpfp, const char *info);
+void   BLI_ghash_free  (GHash *gh, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp);
+void   BLI_ghash_insert(GHash *gh, void *key, void *val);
+void * BLI_ghash_lookup(GHash *gh, const void *key);
+int    BLI_ghash_remove(GHash *gh, void *key, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp);
+int    BLI_ghash_haskey(GHash *gh, void *key);
+int       BLI_ghash_size  (GHash *gh);
 
 /* *** */
 
@@ -89,8 +80,8 @@ int           BLI_ghash_size          (GHash *gh);
         * while the iterator is in use, and the iterator will step exactly
         * BLI_ghash_size(gh) times before becoming done.
         * 
-        * @param gh The GHash to iterate over.
-        * @return Pointer to a new DynStr.
+        * \param gh The GHash to iterate over.
+        * \return Pointer to a new DynStr.
         */
 GHashIterator* BLI_ghashIterator_new           (GHash *gh);
        /**
@@ -98,178 +89,71 @@ GHashIterator*     BLI_ghashIterator_new           (GHash *gh);
         * be mutated while the iterator is in use, and the iterator will
         * step exactly BLI_ghash_size(gh) times before becoming done.
         * 
-        * @param ghi The GHashIterator to initialize.
-        * @param gh The GHash to iterate over.
+        * \param ghi The GHashIterator to initialize.
+        * \param gh The GHash to iterate over.
         */
 void BLI_ghashIterator_init(GHashIterator *ghi, GHash *gh);
        /**
         * Free a GHashIterator.
         *
-        * @param ghi The iterator to free.
+        * \param ghi The iterator to free.
         */
 void                   BLI_ghashIterator_free          (GHashIterator *ghi);
 
        /**
         * Retrieve the key from an iterator.
         *
-        * @param ghi The iterator.
-        * @return The key at the current index, or NULL if the 
+        * \param ghi The iterator.
+        * \return The key at the current index, or NULL if the 
         * iterator is done.
         */
 void*                  BLI_ghashIterator_getKey        (GHashIterator *ghi);
        /**
         * Retrieve the value from an iterator.
         *
-        * @param ghi The iterator.
-        * @return The value at the current index, or NULL if the 
+        * \param ghi The iterator.
+        * \return The value at the current index, or NULL if the 
         * iterator is done.
         */
 void*                  BLI_ghashIterator_getValue      (GHashIterator *ghi);
        /**
         * Steps the iterator to the next index.
         *
-        * @param ghi The iterator.
+        * \param ghi The iterator.
         */
 void                   BLI_ghashIterator_step          (GHashIterator *ghi);
        /**
         * Determine if an iterator is done (has reached the end of
         * the hash table).
         *
-        * @param ghi The iterator.
-        * @return True if done, False otherwise.
+        * \param ghi The iterator.
+        * \return True if done, False otherwise.
         */
 int                            BLI_ghashIterator_isDone        (GHashIterator *ghi);
 
 /* *** */
 
-unsigned int   BLI_ghashutil_ptrhash   (void *key);
-int    BLI_ghashutil_ptrcmp    (void *a, void *b);
-
-unsigned int   BLI_ghashutil_strhash   (void *key);
-int                            BLI_ghashutil_strcmp    (void *a, void *b);
-
-unsigned int   BLI_ghashutil_inthash   (void *ptr);
-int                            BLI_ghashutil_intcmp(void *a, void *b);
+unsigned int   BLI_ghashutil_ptrhash   (const void *key);
+int                            BLI_ghashutil_ptrcmp    (const void *a, const void *b);
 
-/*begin of macro-inlined functions*/
-unsigned int hashsizes[];
+unsigned int   BLI_ghashutil_strhash   (const void *key);
+int                            BLI_ghashutil_strcmp    (const void *a, const void *b);
 
-#if 0
-#define BLI_ghash_insert(gh, _k, _v){\
-       unsigned int _hash= (gh)->hashfp(_k)%gh->nbuckets;\
-       Entry *_e= BLI_mempool_alloc((gh)->entrypool);\
-       _e->key= _k;\
-       _e->val= _v;\
-       _e->next= (gh)->buckets[_hash];\
-       (gh)->buckets[_hash]= _e;\
-       if (++(gh)->nentries>(gh)->nbuckets*3) {\
-               Entry *_e, **_old= (gh)->buckets;\
-               int _i, _nold= (gh)->nbuckets;\
-               (gh)->nbuckets= hashsizes[++(gh)->cursize];\
-               (gh)->buckets= malloc((gh)->nbuckets*sizeof(*(gh)->buckets));\
-               memset((gh)->buckets, 0, (gh)->nbuckets*sizeof(*(gh)->buckets));\
-               for (_i=0; _i<_nold; _i++) {\
-                       for (_e= _old[_i]; _e;) {\
-                               Entry *_n= _e->next;\
-                               _hash= (gh)->hashfp(_e->key)%(gh)->nbuckets;\
-                               _e->next= (gh)->buckets[_hash];\
-                               (gh)->buckets[_hash]= _e;\
-                               _e= _n;\
-                       }\
-               }\
-               free(_old); } }
-#endif
+unsigned int   BLI_ghashutil_inthash   (const void *ptr);
+int                            BLI_ghashutil_intcmp    (const void *a, const void *b);
 
-/*---------inlined functions---------*/
-BM_INLINE void BLI_ghash_insert(GHash *gh, void *key, void *val) {
-       unsigned int hash= gh->hashfp(key)%gh->nbuckets;
-       Entry *e= (Entry*) BLI_mempool_alloc(gh->entrypool);
+typedef struct GHashPair {
+       const void *first;
+       int second;
+} GHashPair;
 
-       e->key= key;
-       e->val= val;
-       e->next= gh->buckets[hash];
-       gh->buckets[hash]= e;
-       
-       if (++gh->nentries>gh->nbuckets*3) {
-               Entry *e, **old= gh->buckets;
-               int i, nold= gh->nbuckets;
-               
-               gh->nbuckets= hashsizes[++gh->cursize];
-               gh->buckets= (Entry**)malloc(gh->nbuckets*sizeof(*gh->buckets));
-               memset(gh->buckets, 0, gh->nbuckets*sizeof(*gh->buckets));
-               
-               for (i=0; i<nold; i++) {
-                       for (e= old[i]; e;) {
-                               Entry *n= e->next;
-                               
-                               hash= gh->hashfp(e->key)%gh->nbuckets;
-                               e->next= gh->buckets[hash];
-                               gh->buckets[hash]= e;
-                               
-                               e= n;
-                       }
-               }
-               
-               free(old);
-       }
-}
-
-BM_INLINE void* BLI_ghash_lookup(GHash *gh, void *key) 
-{
-       if(gh) {
-               unsigned int hash= gh->hashfp(key)%gh->nbuckets;
-               Entry *e;
-               
-               for (e= gh->buckets[hash]; e; e= e->next)
-                       if (gh->cmpfp(key, e->key)==0)
-                               return e->val;
-       }       
-       return NULL;
-}
-
-BM_INLINE int BLI_ghash_remove (GHash *gh, void *key, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp)
-{
-       unsigned int hash= gh->hashfp(key)%gh->nbuckets;
-       Entry *e;
-       Entry *p = 0;
-
-       for (e= gh->buckets[hash]; e; e= e->next) {
-               if (gh->cmpfp(key, e->key)==0) {
-                       Entry *n= e->next;
-
-                       if (keyfreefp) keyfreefp(e->key);
-                       if (valfreefp) valfreefp(e->val);
-                       BLI_mempool_free(gh->entrypool, e);
-
-
-                       e= n;
-                       if (p)
-                               p->next = n;
-                       else
-                               gh->buckets[hash] = n;
-
-                       --gh->nentries;
-                       return 1;
-               }
-               p = e;
-       }
-       return 0;
-}
-
-BM_INLINE int BLI_ghash_haskey(GHash *gh, void *key) {
-       unsigned int hash= gh->hashfp(key)%gh->nbuckets;
-       Entry *e;
-       
-       for (e= gh->buckets[hash]; e; e= e->next)
-               if (gh->cmpfp(key, e->key)==0)
-                       return 1;
-       
-       return 0;
-}
+GHashPair*             BLI_ghashutil_pairalloc (const void *first, int second);
+unsigned int   BLI_ghashutil_pairhash  (const void *ptr);
+int                            BLI_ghashutil_paircmp   (const void *a, const void *b);
+void                   BLI_ghashutil_pairfree  (void *ptr);
 
 #ifdef __cplusplus
 }
 #endif
 
-#endif
+#endif /* __BLI_GHASH_H__ */