A 2d Hash map

hash_map2d.c

#include "hash_map2d.h"

#include <stdlib.h>

static unsigned hash_map2d_hash(int x, int y) {
    unsigned h = 65521u*x + 101u*y;
    return h;
}

static hash_map2d_entry* hash_map2d_alloc(int capacity) {
    hash_map2d_entry *data = malloc(capacity*sizeof(struct hash_map2d_t));
    if(data != NULL) {
        for(int i = 0;i<capacity;++i) {
            data[i].x = 0;
            data[i].y = 0;
            data[i].value = -2;
        }
    }
    return data;
}

hash_map2d hash_map2d_create_n(int capacity) {
    hash_map2d map = malloc(sizeof(struct hash_map2d_t));
    if(map == NULL) {
        return NULL;
    }
    map->capacity = capacity;
    map->size = 0;
    map->refcount = 1;
    map->data = hash_map2d_alloc(map->capacity);
    if(map->data == NULL) {
        free(map);
        return NULL;
    }
    return map;
}

hash_map2d hash_map2d_create() {
    return hash_map2d_create_n(16);
}

int hash_map2d_size(hash_map2d map) {
    return map->size;
}

int hash_map2d_capacity(hash_map2d map) {
    return map->capacity;
}

hash_map2d_iterator hash_map2d_get_iterator(hash_map2d map) {
    hash_map2d_iterator iter;
    iter.map = map;
    iter.index = -1;
    return iter;
}

int hash_map2d_iterator_next(hash_map2d_iterator *iter, hash_map2d_entry *result) {
    int index = iter->index+1;
    int capacity = iter->map->capacity;
    while(iter->map->data[index].value<0 && index<capacity) ++index;
    iter->index = index;
    if(index<capacity) {
        *result = iter->map->data[index];
        return 1;
    }
    return 0;
}

static int hash_map2d_find(hash_map2d_entry *data, int capacity, int x, int y, int k) {
    unsigned h = hash_map2d_hash(x, y);
    for(int i = 0;i<capacity;++i) {
        unsigned idx = (h+i)%capacity;
        if(data[idx].value < k || (data[idx].x == x && data[idx].y == y)) {
            return idx;
        }
    }
    return -1;
}

static int hash_map2d_set_algo(int x, int y, int data, hash_map2d_entry *arr, int capacity) {
    int idx = hash_map2d_find(arr, capacity, x, y, 0);
    int odata = arr[idx].value;
    arr[idx].x = x;
    arr[idx].y = y;
    if(odata<0) {
        if(data<0) {
            return 0;
        } else {
            arr[idx].value = data;
            return 1;
        }
    } else {
        if(data<0) {
            arr[idx].value = -1;
            return -1;
        } else {
            arr[idx].value = data;
            return 0;
        }
    }
}

static int hash_map2d_resize(hash_map2d map, int capacity) {
    hash_map2d_entry *data = hash_map2d_alloc(capacity);
    if(data == NULL) {
        return 0;
    }
    for(int i = 0;i<map->capacity;++i) {
        if(map->data[i].value >= 0) {
            hash_map2d_set_algo(map->data[i].x, map->data[i].y, map->data[i].value, data, capacity);
        }
    }
    free(map->data);
    map->capacity = capacity;
    map->data = data;
    return 1;
}

int hash_map2d_set(hash_map2d map, int x, int y, int value) {
    if(2*map->capacity < 3*map->size) {
        if(!hash_map2d_resize(map, 3*map->capacity/2)) {
            return 0;
        }
    }
    map->size += hash_map2d_set_algo(x, y, value, map->data, map->capacity);
    return 1;
}

int hash_map2d_get(hash_map2d map, int x, int y) {    
    unsigned idx = hash_map2d_find(map->data, map->capacity, x, y, -1);
    if(map->data[idx].value < 0) {
        return -1;
    } else {
        return map->data[idx].value;
    }
}

void hash_map2d_retain(hash_map2d map) {
    ++map->refcount;
}

void hash_map2d_free(hash_map2d map) {
    if(map != NULL && --map->refcount==0) {
        free(map->data);
        free(map);
    }
}

hash_map2d.h

#ifndef HASH_MAP2D_H
#define HASH_MAP2D_H

typedef struct hash_map2d_entry_t {
    int x, y;
    int value;
} hash_map2d_entry;

typedef struct hash_map2d_t {
    int capacity, size, refcount;
    hash_map2d_entry *data;
}* hash_map2d;

typedef struct hash_map2d_iterator_t {
    hash_map2d map;
    int index;
} hash_map2d_iterator;

// create hash map
hash_map2d hash_map2d_create();

// create hash map with capacity elements preallocated
hash_map2d hash_map2d_create_n(int capacity);

// get size
int hash_map2d_size(hash_map2d map);

// get capacity
int hash_map2d_capacity(hash_map2d map);

// create iterator
hash_map2d_iterator hash_map2d_get_iterator(hash_map2d map);

// get next element of iteration. returns 1 on success or 0 if there is no next element
int hash_map2d_iterator_next(hash_map2d_iterator *iter, hash_map2d_entry *result);

// set value (setting to value<0 deletes the element)
int hash_map2d_set(hash_map2d map, int x, int y, int value);

// get value (returns<0 if element doesn't exist)
int hash_map2d_get(hash_map2d map, int x, int y);

// increase reference count
void hash_map2d_retain(hash_map2d map);

// decrease reference count and free if count == 0
void hash_map2d_free(hash_map2d map);

#endif