Skip to content

Instantly share code, notes, and snippets.

@tekladis

tekladis/arraymap.c

Last active April 21, 2017 06:17
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save tekladis/71e84cd0afd22d3a80e112a5b86865e6 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save tekladis/71e84cd0afd22d3a80e112a5b86865e6 to your computer and use it in GitHub Desktop.
Download ZIP
Associative array map implementation in C, for small data sets
Raw
arraymap.c
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// Our array entry structure
typedef struct arraymap_entry_t {
char *key;
char *value;
uint_fast32_t key_hash;
uint_fast32_t value_len;
} arraymap_entry_t;
// Our array container
typedef struct arraymap_t {
uint_fast32_t count;
uint_fast32_t insert_index;
uint_fast32_t allocated;
arraymap_entry_t **entries;
} arraymap_t;
// One-at-a-time hashing function
static uint_fast32_t hash(char* key)
{
unsigned char *p = (unsigned char*)key;
uint_fast32_t len = strlen(key);
uint_fast32_t h = 0;
for (uint_fast32_t i = 0; i < len; i++) {
h += p[i];
h += (h << 10);
h ^= (h >> 6);
}
h += (h << 3);
h ^= (h >> 11);
h += (h << 15);
return h;
}
// Pull the index of an existing key, or return -1
static int_fast32_t arraymap_get_index(arraymap_t *map, char *key)
{
uint_fast32_t key_hash = hash(key);
uint_fast32_t cur_count = 0;
for (uint_fast32_t i = 0; i < map->allocated; ++i) {
arraymap_entry_t *entry = map->entries[i];
if (entry != NULL) {
cur_count++;
if (entry->key_hash == key_hash) {
if (strcmp(entry->key, key) == 0) {
return i;
}
}
}
// Short circuit if we've checked all the allocated entries.
if (cur_count == map->count) {
break;
}
}
return -1;
}
arraymap_t *arraymap_new(uint_fast32_t reserve)
{
arraymap_t *map = malloc(sizeof(arraymap_t));
if (map == NULL) {
return NULL;
}
map->allocated = reserve;
map->count = 0;
map->insert_index = 0;
map->entries = malloc(sizeof(arraymap_entry_t*) * reserve);
if (map->entries == NULL) {
free(map);
return NULL;
}
// NULL initialize all the entries.
for (uint_fast32_t i = 0; i < reserve; ++i) {
map->entries[i] = NULL;
}
return map;
}
void arraymap_free(arraymap_t *map)
{
uint_fast32_t cur_count = 0;
for (uint_fast32_t i = 0; i < map->allocated; ++i) {
if (map->entries[i] != NULL) {
free(map->entries[i]->key);
free(map->entries[i]->value);
free(map->entries[i]);
cur_count++;
}
if (cur_count == map->count) {
break;
}
}
free(map->entries);
free(map);
}
int_fast32_t arraymap_insert(arraymap_t *map, char *key, char *value)
{
int_fast32_t found = arraymap_get_index(map, key);
uint_fast32_t key_len = strlen(key);
uint_fast32_t value_len = strlen(value);
// Adjust the value of a pre-existing key if we can.
if (found != -1) {
arraymap_entry_t *entry = map->entries[found];
if (value_len > entry->value_len) {
char *value_tmp = realloc(entry->value, (value_len + 1) * sizeof(char));
if (value_tmp == NULL) {
return -1;
}
entry->value = value_tmp;
entry->value_len = value_len;
memcpy(entry->value, value, value_len + 1);
return found;
}
}
// Automagically grow if an insertion exceeds allocated size.
if (map->insert_index == map->count) {
if (map->count + 1 > map->allocated) {
map->allocated = map->allocated * 2;
map->entries = realloc(map->entries,
map->allocated * sizeof(arraymap_entry_t*));
}
}
// Allocate a new entry
uint_fast32_t index = map->insert_index;
map->entries[index] = malloc(sizeof(arraymap_entry_t));
arraymap_entry_t *entry = map->entries[index];
if (entry == NULL) {
return -1;
}
entry->key = malloc((key_len + 1) * sizeof(char));
if (entry->key == NULL) {
free(entry);
return -1;
}
entry->value = malloc((value_len + 1) * sizeof(char));
if (entry->value == NULL) {
free(entry->key);
free(entry);
return -1;
}
// Copy data to the entry.
entry->key_hash = hash(key);
entry->value_len = value_len;
memcpy(entry->key, key, key_len + 1);
memcpy(entry->value, value, value_len + 1);
// Find the next empty entry if one exists, or go to the end of the array.
if (map->insert_index != map->count) {
while (++map->insert_index < map->allocated) {
if (map->entries[map->insert_index] == NULL) {
break;
}
}
}else {
map->insert_index++;
}
map->count++;
return index;
}
void arraymap_remove(arraymap_t *map, char *key)
{
int_fast32_t found = arraymap_get_index(map, key);
if (found != -1) {
// Move our insertion index backwards if found is at a lower bounds.
if (found < (int_fast32_t)map->insert_index) {
map->insert_index = found;
}
arraymap_entry_t *entry = map->entries[found];
free(entry->key);
free(entry->value);
free(entry);
map->entries[found] = NULL;
map->count--;
}
}
const char* arraymap_get(arraymap_t *map, char *key)
{
int_fast32_t found = arraymap_get_index(map, key);
if (found != -1) {
return map->entries[found]->value;
}
return NULL;
}
uint_fast32_t arraymap_count(arraymap_t *map)
{
return map->count;
}
Raw
arraymap.h
#ifndef __ARRAYMAP_H__
#define __ARRAYMAP_H__
#include <stdint.h>
typedef struct arraymap_t arraymap_t;
/**
* @brief Creates a new arraymap... reserving the amount specified by
* `reserve' as the default container size.
* @param reserve
* @return A pointer to a new arraymap_t struct
*/
arraymap_t *arraymap_new(uint_fast32_t reserve);
/**
* @brief Frees the memory for a previously allocated arraymap struct
* @param map
*/
void arraymap_free(arraymap_t *map);
/**
* @brief Inserts a new key/value pair into the arraymap struct if the
* specified key does not exist. Otherwise, it overwrites the
* previous entry instead.
* @param map
* @param key
* @param value
* @return The index of the newly created key/value pair, or -1 on failure.
*/
int_fast32_t arraymap_insert(arraymap_t *map, char *key, char *value);
/**
* @brief Removes the specified key from the arraymap struct if it exists.
* Does nothing otherwise.
* @param map
* @param key
*/
void arraymap_remove(arraymap_t *map, char *key);
/**
* @brief Finds the specified `key' if it exists in the arraymap and returns
* the value.
* @param map
* @param key
* @return const char* pointer to the value of `key' if it exists. NULL
* otherwise.
*/
const char* arraymap_get(arraymap_t *map, char *key);
/**
* @brief Returns the total number of key/value pairs currently in the
* arraymap.
* @param map
* @return number of key/value pairs.
*/
uint_fast32_t arraymap_count(arraymap_t *map);
#endif//__ARRAYMAP_H__
Raw
arraymap_test.c
#include <stdio.h>
#include <stdlib.h>
#include "arraymap.h"
int main()
{
arraymap_t *map = arraymap_new(10);
// Insert a few things
arraymap_insert(map, "Test 1", "a");
arraymap_insert(map, "Test 2", "b");
arraymap_insert(map, "Test 3", "c");
arraymap_insert(map, "Test 4", "d");
// Remove the first and third element.
arraymap_remove(map, "Test 1");
arraymap_remove(map, "Test 3");
// Insert some more stuff, which should fill the gaps.
arraymap_insert(map, "Test 5", "e");
arraymap_insert(map, "Test 6", "f");
arraymap_insert(map, "Test 7", "g");
// Overwrite an entry
arraymap_insert(map, "Test 2", "peanuts");
// Print some testing information
printf("Total count: %lu\n", arraymap_count(map));
printf("Test 1 %s\n", arraymap_get(map, "Test 1"));
printf("Test 2 %s\n", arraymap_get(map, "Test 2"));
printf("Test 3 %s\n", arraymap_get(map, "Test 3"));
printf("Test 4 %s\n", arraymap_get(map, "Test 4"));
printf("Test 5 %s\n", arraymap_get(map, "Test 5"));
printf("Test 6 %s\n", arraymap_get(map, "Test 6"));
printf("Test 7 %s\n", arraymap_get(map, "Test 7"));
// Test quick inserts
char keybuf[50];
char valbuf[50];
for (int i = 0; i < 1000; ++i) {
snprintf(keybuf, 50, "Test %i", i);
snprintf(valbuf, 50, "%i", rand());
arraymap_insert(map, keybuf, valbuf);
}
uint_fast32_t count = 0;
for (uint_fast32_t i = 0; i < 1000; ++i) {
snprintf(keybuf, 50, "Test %i", i);
if (arraymap_get(map, keybuf)) {
count++;
}
}
printf ("Checked %i entries\n", count);
// Free our array
arraymap_free(map);
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment