path: root/source/blender/blenlib/BLI_ghash.h

/*
 * ***** BEGIN GPL LICENSE BLOCK *****
 *
 * 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 (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.
 *
 * 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., 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.
 *
 * The Original Code is: all of this file.
 *
 * Contributor(s): none yet.
 *
 * ***** END GPL LICENSE BLOCK *****
 */
 
#ifndef __BLI_GHASH_H__
#define __BLI_GHASH_H__

/** \file BLI_ghash.h
 *  \ingroup bli
 */

#include "BLI_sys_types.h" /* for bool */
#include "BLI_compiler_attrs.h"

#ifdef __cplusplus
extern "C" {
#endif

#define _GHASH_INTERNAL_ATTR
#ifndef GHASH_INTERNAL_API
#  ifdef __GNUC__
#    undef  _GHASH_INTERNAL_ATTR
#    define _GHASH_INTERNAL_ATTR __attribute__ ((deprecated))  /* not deprecated, just private. */
#  endif
#endif

typedef unsigned int  (*GHashHashFP)     (const void *key);
/** returns false when equal */
typedef bool          (*GHashCmpFP)      (const void *a, const void *b);
typedef void          (*GHashKeyFreeFP)  (void *key);
typedef void          (*GHashValFreeFP)  (void *val);
typedef void         *(*GHashKeyCopyFP)  (const void *key);
typedef void         *(*GHashValCopyFP)  (const void *val);

typedef struct GHash GHash;

typedef struct GHashIterator {
	GHash *gh;
	struct Entry *curEntry;
	unsigned int curBucket;
} GHashIterator;

typedef struct GHashIterState {
	unsigned int curr_bucket _GHASH_INTERNAL_ATTR;
} GHashIterState;



enum {
	GHASH_FLAG_ALLOW_DUPES  = (1 << 0),  /* Only checked for in debug mode */
	GHASH_FLAG_ALLOW_SHRINK = (1 << 1),  /* Allow to shrink buckets' size. */

#ifdef GHASH_INTERNAL_API
	/* Internal usage only */
	GHASH_FLAG_IS_GSET      = (1 << 16),  /* Whether the GHash is actually used as GSet (no value storage). */
#endif
};

/* *** */

GHash *BLI_ghash_new_ex(GHashHashFP hashfp, GHashCmpFP cmpfp, const char *info,
                        const unsigned int nentries_reserve) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT;
GHash *BLI_ghash_new(GHashHashFP hashfp, GHashCmpFP cmpfp, const char *info) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT;
GHash *BLI_ghash_copy(GHash *gh, GHashKeyCopyFP keycopyfp,
                      GHashValCopyFP valcopyfp) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT;
void   BLI_ghash_free(GHash *gh, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp);
void   BLI_ghash_reserve(GHash *gh, const unsigned int nentries_reserve);
void   BLI_ghash_insert(GHash *gh, void *key, void *val);
bool   BLI_ghash_reinsert(GHash *gh, void *key, void *val, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp);
void  *BLI_ghash_replace_key(GHash *gh, void *key);
void  *BLI_ghash_lookup(GHash *gh, const void *key) ATTR_WARN_UNUSED_RESULT;
void  *BLI_ghash_lookup_default(GHash *gh, const void *key, void *val_default) ATTR_WARN_UNUSED_RESULT;
void **BLI_ghash_lookup_p(GHash *gh, const void *key) ATTR_WARN_UNUSED_RESULT;
bool   BLI_ghash_ensure_p(GHash *gh, void *key, void ***r_val) ATTR_WARN_UNUSED_RESULT;
bool   BLI_ghash_ensure_p_ex(GHash *gh, const void *key, void ***r_key, void ***r_val) ATTR_WARN_UNUSED_RESULT;
bool   BLI_ghash_remove(GHash *gh, const void *key, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp);
void   BLI_ghash_clear(GHash *gh, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp);
void   BLI_ghash_clear_ex(GHash *gh, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp,
                          const unsigned int nentries_reserve);
void  *BLI_ghash_popkey(GHash *gh, const void *key, GHashKeyFreeFP keyfreefp) ATTR_WARN_UNUSED_RESULT;
bool   BLI_ghash_haskey(GHash *gh, const void *key) ATTR_WARN_UNUSED_RESULT;
bool   BLI_ghash_pop(GHash *gh, GHashIterState *state, void **r_key, void **r_val) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL();
unsigned int BLI_ghash_size(GHash *gh) ATTR_WARN_UNUSED_RESULT;
void   BLI_ghash_flag_set(GHash *gh, unsigned int flag);
void   BLI_ghash_flag_clear(GHash *gh, unsigned int flag);

/* *** */

GHashIterator *BLI_ghashIterator_new(GHash *gh) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT;

void           BLI_ghashIterator_init(GHashIterator *ghi, GHash *gh);
void           BLI_ghashIterator_free(GHashIterator *ghi);
void           BLI_ghashIterator_step(GHashIterator *ghi);

BLI_INLINE void  *BLI_ghashIterator_getKey(GHashIterator *ghi) ATTR_WARN_UNUSED_RESULT;
BLI_INLINE void  *BLI_ghashIterator_getValue(GHashIterator *ghi) ATTR_WARN_UNUSED_RESULT;
BLI_INLINE void **BLI_ghashIterator_getValue_p(GHashIterator *ghi) ATTR_WARN_UNUSED_RESULT;
BLI_INLINE bool   BLI_ghashIterator_done(GHashIterator *ghi) ATTR_WARN_UNUSED_RESULT;

struct _gh_Entry { void *next, *key, *val; };
BLI_INLINE void  *BLI_ghashIterator_getKey(GHashIterator *ghi)     { return  ((struct _gh_Entry *)ghi->curEntry)->key; }
BLI_INLINE void  *BLI_ghashIterator_getValue(GHashIterator *ghi)   { return  ((struct _gh_Entry *)ghi->curEntry)->val; }
BLI_INLINE void **BLI_ghashIterator_getValue_p(GHashIterator *ghi) { return &((struct _gh_Entry *)ghi->curEntry)->val; }
BLI_INLINE bool   BLI_ghashIterator_done(GHashIterator *ghi)       { return !ghi->curEntry; }
/* disallow further access */
#ifdef __GNUC__
#  pragma GCC poison _gh_Entry
#else
#  define _gh_Entry void
#endif

#define GHASH_ITER(gh_iter_, ghash_) \
	for (BLI_ghashIterator_init(&gh_iter_, ghash_); \
	     BLI_ghashIterator_done(&gh_iter_) == false; \
	     BLI_ghashIterator_step(&gh_iter_))

#define GHASH_ITER_INDEX(gh_iter_, ghash_, i_) \
	for (BLI_ghashIterator_init(&gh_iter_, ghash_), i_ = 0; \
	     BLI_ghashIterator_done(&gh_iter_) == false; \
	     BLI_ghashIterator_step(&gh_iter_), i_++)

/** \name Callbacks for GHash
 *
 * \note '_p' suffix denotes void pointer arg,
 * so we can have functions that take correctly typed args too.
 * \{ */

unsigned int    BLI_ghashutil_ptrhash(const void *key);
bool            BLI_ghashutil_ptrcmp(const void *a, const void *b);

unsigned int    BLI_ghashutil_strhash_n(const char *key, size_t n);
#define         BLI_ghashutil_strhash(key) ( \
                CHECK_TYPE_ANY(key, char *, const char *, const char * const), \
                BLI_ghashutil_strhash_p(key))
