diff -r ae5a98f0545c -r 88625853ae74 ucx/map.h --- a/ucx/map.h Sat Dec 01 20:34:55 2012 +0100 +++ b/ucx/map.h Mon Aug 12 14:40:19 2013 +0200 @@ -1,36 +1,65 @@ /* - * + * 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. */ -#ifndef MAP_H -#define MAP_H +/** + * @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 "mempool.h" +#include "allocator.h" #include #ifdef __cplusplus extern "C" { #endif -#define UCX_MAP_FOREACH(elm,iter) \ - for(;ucx_map_iter_next(&iter,(void**)&elm)==0;) +#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; -/* - * param 1: element - * param 2: additional data - * param 3: size of encoded data will be stored here - * returns encoded / decoded string or NULL on failure - */ -typedef void*(*ucx_map_coder)(void*,void*,size_t*); - struct UcxMap { + UcxAllocator *allocator; UcxMapElement **map; size_t size; size_t count; @@ -51,12 +80,34 @@ struct UcxMapIterator { UcxMap *map; UcxMapElement *cur; - int index; + 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. + * + * Note: the contents are not 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); @@ -67,18 +118,81 @@ void* ucx_map_get(UcxMap *map, UcxKey key); void* ucx_map_remove(UcxMap *map, UcxKey key); -#define ucx_map_sstr_put(m, s, d) \ - ucx_map_put(m, ucx_key((void*)s.ptr, s.length), d) -#define ucx_map_cstr_put(m, s, d) \ - ucx_map_put(m, ucx_key((void*)s, 1+strlen(s)), d) -#define ucx_map_sstr_get(m, s) \ - ucx_map_get(m, ucx_key((void*)s.ptr, s.length)) -#define ucx_map_cstr_get(m, s) \ - ucx_map_get(m, ucx_key((void*)s, 1+strlen(s))) -#define ucx_map_sstr_remove(m, s) \ - ucx_map_remove(m, ucx_key((void*)s.ptr, s.length)) -#define ucx_map_cstr_remove(m, s) \ - ucx_map_remove(m, ucx_key((void*)s, 1+strlen(s))) +/** + * 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); @@ -86,21 +200,12 @@ UcxMapIterator ucx_map_iterator(UcxMap *map); -int ucx_map_iter_next(UcxMapIterator *i, void **elm); - -/* use macros for string maps only, values are not encoded */ -#define ucx_map_load(map, f, alloc) ucx_map_load_enc(map, f, alloc, NULL, NULL) -#define ucx_map_store(map, f) ucx_map_store_enc(map, f, NULL, NULL) +int ucx_map_iter_next(UcxMapIterator *i, UcxKey *key, void **elm); -int ucx_map_load_enc(UcxMap *map, FILE *f, UcxAllocator allocator, - ucx_map_coder decoder, void* decdata); -/* encoders shall provide null terminated strings*/ -int ucx_map_store_enc(UcxMap *map, FILE *f, - ucx_map_coder encoder, void* encdata); #ifdef __cplusplus } #endif -#endif /* MAP_H */ +#endif /* UCX_MAP_H */