code cleanup: better use of BLI_array_* (grow in larger steps where possible), includ...
[blender.git] / source / blender / blenlib / BLI_ghash.h
index 8f2cd02c35e05c13f8e9a1e2bd0a73a66c5e8d3b..457f098bff7a085d6c6d7dee87d5eee7ba641e69 100644 (file)
@@ -1,6 +1,4 @@
 /*
 /*
- * $Id$
- *
  * ***** BEGIN GPL LICENSE BLOCK *****
  *
  * This program is free software; you can redistribute it and/or
  * ***** BEGIN GPL LICENSE BLOCK *****
  *
  * This program is free software; you can redistribute it and/or
@@ -27,8 +25,8 @@
  * ***** END GPL LICENSE BLOCK *****
  */
  
  * ***** END GPL LICENSE BLOCK *****
  */
  
-#ifndef BLI_GHASH_H
-#define BLI_GHASH_H
+#ifndef __BLI_GHASH_H__
+#define __BLI_GHASH_H__
 
 /** \file BLI_ghash.h
  *  \ingroup bli
 
 /** \file BLI_ghash.h
  *  \ingroup bli
 extern "C" {
 #endif
 
 extern "C" {
 #endif
 
-#include <stdio.h>
-#include <stdlib.h>
-#include <string.h>
-
-
-#include "BKE_utildefines.h"
-#include "MEM_guardedalloc.h"
-
-#include "BLI_mempool.h"
-#include "BLI_blenlib.h"
-
 typedef unsigned int   (*GHashHashFP)          (const void *key);
 typedef int                            (*GHashCmpFP)           (const void *a, const void *b);
 typedef        void                    (*GHashKeyFreeFP)       (void *key);
 typedef unsigned int   (*GHashHashFP)          (const void *key);
 typedef int                            (*GHashCmpFP)           (const void *a, const void *b);
 typedef        void                    (*GHashKeyFreeFP)       (void *key);
@@ -57,14 +44,14 @@ typedef void                        (*GHashValFreeFP)       (void *val);
 
 typedef struct Entry {
        struct Entry *next;
 
 typedef struct Entry {
        struct Entry *next;
-       
+
        void *key, *val;
 } Entry;
 
 typedef struct GHash {
        GHashHashFP     hashfp;
        GHashCmpFP      cmpfp;
        void *key, *val;
 } Entry;
 
 typedef struct GHash {
        GHashHashFP     hashfp;
        GHashCmpFP      cmpfp;
-       
+
        Entry **buckets;
        struct BLI_mempool *entrypool;
        int nbuckets, nentries, cursize;
        Entry **buckets;
        struct BLI_mempool *entrypool;
        int nbuckets, nentries, cursize;
@@ -76,10 +63,15 @@ typedef struct GHashIterator {
        struct Entry *curEntry;
 } GHashIterator;
 
        struct Entry *curEntry;
 } GHashIterator;
 
-GHash* BLI_ghash_new           (GHashHashFP hashfp, GHashCmpFP cmpfp, const char *info);
-void   BLI_ghash_free          (GHash *gh, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp);
+/* *** */
 
 
-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);
 
 /* *** */
 
 
 /* *** */
 
@@ -88,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.
         * 
         * 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);
        /**
         */
 GHashIterator* BLI_ghashIterator_new           (GHash *gh);
        /**
@@ -97,45 +89,45 @@ 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.
         * 
         * 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.
         *
         */
 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.
         *
         */
 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.
         *
         * 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.
         *
         * 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).
         *
         */
 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);
 
         */
 int                            BLI_ghashIterator_isDone        (GHashIterator *ghi);
 
@@ -148,100 +140,20 @@ unsigned int     BLI_ghashutil_strhash   (const void *key);
 int                            BLI_ghashutil_strcmp    (const void *a, const void *b);
 
 unsigned int   BLI_ghashutil_inthash   (const void *ptr);
 int                            BLI_ghashutil_strcmp    (const void *a, const void *b);
 
 unsigned int   BLI_ghashutil_inthash   (const void *ptr);
-int                            BLI_ghashutil_intcmp(const void *a, const void *b);
-
-/*begin of macro-inlined functions*/
-extern unsigned int hashsizes[];
-
-/*---------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);
-
-       e->key= key;
-       e->val= val;
-       e->next= gh->buckets[hash];
-       gh->buckets[hash]= e;
-       
-       if (++gh->nentries>(float)gh->nbuckets/2) {
-               Entry **old= gh->buckets;
-               int i, nold= gh->nbuckets;
-               
-               gh->nbuckets= hashsizes[++gh->cursize];
-               gh->buckets= (Entry**)MEM_mallocN(gh->nbuckets*sizeof(*gh->buckets), "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;
-                       }
-               }
-               
-               MEM_freeN(old);
-       }
-}
-
-BM_INLINE void* BLI_ghash_lookup(GHash *gh, const 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;
-}
+int                            BLI_ghashutil_intcmp    (const void *a, const void *b);
 
 
-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 = NULL;
+typedef struct GHashPair {
+       const void *first;
+       int second;
+} GHashPair;
 
 
-       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
 
 #ifdef __cplusplus
 }
 #endif
-#endif
+
+#endif /* __BLI_GHASH_H__ */