Mercurial > hg > ucx / 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 */