unsigned int    BLI_ghashutil_strhash_p(const void *key);
unsigned int    BLI_ghashutil_strhash_p_murmur(const void *key);
bool            BLI_ghashutil_strcmp(const void *a, const void *b);

#define         BLI_ghashutil_inthash(key) ( \
                CHECK_TYPE_ANY(&(key), int *, const int *), \
                BLI_ghashutil_uinthash((unsigned int)key))
unsigned int    BLI_ghashutil_uinthash(unsigned int key);
unsigned int    BLI_ghashutil_inthash_p(const void *ptr);
unsigned int    BLI_ghashutil_inthash_p_murmur(const void *ptr);
unsigned int    BLI_ghashutil_inthash_p_simple(const void *ptr);
bool            BLI_ghashutil_intcmp(const void *a, const void *b);

size_t          BLI_ghashutil_combine_hash(size_t hash_a, size_t hash_b);


unsigned int    BLI_ghashutil_uinthash_v4(const unsigned int key[4]);
#define         BLI_ghashutil_inthash_v4(key) ( \
                CHECK_TYPE_ANY(key, int *, const int *), \
                BLI_ghashutil_uinthash_v4((const unsigned int *)key))
#define         BLI_ghashutil_inthash_v4_p \
   ((GSetHashFP)BLI_ghashutil_uinthash_v4)
