HMap

Overview

The HMap module provides a flexible hash-map implementation featuring:
  • hash bucket chaining or linear probing operating modes;
  • pointer, string or opaque data types for both keys and values;
  • optional cache-style usage by specifying discard policies (FIFO, LRU, LFU and CUSTOM);
  • choice between user or hmap memory ownership;
  • custom hash function, comparison function and object free functions.
Simplified Interface
Developers new to hmap or those wanting a plain and simple { string -> object } hashmap implementation are strongly recommended to use the new hmap easy interface. It is more user-friendly than the standard version and still allows choice between operating modes, policies and other options applied to hmap values.
The following examples illustrates the basic usage of the hmap_easy interface:
          u_hmap_opts_t *opts = NULL;
          u_hmap_t *hmap = NULL;

          dbg_err_if (u_hmap_opts_new(&opts));
          dbg_err_if (u_hmap_opts_set_val_type(opts,
                          U_HMAP_OPTS_DATATYPE_STRING));
          dbg_err_if (u_hmap_easy_new(opts, &hmap));

          dbg_err_if (u_hmap_easy_put(hmap, "jack", (const void *) ":S"));
          dbg_err_if (u_hmap_easy_put(hmap, "jill", (const void *) ":)))"));

          u_con("jack is %s and jill is %s",
              (const char *) u_hmap_easy_get(hmap, "jack"),
              (const char *) u_hmap_easy_get(hmap, "jill"));
      err:
          U_FREEF(hmap, u_hmap_easy_free);
          U_FREEF(opts, u_hmap_opts_free);

As illustrated by the example above, keys are always strings in the easy interface, but there are three types of possibile value types, which can be set by using hmap::u_hmap_opts_set_val_type.

Discard Policies for Caching
HMap also features a useful caching component which allows the user to specify a maximum size after which elements are discarded using one of the following policies:
  • U_HMAP_PCY_NONE: the default policy is to never discard elements;
  • U_HMAP_PCY_FIFO: First In First Out discard policy;
  • U_HMAP_PCY_LRU: Least Recently Used discard policy;
  • U_HMAP_PCY_LFU: Least Frequently Used discard policy;
  • U_HMAP_PCY_CUSTOM: Custom discard policy. For a basic illustration of how each of these work, take a look at the source code of the hmap::u_hmap_pcy_type_t definition. For a sample usage please refer to test/hmap.c.
Advanced Interface
The advanced interface is required if and only if:
  • you want to able to customise the key type to be different than the default C-style string;
  • for some reason you cannot let hmap manage deallocations for you (by calling your custom handler);
  • you don't like the way overwrites are handled in the easy interface (overwritten values are not returned automatically, they must be retrieved by using hmap::u_hmap_easy_get).
The easy interface should do just fine for most applications and it is less error-prone than the advanced interface. So, if you must use the latter, please take special care.

More examples of both easy and advanced API usage can be found in test/hmap.c.

Modules

 hmap_easy: Simplified Interface (recommended)
 hmap: Advanced Interface
 Options
 Policy Settings
 Other Utilities

Enumerations

enum  u_hmap_ret_t
 

hmap error codes


enum  u_hmap_type_t { U_HMAP_TYPE_CHAIN = 0, U_HMAP_TYPE_LINEAR }
 

type of hashmap

More...
enum  u_hmap_options_t { U_HMAP_OPTS_OWNSDATA = 0x1, U_HMAP_OPTS_NO_OVERWRITE = 0x2, U_HMAP_OPTS_HASH_STRONG = 0x4 }
 

hmap options

More...
enum  u_hmap_options_datatype_t { U_HMAP_OPTS_DATATYPE_POINTER = 0, U_HMAP_OPTS_DATATYPE_STRING, U_HMAP_OPTS_DATATYPE_OPAQUE }
 

hmap data type for keys and values (only for U_HMAP_OPTS_OWNSDATA)

More...
enum  u_hmap_pcy_type_t {
  U_HMAP_PCY_NONE = 0, U_HMAP_PCY_FIFO, U_HMAP_PCY_LRU, U_HMAP_PCY_LFU,
  U_HMAP_PCY_CUSTOM
}
 

