Mercurial > hg > dav / file revision

/*
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
 *
 * Copyright 2013 Olaf Wintermann. All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *
 *   1. Redistributions of source code must retain the above copyright
 *      notice, this list of conditions and the following disclaimer.
 *
 *   2. Redistributions in binary form must reproduce the above copyright
 *      notice, this list of conditions and the following disclaimer in the
 *      documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 */

/**
 * @file map.h
 * 
 * Hash map implementation.
 * 
 * This implementation uses murmur hash 2 and separate chaining with linked
 * lists.
 * 
 * @author Mike Becker
 * @author Olaf Wintermann
 */

#ifndef UCX_MAP_H
#define	UCX_MAP_H

#include "ucx.h"
#include "string.h"
#include "allocator.h"
#include <stdio.h>

#ifdef	__cplusplus
extern "C" {
#endif

#define UCX_MAP_FOREACH(key,elm,iter) \
        for(UcxKey key;ucx_map_iter_next(&iter,&key, (void**)&elm)==0;)

typedef struct UcxMap          UcxMap;
typedef struct UcxKey          UcxKey;
typedef struct UcxMapElement   UcxMapElement;
typedef struct UcxMapIterator  UcxMapIterator;

struct UcxMap {
    UcxAllocator  *allocator;
    UcxMapElement **map;
    size_t        size;
    size_t        count;
};

struct UcxKey {
    void   *data;
    size_t len;
    int    hash;
};

struct UcxMapElement {
    void          *data;
    UcxMapElement *next;
    UcxKey        key;
};

struct UcxMapIterator {
    UcxMap        *map;
    UcxMapElement *cur;
    size_t        index;
};

/**
 * Creates a new hash map with the specified size.
 * @param size the size of the hash map
 * @return a pointer to the new hash map
 */
UcxMap *ucx_map_new(size_t size);

/**
 * Creates a new hash map with the specified size using an UcxAllocator.
 * @param allocator the allocator to use
 * @param size the size of the hash map
 * @return a pointer to the new hash map
 */
UcxMap *ucx_map_new_a(UcxAllocator *allocator, size_t size);

/**
 * Frees a hash map.
 * 
 * <b>Note:</b> the contents are <b>not</b> freed, use an UcxMempool for that
 * purpose.
 * 
 * @param map the map to be freed
 */
void ucx_map_free(UcxMap *map);

/* you cannot clone maps with more than 390 mio entries */
int ucx_map_copy(UcxMap *restrict from, UcxMap *restrict to,
        copy_func fnc, void *data);
UcxMap *ucx_map_clone(UcxMap *map, copy_func fnc, void *data);
int ucx_map_rehash(UcxMap *map);

int ucx_map_put(UcxMap *map, UcxKey key, void *data);
void* ucx_map_get(UcxMap *map, UcxKey key);
void* ucx_map_remove(UcxMap *map, UcxKey key);

/**
 * Shorthand for putting data with a sstr_t key into the map.
 * @param map the map
 * @param key the key
 * @param value the value
 * @see ucx_map_put()
 */
#define ucx_map_sstr_put(map, key, value) \
    ucx_map_put(map, ucx_key(key.ptr, key.length), (void*)value)
/**
 * Shorthand for putting data with a C string key into the map.
 * @param map the map
 * @param key the key
 * @param value the value
 * @see ucx_map_put()
 */
#define ucx_map_cstr_put(map, key, value) \
    ucx_map_put(map, ucx_key((void*)key, strlen(key)), (void*)value)
/**
 * Shorthand for putting data with an integer key into the map.
 * @param map the map
 * @param key the key
 * @param value the value
 * @see ucx_map_put()
 */
#define ucx_map_int_put(map, key, value) \
    ucx_map_put(map, ucx_key((void*)&key, sizeof(key)), (void*)value)


/**
 * Shorthand for getting data from the map with a sstr_t key.
 * @param map the map
 * @param key the key
 * @see ucx_map_get()
 */
#define ucx_map_sstr_get(map, key) \
    ucx_map_get(map, ucx_key(key.ptr, key.length))
/**
 * Shorthand for getting data from the map with a C string key.
 * @see ucx_map_get()
 */
#define ucx_map_cstr_get(map, key) \
    ucx_map_get(map, ucx_key((void*)key, strlen(key)))
/**
 * Shorthand for getting data from the map with an integer key.
 * @param map the map
 * @param key the key
 * @see ucx_map_get()
 */
#define ucx_map_int_get(map, key) \
    ucx_map_get(map, ucx_key((void*)&key, sizeof(int)))
/**
 * Shorthand for removing data from the map with a sstr_t key.
 * @param map the map
 * @param key the key
 * @see ucx_map_remove()
 */
#define ucx_map_sstr_remove(map, key) \
    ucx_map_remove(map, ucx_key(key.ptr, key.length))
/**
 * Shorthand for removing data from the map with a C string key.
 * @param map the map
 * @param key the key
 * @see ucx_map_remove()
 */
#define ucx_map_cstr_remove(map, key) \
    ucx_map_remove(map, ucx_key((void*)key, strlen(key)))
/**
 * Shorthand for removing data from the map with an integer key.
 * @param map the map
 * @param key the key
 * @see ucx_map_remove()
 */
#define ucx_map_int_remove(map, key) \
    ucx_map_remove(map, ucx_key((void*)&key, sizeof(key)))

UcxKey ucx_key(void *data, size_t len);

int ucx_hash(const char *data, size_t len);

UcxMapIterator ucx_map_iterator(UcxMap *map);

int ucx_map_iter_next(UcxMapIterator *i, UcxKey *key, void **elm);


#ifdef	__cplusplus
}
#endif

#endif	/* UCX_MAP_H */