#define         BLI_ghashutil_uinthash_v4_p \
   ((GSetHashFP)BLI_ghashutil_uinthash_v4)
unsigned int    BLI_ghashutil_uinthash_v4_murmur(const unsigned int key[4]);
#define         BLI_ghashutil_inthash_v4_murmur(key) ( \
                CHECK_TYPE_ANY(key, int *, const int *), \
                BLI_ghashutil_uinthash_v4_murmur((const unsigned int *)key))
#define         BLI_ghashutil_inthash_v4_p_murmur \
   ((GSetHashFP)BLI_ghashutil_uinthash_v4_murmur)
#define         BLI_ghashutil_uinthash_v4_p_murmur \
   ((GSetHashFP)BLI_ghashutil_uinthash_v4_murmur)
bool            BLI_ghashutil_uinthash_v4_cmp(const void *a, const void *b);
#define         BLI_ghashutil_inthash_v4_cmp \
                BLI_ghashutil_uinthash_v4_cmp

/** \} */

GHash          *BLI_ghash_ptr_new_ex(const char *info,
                                     const unsigned int nentries_reserve) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT;
GHash          *BLI_ghash_ptr_new(const char *info) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT;
GHash          *BLI_ghash_str_new_ex(const char *info,
                                     const unsigned int nentries_reserve) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT;
GHash          *BLI_ghash_str_new(const char *info) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT;
GHash          *BLI_ghash_int_new_ex(const char *info,
                                     const unsigned int nentries_reserve) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT;
GHash          *BLI_ghash_int_new(const char *info) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT;
GHash          *BLI_ghash_pair_new_ex(const char *info,
                                      const unsigned int nentries_reserve) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT;
GHash          *BLI_ghash_pair_new(const char *info) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT;

typedef struct GHashPair {
	const void *first;
	const void *second;
} GHashPair;

GHashPair      *BLI_ghashutil_pairalloc(const void *first, const void *second);
unsigned int    BLI_ghashutil_pairhash(const void *ptr);
bool            BLI_ghashutil_paircmp(const void *a, const void *b);
void            BLI_ghashutil_pairfree(void *ptr);


/* *** */

typedef struct GSet GSet;

typedef GHashHashFP GSetHashFP;
typedef GHashCmpFP GSetCmpFP;
typedef GHashKeyFreeFP GSetKeyFreeFP;
typedef GHashKeyCopyFP GSetKeyCopyFP;

typedef GHashIterState GSetIterState;

/* so we can cast but compiler sees as different */
typedef struct GSetIterator {
	GHashIterator _ghi
#ifdef __GNUC__
	__attribute__ ((deprecated))
#endif
	;
} GSetIterator;

GSet  *BLI_gset_new_ex(GSetHashFP hashfp, GSetCmpFP cmpfp, const char *info,
                       const unsigned int nentries_reserve) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT;
GSet  *BLI_gset_new(GSetHashFP hashfp, GSetCmpFP cmpfp, const char *info) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT;
GSet  *BLI_gset_copy(GSet *gs, GSetKeyCopyFP keycopyfp) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT;
unsigned int BLI_gset_size(GSet *gs) ATTR_WARN_UNUSED_RESULT;
void   BLI_gset_flag_set(GSet *gs, unsigned int flag);
void   BLI_gset_flag_clear(GSet *gs, unsigned int flag);
void   BLI_gset_free(GSet *gs, GSetKeyFreeFP keyfreefp);
void   BLI_gset_insert(GSet *gh, void *key);
bool   BLI_gset_add(GSet *gs, void *key);
bool   BLI_gset_ensure_p_ex(GSet *gs, const void *key, void ***r_key);
bool   BLI_gset_reinsert(GSet *gh, void *key, GSetKeyFreeFP keyfreefp);
void  *BLI_gset_replace_key(GSet *gs, void *key);
bool   BLI_gset_haskey(GSet *gs, const void *key) ATTR_WARN_UNUSED_RESULT;
bool   BLI_gset_pop(GSet *gs, GSetIterState *state, void **r_key) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL();
bool   BLI_gset_remove(GSet *gs, const void *key, GSetKeyFreeFP keyfreefp);
void   BLI_gset_clear_ex(GSet *gs, GSetKeyFreeFP keyfreefp,
                         const unsigned int nentries_reserve);