Policies to discard hmap elements.

More...

Functions

int u_hmap_easy_new (u_hmap_opts_t *opts, u_hmap_t **phmap)
 Create a new hmap.
int u_hmap_easy_put (u_hmap_t *hmap, const char *key, const void *val)
 Insert an object into the hmap.
void * u_hmap_easy_get (u_hmap_t *hmap, const char *key)
 Retrieve a value from the hmap.
int u_hmap_easy_del (u_hmap_t *hmap, const char *key)
 Delete an object from the hmap.
void u_hmap_easy_clear (u_hmap_t *hmap)
 Clear hmap.
void u_hmap_easy_free (u_hmap_t *hmap)
 Deallocate hmap.
int u_hmap_new (u_hmap_opts_t *opts, u_hmap_t **phmap)
 Create a new hmap.
int u_hmap_put (u_hmap_t *hmap, u_hmap_o_t *obj, u_hmap_o_t **old)
 Insert an object into the hmap.
int u_hmap_get (u_hmap_t *hmap, const void *key, u_hmap_o_t **obj)
 Retrieve an object from the hmap.
int u_hmap_del (u_hmap_t *hmap, const void *key, u_hmap_o_t **obj)
 Delete an object from the hmap.
int u_hmap_copy (u_hmap_t *to, u_hmap_t *from)
 Copy hmap.
void u_hmap_clear (u_hmap_t *hmap)
 Clear hmap.
void u_hmap_free (u_hmap_t *hmap)
 Deallocate hmap.
int u_hmap_foreach (u_hmap_t *hmap, int f(const void *val))
 Perform an operation on all objects.
ssize_t u_hmap_count (u_hmap_t *hmap)
 Count the number of elements currently stored in hmap.
const char * u_hmap_strerror (u_hmap_ret_t)
 Get a string representation of an error code.
u_hmap_o_t * u_hmap_o_new (u_hmap_t *hmap, const void *key, const void *val)
 Create a data object (unused for hmap_easy interface).
void * u_hmap_o_get_key (u_hmap_o_t *obj)
 Access the key of the hmap element pointed to by obj.
void * u_hmap_o_get_val (u_hmap_o_t *obj)
 Access the value of the hmap element pointed to by obj.
void u_hmap_o_free (u_hmap_o_t *obj)
 Free a data object (unused for hmap_easy interface).
int u_hmap_opts_new (u_hmap_opts_t **opts)
 Create new hmap options.
void u_hmap_opts_init (u_hmap_opts_t *opts)
 Initialise hmap options.
int u_hmap_opts_set_size (u_hmap_opts_t *opts, int sz)
 Set initial size of hmap's dynamic array.
int u_hmap_opts_set_max (u_hmap_opts_t *opts, int max)
 Set maximum number of elements.
int u_hmap_opts_set_type (u_hmap_opts_t *opts, u_hmap_type_t type)
 Set type of hmap.
int u_hmap_opts_set_policy (u_hmap_opts_t *opts, u_hmap_pcy_type_t policy)
 Set discard policy.
int u_hmap_opts_set_policy_cmp (u_hmap_opts_t *opts, int(*f_pcy_cmp)(void *o1, void *o2))
 Set custom policy comparison function.
int u_hmap_opts_set_val_freefunc (u_hmap_opts_t *opts, void(*f_free)(void *val))
 Set free function for values.
int u_hmap_opts_set_val_type (u_hmap_opts_t *opts, u_hmap_options_datatype_t type)
 Set type of values.
int u_hmap_opts_set_val_sz (u_hmap_opts_t *opts, size_t sz)
 Set size of values (only valid for U_HMAP_OPTS_DATATYPE_OPAQUE key type).
int u_hmap_opts_copy (u_hmap_opts_t *to, u_hmap_opts_t *from)
 Copy options.
void u_hmap_opts_free (u_hmap_opts_t *opts)
 Deallocate hmap options.
