BRL-CAD
Collaboration diagram for Hash Tables:

Files

file  hash.c
 An implementation of hash tables.
 

Data Structures

struct  bu_hash_entry
 
struct  bu_hash_tbl
 
struct  bu_hash_record
 

Macros

#define BU_HASH_ENTRY_NULL   ((struct bu_hash_entry *)0)
 
#define BU_CK_HASH_ENTRY(_ep)   BU_CKMAG(_ep, BU_HASH_ENTRY_MAGIC, "bu_hash_entry")
 
#define BU_HASH_ENTRY_INIT(_h)
 
#define BU_HASH_ENTRY_INIT_ZERO   { BU_HASH_ENTRY_MAGIC, NULL, NULL, 0, NULL }
 
#define BU_HASH_ENTRY_IS_INITIALIZED(_h)   (((struct bu_hash_entry *)(_h) != BU_HASH_ENTRY_NULL) && LIKELY((_h)->magic == BU_HASH_ENTRY_MAGIC))
 
#define BU_HASH_TBL_NULL   ((struct bu_hash_tbl *)0)
 
#define BU_CK_HASH_TBL(_hp)   BU_CKMAG(_hp, BU_HASH_TBL_MAGIC, "bu_hash_tbl")
 
#define BU_HASH_TBL_INIT(_h)
 
#define BU_HASH_TBL_INIT_ZERO   { BU_HASH_TBL_MAGIC, 0, 0, 0, NULL }
 
#define BU_HASH_TBL_IS_INITIALIZED(_h)   (((struct bu_hash_tbl *)(_h) != BU_HASH_TBL_NULL) && LIKELY((_h)->magic == BU_HASH_TBL_MAGIC))
 
#define BU_HASH_RECORD_NULL   ((struct bu_hash_record *)0)
 
#define BU_CK_HASH_RECORD(_rp)   BU_CKMAG(_rp, BU_HASH_RECORD_MAGIC, "bu_hash_record")
 
#define BU_HASH_RECORD_INIT(_h)
 
#define BU_HASH_RECORD_INIT_ZERO   { BU_HASH_RECORD_MAGIC, NULL, 0, NULL }
 
#define BU_HASH_RECORD_IS_INITIALIZED(_h)   (((struct bu_hash_record *)(_h) != BU_HASH_RECORD_NULL) && LIKELY((_h)->magic == BU_HASH_RECORD_MAGIC))
 

Typedefs

typedef struct bu_hash_entry bu_hash_entry_t
 
typedef struct bu_hash_tbl bu_hash_tbl_t
 
typedef struct bu_hash_record bu_hash_record_t
 

Functions

unsigned long bu_hash (const unsigned char *str, int len)
 
struct bu_hash_tblbu_hash_tbl_create (unsigned long tbl_size)
 
struct bu_hash_entrybu_hash_tbl_find (const struct bu_hash_tbl *hsh_tbl, const unsigned char *key, int key_len, struct bu_hash_entry **prev, unsigned long *idx)
 
void bu_set_hash_value (struct bu_hash_entry *hsh_entry, unsigned char *value)
 
unsigned char * bu_get_hash_value (const struct bu_hash_entry *hsh_entry)
 
unsigned char * bu_get_hash_key (const struct bu_hash_entry *hsh_entry)
 
struct bu_hash_entrybu_hash_tbl_add (struct bu_hash_tbl *hsh_tbl, const unsigned char *key, int key_len, int *new_entry)
 
void bu_hash_tbl_print (const struct bu_hash_tbl *hsh_tbl, const char *str)
 
void bu_hash_tbl_free (struct bu_hash_tbl *hsh_tbl)
 
struct bu_hash_entrybu_hash_tbl_first (const struct bu_hash_tbl *hsh_tbl, struct bu_hash_record *rec)
 
struct bu_hash_entrybu_hash_tbl_next (struct bu_hash_record *rec)
 
struct bu_hash_entrybu_hash_tbl_traverse (struct bu_hash_tbl *hsh_tbl, int(*func)(struct bu_hash_entry *, void *), void *func_arg)
 

Detailed Description

Macro Definition Documentation

#define BU_HASH_ENTRY_NULL   ((struct bu_hash_entry *)0)

Definition at line 52 of file hash.h.

#define BU_CK_HASH_ENTRY (   _ep)    BU_CKMAG(_ep, BU_HASH_ENTRY_MAGIC, "bu_hash_entry")

asserts the integrity of a non-head node bu_hash_entry struct.

Definition at line 57 of file hash.h.

Referenced by bu_get_hash_key(), bu_get_hash_value(), bu_hash_tbl_free(), bu_hash_tbl_print(), and bu_set_hash_value().

#define BU_HASH_ENTRY_INIT (   _h)
Value:
{ \
(_h)->key = (_h)->value = NULL; \
(_h)->key_len = 0; \
(_h)->next = NULL; \
}
#define BU_HASH_ENTRY_MAGIC
Definition: magic.h:50
oldeumate l2 magic
Definition: nmg_mod.c:3843

initializes a bu_hash_entry struct without allocating any memory.

Definition at line 62 of file hash.h.

#define BU_HASH_ENTRY_INIT_ZERO   { BU_HASH_ENTRY_MAGIC, NULL, NULL, 0, NULL }

macro suitable for declaration statement initialization of a bu_hash_entry struct. does not allocate memory.

Definition at line 73 of file hash.h.

#define BU_HASH_ENTRY_IS_INITIALIZED (   _h)    (((struct bu_hash_entry *)(_h) != BU_HASH_ENTRY_NULL) && LIKELY((_h)->magic == BU_HASH_ENTRY_MAGIC))

returns truthfully whether a bu_hash_entry has been initialized.

Definition at line 78 of file hash.h.

#define BU_HASH_TBL_NULL   ((struct bu_hash_tbl *)0)

Definition at line 92 of file hash.h.

#define BU_CK_HASH_TBL (   _hp)    BU_CKMAG(_hp, BU_HASH_TBL_MAGIC, "bu_hash_tbl")

asserts the integrity of a non-head node bu_hash_tbl struct.

Definition at line 97 of file hash.h.

Referenced by bu_hash_tbl_add(), bu_hash_tbl_find(), bu_hash_tbl_first(), bu_hash_tbl_free(), bu_hash_tbl_next(), and bu_hash_tbl_print().

#define BU_HASH_TBL_INIT (   _h)
Value:
{ \
(_h)->mask = (_h)->num_lists = (_h)->num_entries = 0; \
(_h)->lists = NULL; \
}
oldeumate l2 magic
Definition: nmg_mod.c:3843
#define BU_HASH_TBL_MAGIC
Definition: magic.h:52

initializes a bu_hash_tbl struct without allocating any memory.

Definition at line 102 of file hash.h.

#define BU_HASH_TBL_INIT_ZERO   { BU_HASH_TBL_MAGIC, 0, 0, 0, NULL }

macro suitable for declaration statement initialization of a bu_hash_tbl struct. does not allocate memory.

Definition at line 112 of file hash.h.

#define BU_HASH_TBL_IS_INITIALIZED (   _h)    (((struct bu_hash_tbl *)(_h) != BU_HASH_TBL_NULL) && LIKELY((_h)->magic == BU_HASH_TBL_MAGIC))

returns truthfully whether a bu_hash_tbl has been initialized.

Definition at line 117 of file hash.h.

#define BU_HASH_RECORD_NULL   ((struct bu_hash_record *)0)

Definition at line 130 of file hash.h.

#define BU_CK_HASH_RECORD (   _rp)    BU_CKMAG(_rp, BU_HASH_RECORD_MAGIC, "bu_hash_record")

asserts the integrity of a non-head node bu_hash_record struct.

Definition at line 135 of file hash.h.

Referenced by bu_hash_tbl_next().

#define BU_HASH_RECORD_INIT (   _h)
Value:
{ \
(_h)->tbl = NULL; \
(_h)->index = 0; \
(_h)->hsh_entry = NULL; \
}
#define BU_HASH_RECORD_MAGIC
Definition: magic.h:51
oldeumate l2 magic
Definition: nmg_mod.c:3843

initializes a bu_hash_record struct without allocating any memory.

Definition at line 140 of file hash.h.

#define BU_HASH_RECORD_INIT_ZERO   { BU_HASH_RECORD_MAGIC, NULL, 0, NULL }

