--- 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 <stdio.h>
#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.
+ *
+ * <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);
@@ -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 */