int u_hmap_opts_set_option (u_hmap_opts_t *opts, int option)
 Set option in options mask (hmap_easy interface cannot operate on U_HMAP_OPTS_OWNSDATA).
int u_hmap_opts_unset_option (u_hmap_opts_t *opts, int option)
 Unset option in options mask (hmap_easy interface cannot operate on U_HMAP_OPTS_OWNSDATA).
int u_hmap_opts_set_hashfunc (u_hmap_opts_t *opts, size_t(*f_hash)(const void *key, size_t buckets))
 Set a custom hash function.
int u_hmap_opts_set_compfunc (u_hmap_opts_t *opts, int(*f_comp)(const void *k1, const void *k2))
 Set a custom key comparison function.
int u_hmap_opts_set_freefunc (u_hmap_opts_t *opts, void(*f_free)(u_hmap_o_t *obj))
 Set a custom object free function (not available for hmap_easy interface).
int u_hmap_opts_set_strfunc (u_hmap_opts_t *opts, u_string_t *(*f_str)(u_hmap_o_t *obj))
 Set a custom string representation for objects.
int u_hmap_opts_set_key_type (u_hmap_opts_t *opts, u_hmap_options_datatype_t type)
 Set type for keys (not available for hmap_easy interface).
int u_hmap_opts_set_key_sz (u_hmap_opts_t *opts, size_t sz)
 Set size of keys (not available for hmap_easy interface, only valid for U_HMAP_OPTS_DATATYPE_OPAQUE key type).
int u_hmap_opts_set_key_freefunc (u_hmap_opts_t *opts, void(*f_free)(const void *key))
 Set free function for keys (not available for hmap_easy interface).
void u_hmap_dbg (u_hmap_t *hmap)
 Debug Hmap.
void u_hmap_opts_dbg (u_hmap_opts_t *opts)
 Debug options.

Enumeration Type Documentation

enum u_hmap_options_datatype_t
Enumerator:
U_HMAP_OPTS_DATATYPE_POINTER 

pointer to custom data

U_HMAP_OPTS_DATATYPE_STRING 

null-terminated string

U_HMAP_OPTS_DATATYPE_OPAQUE 

user data of given size

Definition at line 46 of file hmap.h.

enum u_hmap_options_t
Enumerator:
U_HMAP_OPTS_OWNSDATA 

hmap owns memory

U_HMAP_OPTS_NO_OVERWRITE 

don't overwrite equal keys

U_HMAP_OPTS_HASH_STRONG 

custom hash function is strong

Definition at line 38 of file hmap.h.

enum u_hmap_pcy_type_t
Enumerator:
U_HMAP_PCY_NONE 

never discard old elements (grow if threshold is exceeded)

U_HMAP_PCY_FIFO 

discard entry inserted longest ago

U_HMAP_PCY_LRU 

discard least recently used (accessed)

U_HMAP_PCY_LFU 

discard least frequently used (accessed)

U_HMAP_PCY_CUSTOM 

user policy via u_hmap_opts_set_policy_cmp()

Definition at line 56 of file hmap.h.

enum u_hmap_type_t
Enumerator:
U_HMAP_TYPE_CHAIN 

separate chaining (default)

U_HMAP_TYPE_LINEAR 

linear probing

Definition at line 29 of file hmap.h.

Function Documentation

void u_hmap_clear ( u_hmap_t *  hmap  ) 

Clears all hmap elements. Objects are freed via free() by default or using the custom deallocation function passed in the hmap options.

Parameters:
hmap hmap object

Definition at line 611 of file srcs/toolbox/hmap.c.

Referenced by u_hmap_easy_clear(), and u_hmap_free().

int u_hmap_copy ( u_hmap_t *  to,
u_hmap_t *  from 
)

Perform a copy of an hmap from to to by rehashing all elements and copying the object pointers to the new locations.

Parameters:
to destination hmap
from source hmap
Return values:
U_HMAP_ERR_NONE on success
U_HMAP_ERR_FAIL on failure

Definition at line 1516 of file srcs/toolbox/hmap.c.

References u_hmap_put().

ssize_t u_hmap_count ( u_hmap_t *  hmap  ) 

Count the number of elements currently stored in the supplied hmap object

Parameters:
hmap hmap object
Returns:
The number of elements currently stored in hmap, or -1 on error

Definition at line 1059 of file srcs/toolbox/hmap.c.

void u_hmap_dbg ( u_hmap_t *  hmap  ) 

Print out information on an hmap.

Parameters:
hmap hmap object

Definition at line 1885 of file srcs/toolbox/hmap.c.

References u_string_append(), u_string_aprintf(), u_string_c(), u_string_cat, u_string_clear(), u_string_create(), u_string_free(), and u_string_len().

int u_hmap_del ( u_hmap_t *  hmap,
const void *  key,
u_hmap_o_t **  obj 
)

Delete object with given key from hmap and return it (if the object is owned by user).

Parameters:
hmap hmap object
key key of object to be deleted
obj deleted object
Return values:
U_HMAP_ERR_NONE on success
U_HMAP_ERR_FAIL on failure

Definition at line 838 of file srcs/toolbox/hmap.c.

References U_HMAP_OPTS_OWNSDATA.

Referenced by u_hmap_easy_del().

void u_hmap_easy_clear ( u_hmap_t *  hmap  ) 

See u_hmap_clear().

Parameters:
hmap hmap object

Definition at line 302 of file srcs/toolbox/hmap.c.

References u_hmap_clear().

int u_hmap_easy_del ( u_hmap_t *  hmap,
const char *  key 
)

Delete object with given key from hmap.

Parameters:
hmap hmap object
key key of object to be deleted
Return values:
U_HMAP_ERR_NONE on success
U_HMAP_ERR_FAIL on failure

Definition at line 398 of file srcs/toolbox/hmap.c.

References u_hmap_del().

void u_hmap_easy_free ( u_hmap_t *  hmap  ) 

Deallocate hmap along with all hmapd objects. Objects are freed by using the function pointer specified with u_hmap_opts_set_val_freefunc() if it is not NULL.

Parameters:
hmap hmap object

Definition at line 318 of file srcs/toolbox/hmap.c.

References u_hmap_free().

Referenced by u_json_free(), u_json_index(), and u_json_unindex().

void* u_hmap_easy_get ( u_hmap_t *  hmap,
const char *  key 
)

Retrieve the value with given key from hmap.

Parameters:
hmap hmap object
key key to be retrieved
Returns:
a pointer to the retrieved value on success, NULL on failure or no match

Definition at line 378 of file srcs/toolbox/hmap.c.

References u_hmap_get().

Referenced by u_json_cache_get().

int u_hmap_easy_new ( u_hmap_opts_t *  opts,
u_hmap_t **  phmap 
)

Create a new hmap object and save its pointer to *hmap. The call may fail on memory allocation problems or if the options are manipulated incorrectly.

Parameters:
opts options to be passed to the hmap
phmap on success contains the hmap options object
Return values:
U_HMAP_ERR_NONE on success
U_HMAP_ERR_FAIL on failure

Definition at line 274 of file srcs/toolbox/hmap.c.

References u_hmap_new(), u_hmap_opts_copy(), and u_hmap_opts_init().

Referenced by u_json_index().

int u_hmap_easy_put ( u_hmap_t *  hmap,
const char *  key,
const void *  val 
)

Insert a key, val pair into hmap.

The size of val copied into the hmap is based on its type set using u_hmap_opts_set_val_type():

  • U_HMAP_OPTS_DATATYPE_POINTER (default): the pointer value will be simply copied
  • U_HMAP_OPTS_DATATYPE_STRING: the null-terminated string value will copied entirely
  • U_HMAP_OPTS_DATATYPE_OPAQUE: the value will be duplicated to the size set with u_hmap_opts_set_val_sz()

Values are not overwritten if a value already exists in the hmap for a given key, unless U_HMAP_OPTS_NO_OVERWRITE is explicitly unset using u_hmap_opts_unset_option().

Parameters:
hmap hmap object
key key to be inserted
val value to be inserted
Return values:
U_HMAP_ERR_NONE on success
U_HMAP_ERR_EXISTS if key already exists
U_HMAP_ERR_FAIL on other failures

Definition at line 353 of file srcs/toolbox/hmap.c.

References u_hmap_o_new(), and u_hmap_put().

int u_hmap_foreach ( u_hmap_t *  hmap,
int   fconst void *val 
)

Execute function f on all objects within hmap. These functions should return U_HMAP_ERR_NONE on success, and take an object as a parameter.

Parameters:
hmap hmap object
f function
Return values:
U_HMAP_ERR_NONE on success
U_HMAP_ERR_FAIL on failure

Definition at line 1793 of file srcs/toolbox/hmap.c.

void u_hmap_free ( u_hmap_t *  hmap  ) 

Deallocate hmap along with all hmapd objects (unless U_HMAP_OPTS_OWNSDATA is set). Objects are freed via free() by default or using the custom deallocation function passed in the hmap options.

Parameters:
hmap hmap object

Definition at line 646 of file srcs/toolbox/hmap.c.

References u_free(), u_hmap_clear(), and u_hmap_opts_free().

Referenced by u_hmap_easy_free().

int u_hmap_get ( u_hmap_t *  hmap,
const void *  key,
u_hmap_o_t **  obj 
)

Retrieve object with given key from hmap. On success the requested object is returned in obj. The object is not removed from the hmap, so ownership of the object is not returned to the user.

Parameters:
hmap hmap object
key key to be retrieved
obj returned object
Return values:
U_HMAP_ERR_NONE on success
U_HMAP_ERR_FAIL on failure

Definition at line 803 of file srcs/toolbox/hmap.c.

Referenced by u_hmap_easy_get().

int u_hmap_new ( u_hmap_opts_t *  opts,
u_hmap_t **  phmap 
)

Create a new hmap object and save its pointer to *hmap. The call may fail on memory allocation problems or if the options are manipulated incorrectly.

Parameters:
opts options to be passed to the hmap (may be NULL)
phmap on success contains the hmap options object
Return values:
U_HMAP_ERR_NONE on success
U_HMAP_ERR_FAIL on failure

Definition at line 551 of file srcs/toolbox/hmap.c.

References u_free(), u_hmap_opts_copy(), U_HMAP_OPTS_DATATYPE_STRING, u_hmap_opts_dbg(), u_hmap_opts_new(), and u_zalloc().

Referenced by u_hmap_easy_new().

void u_hmap_o_free ( u_hmap_o_t *  obj  ) 

Frees a data object (without freeing its content). This function should only be used if U_HMAP_OPTS_OWNSDATA is not set to free objects allocated with u_hmap_o_new(). If U_HMAP_OPTS_OWNSDATA is set, the data is freed automatically by the hashmap by using the default free function or the overridden f_free().

Parameters:
obj hmap object

Definition at line 951 of file srcs/toolbox/hmap.c.

References u_free().

Referenced by u_hmap_o_new().

u_hmap_o_t* u_hmap_o_new ( u_hmap_t *  hmap,
const void *  key,
const void *  val 
)

Creates a new (key, value) tuple to be inserted into a hmap. By default, the user is responsible for allocation and deallocation of these objects and their content. If the option U_HMAP_OPTS_OWNSDATA is set

Parameters:
hmap reference to parent hmap
key pointer to the key
val pointer to the oject
Returns:
pointer to a new u_hmap_o_t

Definition at line 881 of file srcs/toolbox/hmap.c.

References u_hmap_o_free(), U_HMAP_OPTS_DATATYPE_OPAQUE, U_HMAP_OPTS_DATATYPE_POINTER, U_HMAP_OPTS_DATATYPE_STRING, U_HMAP_OPTS_OWNSDATA, u_strdup(), and u_zalloc().

Referenced by u_hmap_easy_put().

int u_hmap_opts_copy ( u_hmap_opts_t *  to,
u_hmap_opts_t *  from 
)

Perform a deep copy of options object from to to.

Parameters:
to destination options
from source options
Return values:
U_HMAP_ERR_NONE on success
U_HMAP_ERR_FAIL on failure

Definition at line 1162 of file srcs/toolbox/hmap.c.

Referenced by u_hmap_easy_new(), and u_hmap_new().

void u_hmap_opts_dbg ( u_hmap_opts_t *  opts  ) 

Print out information on option settings.

Parameters:
opts options object

Definition at line 1181 of file srcs/toolbox/hmap.c.

References U_HMAP_OPTS_NO_OVERWRITE, and U_HMAP_OPTS_OWNSDATA.

Referenced by u_hmap_new().

void u_hmap_opts_free ( u_hmap_opts_t *  opts  ) 

Deallocate hmap options object opts.

Parameters:
opts hmap options

Definition at line 1112 of file srcs/toolbox/hmap.c.

References u_free().

Referenced by u_hmap_free(), and u_json_index().

void u_hmap_opts_init ( u_hmap_opts_t *  opts  ) 

Set allocated hmap options to default values

Parameters:
opts hmap options object

Definition at line 1126 of file srcs/toolbox/hmap.c.

References U_HMAP_OPTS_DATATYPE_POINTER, U_HMAP_OPTS_DATATYPE_STRING, U_HMAP_OPTS_NO_OVERWRITE, U_HMAP_OPTS_OWNSDATA, U_HMAP_PCY_NONE, and U_HMAP_TYPE_CHAIN.

Referenced by u_hmap_easy_new(), and u_hmap_opts_new().

int u_hmap_opts_new ( u_hmap_opts_t **  opts  ) 

Create a new hmap options object and save its pointer to *opts. The fields within the object can be manipulated publicly according to the description in the header file.

Parameters:
opts on success contains the hmap options object
Return values:
U_HMAP_ERR_NONE on success
U_HMAP_ERR_FAIL on failure

Definition at line 1086 of file srcs/toolbox/hmap.c.

References u_hmap_opts_init(), and u_zalloc().

Referenced by u_hmap_new(), and u_json_index().

int u_hmap_opts_set_max ( u_hmap_opts_t *  opts,
int  max 
)

This limit is used only if a discard policy has been set via u_hmap_opts_set_policy(); otherwise the hmap is simply resized.

Definition at line 1222 of file srcs/toolbox/hmap.c.

int u_hmap_opts_set_policy_cmp ( u_hmap_opts_t *  opts,
int(*)(void *o1, void *o2)  f_pcy_cmp 
)

Sets the object comparison function for U_HMAP_PCY_CUSTOM discard policy. The function should return 1 if o1 has higher priority than o2, 0 if it is equal and -1 if the priority is lower.

Definition at line 1461 of file srcs/toolbox/hmap.c.

References U_HMAP_PCY_CUSTOM.

int u_hmap_put ( u_hmap_t *  hmap,
u_hmap_o_t *  obj,
u_hmap_o_t **  old 
)

Insert a (key, val) pair obj into hmap. Such object should be created with u_hmap_o_new(). The user is responsible for allocation of keys and values unless U_HMAP_OPTS_OWNSDATA is set. If a value is overwritten (U_HMAP_OPTS_NO_OVERWRITE must be unset via u_hmap_opts_unset_option()) and data is owned by the user, the old value is returned.

Parameters:
hmap hmap object
obj key to be inserted
old returned old value
Return values:
U_HMAP_ERR_NONE on success
U_HMAP_ERR_EXISTS if key already exists
U_HMAP_ERR_FAIL on other failures

Definition at line 673 of file srcs/toolbox/hmap.c.

References U_HMAP_OPTS_HASH_STRONG, U_HMAP_PCY_NONE, U_HMAP_TYPE_CHAIN, U_HMAP_TYPE_LINEAR, and u_snprintf().

Referenced by u_hmap_copy(), and u_hmap_easy_put().

const char* u_hmap_strerror ( u_hmap_ret_t  rc  ) 

Get a string representation of an error code

Parameters:
rc return code

Definition at line 1490 of file srcs/toolbox/hmap.c.

←Products
© 2005-2012 - KoanLogic S.r.l. - All rights reserved