void   BLI_gset_clear(GSet *gs, GSetKeyFreeFP keyfreefp);

GSet *BLI_gset_ptr_new_ex(const char *info, const unsigned int nentries_reserve) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT;
GSet *BLI_gset_ptr_new(const char *info);
GSet *BLI_gset_str_new_ex(const char *info, const unsigned int nentries_reserve) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT;
GSet *BLI_gset_str_new(const char *info);
GSet *BLI_gset_pair_new_ex(const char *info, const unsigned int nentries_reserve) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT;
GSet *BLI_gset_pair_new(const char *info) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT;

/* rely on inline api for now */
BLI_INLINE GSetIterator *BLI_gsetIterator_new(GSet *gs) { return (GSetIterator *)BLI_ghashIterator_new((GHash *)gs); }
BLI_INLINE void BLI_gsetIterator_init(GSetIterator *gsi, GSet *gs) { BLI_ghashIterator_init((GHashIterator *)gsi, (GHash *)gs); }
BLI_INLINE void BLI_gsetIterator_free(GSetIterator *gsi) { BLI_ghashIterator_free((GHashIterator *)gsi); }
BLI_INLINE void *BLI_gsetIterator_getKey(GSetIterator *gsi) { return BLI_ghashIterator_getKey((GHashIterator *)gsi); }
BLI_INLINE void BLI_gsetIterator_step(GSetIterator *gsi) { BLI_ghashIterator_step((GHashIterator *)gsi); }
BLI_INLINE bool BLI_gsetIterator_done(GSetIterator *gsi) { return BLI_ghashIterator_done((GHashIterator *)gsi); }

#define GSET_ITER(gs_iter_, gset_) \
	for (BLI_gsetIterator_init(&gs_iter_, gset_); \
	     BLI_gsetIterator_done(&gs_iter_) == false; \
	     BLI_gsetIterator_step(&gs_iter_))

#define GSET_ITER_INDEX(gs_iter_, gset_, i_) \
	for (BLI_gsetIterator_init(&gs_iter_, gset_), i_ = 0; \
	     BLI_gsetIterator_done(&gs_iter_) == false; \
	     BLI_gsetIterator_step(&gs_iter_), i_++)


/* For testing, debugging only */
#ifdef GHASH_INTERNAL_API
int BLI_ghash_buckets_size(GHash *gh);
int BLI_gset_buckets_size(GSet *gs);

double BLI_ghash_calc_quality_ex(
        GHash *gh, double *r_load, double *r_variance,
        double *r_prop_empty_buckets, double *r_prop_overloaded_buckets, int *r_biggest_bucket);
double BLI_gset_calc_quality_ex(
        GSet *gs, double *r_load, double *r_variance,
        double *r_prop_empty_buckets, double *r_prop_overloaded_buckets, int *r_biggest_bucket);
double BLI_ghash_calc_quality(GHash *gh);
double BLI_gset_calc_quality(GSet *gs);
#endif  /* GHASH_INTERNAL_API */

#define GHASH_FOREACH_BEGIN(type, var, what) \
	do { \
		GHashIterator gh_iter##var; \
		GHASH_ITER(gh_iter##var, what) { \
			type var = (type)(BLI_ghashIterator_getValue(&gh_iter##var)); \

#define GHASH_FOREACH_END() \
		} \
	} while(0)

#define GSET_FOREACH_BEGIN(type, var, what) \
	do { \
		GSetIterator gh_iter##var; \
		GSET_ITER(gh_iter##var, what) { \
			type var = (type)(BLI_gsetIterator_getKey(&gh_iter##var));

#define GSET_FOREACH_END() \
		} \
	} while(0)

#ifdef __cplusplus
}
#endif

#endif /* __BLI_GHASH_H__ */