macro suitable for declaration statement initialization of a bu_hash_record struct. does not allocate memory.

Definition at line 151 of file hash.h.

#define BU_HASH_RECORD_IS_INITIALIZED (   _h)    (((struct bu_hash_record *)(_h) != BU_HASH_RECORD_NULL) && LIKELY((_h)->magic == BU_HASH_RECORD_MAGIC))

returns truthfully whether a bu_hash_record has been initialized.

Definition at line 156 of file hash.h.

Typedef Documentation

Definition at line 51 of file hash.h.

typedef struct bu_hash_tbl bu_hash_tbl_t

Definition at line 91 of file hash.h.

Definition at line 129 of file hash.h.

Function Documentation

unsigned long bu_hash ( const unsigned char *  str,
int  len 
)

the hashing function

Definition at line 32 of file hash.c.

Referenced by bu_hash_tbl_find().

struct bu_hash_tbl* bu_hash_tbl_create ( unsigned long  tbl_size)

Create an empty hash table

The input is the number of desired hash bins. This number will be rounded up to the nearest power of two.

Definition at line 48 of file hash.c.

References BU_HASH_TBL_MAGIC, bu_hash_tbl::lists, bu_hash_tbl::magic, bu_hash_tbl::mask, bu_hash_tbl::num_entries, bu_hash_tbl::num_lists, and UNLIKELY.

Referenced by ged_get_object_selections(), ged_init(), to_idle_mode(), and to_open_tcl().

struct bu_hash_entry* bu_hash_tbl_find ( const struct bu_hash_tbl hsh_tbl,
const unsigned char *  key,
int  key_len,
struct bu_hash_entry **  prev,
unsigned long *  idx 
)

Find the hash table entry corresponding to the provided key

Parameters
[in]hsh_tbl- The hash table to look in
[in]key- the key to look for
[in]key_len- the length of the key in bytes

Output:

Parameters
[out]prev- the previous hash table entry (non-null for entries that not the first in hash bin)
[out]idx- the index of the hash bin for this key
Returns
the hash table entry corresponding to the provided key, or NULL if not found.

Definition at line 95 of file hash.c.

References BU_CK_HASH_TBL, bu_hash(), bu_hash_entry::key, bu_hash_entry::key_len, bu_hash_tbl::lists, bu_hash_tbl::mask, bu_hash_entry::next, and bu_hash_tbl::num_lists.

Referenced by bu_hash_tbl_add().

Here is the call graph for this function:

void bu_set_hash_value ( struct bu_hash_entry hsh_entry,
unsigned char *  value 
)

Set the value for a hash table entry

Note that this is just a pointer copy, the hash table does not maintain its own copy of this value.

Definition at line 160 of file hash.c.

References BU_CK_HASH_ENTRY, and bu_hash_entry::value.

Referenced by ged_get_object_selections(), ged_get_selection_set(), and to_mouse_otranslate().

unsigned char* bu_get_hash_value ( const struct bu_hash_entry hsh_entry)

get the value pointer stored for the specified hash table entry

Definition at line 170 of file hash.c.

References BU_CK_HASH_ENTRY, and bu_hash_entry::value.

Referenced by free_path_edit_params_entry(), ged_get_object_selections(), ged_get_selection_set(), go_draw_solid(), redraw_edited_path(), and to_mouse_otranslate().

unsigned char* bu_get_hash_key ( const struct bu_hash_entry hsh_entry)

get the key pointer stored for the specified hash table entry

Definition at line 179 of file hash.c.

References BU_CK_HASH_ENTRY, and bu_hash_entry::key.

Referenced by key_matches_path(), and redraw_edited_path().

struct bu_hash_entry* bu_hash_tbl_add ( struct bu_hash_tbl hsh_tbl,
const unsigned char *  key,
int  key_len,
int *  new_entry 
)

Add an new entry to a hash table

Parameters
[in]hsh_tbl- the hash table to accept the new entry
[in]key- the key (any byte string)
[in]key_len- the number of bytes in the key
[out]new_entry- a flag, non-zero indicates that a new entry was created. zero indicates that an entry already exists with the specified key and key length
Returns
a hash table entry. If "new" is non-zero, a new, empty entry is returned. if "new" is zero, the returned entry is the one matching the specified key and key_len.

