A RetroSearch Logo

Home - News ( United States | United Kingdom | Italy | Germany ) - Football scores

Search Query:

Showing content from https://github.com/DavidLeeds/hashmap below:

DavidLeeds/hashmap: Templated type-safe hashmap implementation in C using open addressing and linear probing for collision resolution.

Templated type-safe hashmap implementation in C using open addressing and linear probing for collision resolution.

This project came into existence because there are a notable lack of flexible and easy to use data structures available in C. C data structures with efficient, type-safe interfaces are virtually non-existent. Higher level languages have built-in libraries and templated classes, but plenty of embedded projects or higher level libraries are implemented in C. When it is undesireable to depend on a bulky library like Glib or grapple with a restrictive license agreement, this is the library for you.

Declaring a type-specific hashmap

Use the HASHMAP(key_type, value_type) macro to declare a hashmap state struct specific to your needs. Keys and values are always passed in by pointer. Keys are const.

/* Map with string key (const char *) and integer value (int *) */
HASHMAP(char, int) map1;

/* Map with uint64 key (const uint64_t *) and struct value (struct my_value *) */
HASHMAP(uint64_t, struct my_value) map2;

The structure defined by the HASHMAP() macro may be used directly, or named using typedef. For example:

typedef HASHMAP(char, struct my_value) value_map_t;
Initialization and cleanup

Maps must be initialized with a key hash function and a key comparator.

/* Initialize the map structure */
hashmap_init(&map, my_key_hash, my_key_compare);

/* Use the map... */

/* Free resources associated with the map */
hashmap_cleanup(&map);

This library provides some hash functions, so you may not have to write your own:

I recommend using these, unless you have very specific needs.

/* Initialize a map with case-sensitive string keys */
hashmap_init(&map, hashmap_hash_string, strcmp);

Note that memory associated with map keys and values is not managed by the map, so you may need to free this before calling hashmap_cleanup(). Keys are often stored in the same structure as the value, but it is possible to have the map manage key memory allocation internally, by calling hashmap_set_key_alloc_funcs().

struct my_value *val = /* ... */;

/* Add a my_value (fails and returns -EEXIST if the key already exists) */
int result1 = hashmap_put(&map, "KeyABC", val);

/* Add or update a my_value (assigns previous value to old_data if the key already exists) */
struct my_value *old_val;
int result2 = hashmap_insert(&map, "KeyABC", val, &old_val);
/* Access the value with a given key */
struct my_value *val1 = hashmap_get(&map, "KeyABC");

/* Access the key or value with an iterator */
HASHMAP_ITER(map) iter = hashmap_iter_find(&map, "keyABC");
const char *key = hashmap_iter_get_key(&iter);
struct my_value *val2 = hashmap_iter_get_data(&iter);

/* Check if an entry with the given key exists */
bool present = hashmap_contains(&map, "KeyABC");
/* Erase the entry with the given key */
struct my_value *val = hashmap_remove(&map, "KeyABC");

/* Erase the entry with an iterator */
HASHMAP_ITER(map) iter = hashmap_iter_find(&map, "keyABC");
hashmap_iter_remove(&iter);

/* Erase all entries */
hashmap_clear(&map);

/* Erase all entries and reset the hash table heap allocation to its initial size */
hashmap_reset(&map);

Iteration may be accomplished using the "convenience" foreach macros, or by using the iterator interface directly. Generally, the foreach macros are the most intuitive and convenient.

const char *key;
struct my_value *val;

/* Iterate over all map entries and access both keys and values */
hashmap_foreach(key, val, &map) {
    /* Access each entry */
}

/* Iterate over all map entries and access just keys */
hashmap_foreach_key(key, &map) {
    /* Access each entry */
}

/* Iterate over all map entries and access just values */
hashmap_foreach_data(val, &map) {
    /* Access each entry */
}

The above iteration macros are only safe for read-only access. To safely remove the current element during iteration, use the macros with a _safe suffix. These require an additional pointer parameter. For example:

const char *key;
struct my_value *val;
void *pos;

/* Okay */
hashmap_foreach_key_safe(key, &map, pos) {
    hashmap_remove(&map, key);
}

Iteration using the iterator interface.

HASHMAP_ITER(map) it;

for (it = hashmap_iter(&map); hashmap_iter_valid(&it); hashmap_iter_next(&it)) {
    /*
     * Access entry using:
     *   hashmap_iter_get_key()
     *   hashmap_iter_get_data()
     *   hashmap_iter_set_data()
     */
}

Are located in the examples directory in the source tree.

This project uses CMake to orchestrate the build and installallation process.

To build and install on your host system, follow these easy steps:

  1. git clone https://github.com/DavidLeeds/hashmap.git - download the source
  2. mkdir build-hashmap && cd build-hashmap - create a build directory outside the source tree
  3. cmake ../hashmap - run CMake to setup the build
  4. make - compile the code
  5. make test - run the unit tests (if enabled)
  6. sudo make install - OPTIONAL install the library on this system
How to integrate with an existing CMake project

Clone and build this repository:

include(FetchContent)

FetchContent_Declare(
    hashmap
    GIT_REPOSITORY https://github.com/DavidLeeds/hashmap.git
    GIT_SHALLOW ON
)
FetchContent_MakeAvailable(hashmap)

Add HashMap::HashMap as a dependnecy, e.g.:

add_executable(my_app main.c)
target_link_libraries(my_app PRIVATE HashMap::HashMap)
Contibutions and Questions

I welcome all questions and contributions. Feel free to e-mail me, or put up a pull request. The core algorithm is stable, but I'm happy to consider CMake improvements, compiler compatibility fixes, or API additions.

RetroSearch is an open source project built by @garambo | Open a GitHub Issue

Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo

HTML: 3.2 | Encoding: UTF-8 | Version: 0.7.4