Definition at line 188 of file hash.c.

References BU_CK_HASH_TBL, BU_HASH_ENTRY_MAGIC, bu_hash_tbl_find(), bu_hash_entry::key, bu_hash_entry::key_len, bu_hash_tbl::lists, bu_hash_entry::magic, bu_hash_entry::next, bu_hash_tbl::num_entries, and bu_hash_entry::value.

Referenced by ged_get_object_selections(), ged_get_selection_set(), and to_mouse_otranslate().

Here is the call graph for this function:

void bu_hash_tbl_print ( const struct bu_hash_tbl hsh_tbl,
const char *  str 
)

Print the specified hash table to stderr.

(Note that the keys and values are printed as pointers)

Definition at line 240 of file hash.c.

References BU_CK_HASH_ENTRY, BU_CK_HASH_TBL, bu_hash_entry::key, bu_hash_tbl::lists, bu_hash_entry::next, bu_hash_tbl::num_entries, bu_hash_tbl::num_lists, and bu_hash_entry::value.

void bu_hash_tbl_free ( struct bu_hash_tbl hsh_tbl)

Free all the memory associated with the specified hash table.

Note that the keys are freed (they are copies), but the "values" are not freed. (The values are merely pointers)

Definition at line 263 of file hash.c.

References BU_CK_HASH_ENTRY, BU_CK_HASH_TBL, bu_hash_entry::key, bu_hash_tbl::lists, bu_hash_entry::next, and bu_hash_tbl::num_lists.

Referenced by ged_free(), to_deleteProc(), and to_idle_mode().

struct bu_hash_entry* bu_hash_tbl_first ( const struct bu_hash_tbl hsh_tbl,
struct bu_hash_record rec 
)

get the "first" entry in a hash table

Parameters
[in]hsh_tbl- the hash table of interest
[in]rec- an empty "bu_hash_record" structure for use by this routine and "bu_hash_tbl_next"
Returns
the first non-null entry in the hash table, or NULL if there are no entries (Note that the order of entries is not likely to have any significance)

Definition at line 296 of file hash.c.

References BU_CK_HASH_TBL, BU_HASH_RECORD_MAGIC, bu_hash_record::hsh_entry, bu_hash_record::index, bu_hash_tbl::lists, bu_hash_record::magic, bu_hash_tbl::num_entries, bu_hash_tbl::num_lists, and bu_hash_record::tbl.

Referenced by bu_hash_tbl_traverse().

struct bu_hash_entry* bu_hash_tbl_next ( struct bu_hash_record rec)

get the "next" entry in a hash table

input: rec - the "bu_hash_record" structure that was passed to "bu_hash_tbl_first"

return: the "next" non-null hash entry in this hash table

Definition at line 327 of file hash.c.

References BU_CK_HASH_RECORD, BU_CK_HASH_TBL, bu_hash_record::hsh_entry, bu_hash_record::index, bu_hash_tbl::lists, bu_hash_entry::next, bu_hash_tbl::num_lists, and bu_hash_record::tbl.

Referenced by bu_hash_tbl_traverse().

struct bu_hash_entry* bu_hash_tbl_traverse ( struct bu_hash_tbl hsh_tbl,
int(*)(struct bu_hash_entry *, void *)  func,
void *  func_arg 
)

Pass each table entry to a supplied function, along with an additional argument (which may be NULL).

Returns when func returns !0 or every entry has been visited.

Example, freeing all memory associated with a table whose values are dynamically allocated ints:

1 static int
2 free_entry(struct bu_hash_entry *entry, void *UNUSED(arg))
3 {
4  bu_free(bu_get_hash_value(entry), "table value");
5  return 0;
6 }
7 
8 bu_hash_table_traverse(table, free_entry, NULL);
9 bu_hash_table_free(table);
Returns
If func returns !0 for an entry, that entry is returned. Otherwise NULL is returned.

Definition at line 358 of file hash.c.

References bu_hash_tbl_first(), and bu_hash_tbl_next().

Referenced by ged_free(), go_draw_solid(), to_deleteProc(), and to_idle_mode().

Here is the call graph for this function: