00001 /* Part of the culibs project, <http://www.eideticdew.org/culibs/>. 00002 * Copyright (C) 2002--2009 Petter Urkedal <urkedal@nbi.dk> 00003 * 00004 * This program is free software: you can redistribute it and/or modify 00005 * it under the terms of the GNU General Public License as published by 00006 * the Free Software Foundation, either version 3 of the License, or 00007 * (at your option) any later version. 00008 * 00009 * This program is distributed in the hope that it will be useful, 00010 * but WITHOUT ANY WARRANTY; without even the implied warranty of 00011 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00012 * GNU General Public License for more details. 00013 * 00014 * You should have received a copy of the GNU General Public License 00015 * along with this program. If not, see <http://www.gnu.org/licenses/>. 00016 */ 00017 00018 #ifndef CUCON_UMAP_H 00019 #define CUCON_UMAP_H 00020 00021 #include <stdlib.h> 00022 #include <stdio.h> 00023 #include <cucon/fwd.h> 00024 #include <cu/memory.h> 00025 #include <cu/clos.h> 00026 00027 CU_BEGIN_DECLARATIONS 00028 /** \defgroup cucon_umap_h cucon/umap.h: Integer-Keyed Hash Map 00029 ** @{ \ingroup cucon_maps_and_sets_mod 00030 ** 00031 ** This header implements hash maps with \c uintptr_t keys and arbitrary value 00032 ** slots. The slots are stored on the nodes for maximum efficiency. You can 00033 ** still store and access arbitrary values using the \c *_mem functions, 00034 ** whereas some specialised functions are provided for pointers and integers. 00035 ** 00036 ** \see cucon_uset_h 00037 ** \see cucon_pmap_h */ 00038 00039 typedef struct cucon_umap_node *cucon_umap_node_t; 00040 00041 /** An integer-keyed map with variable-sized inline value slots. */ 00042 struct cucon_umap 00043 { 00044 size_t size; /* the number of elements in the map. */ 00045 size_t mask; /* = capacity - 1 */ 00046 cucon_umap_node_t *arr; 00047 }; 00048 00049 struct cucon_umap_node 00050 { 00051 cu_uintptr_t key; 00052 struct cucon_umap_node *next; 00053 /* variable size data */ 00054 }; 00055 00056 /* This is used in sources produced by cuex_otcomp. */ 00057 #define CUCON_UMAP_NODE_INIT(key) { key } 00058 00059 CU_SINLINE cu_uintptr_t cucon_umap_node_key(cucon_umap_node_t node) 00060 { return node->key; } 00061 00062 typedef struct 00063 { 00064 struct cucon_umap_node **node_head; 00065 struct cucon_umap_node *node; 00066 } cucon_umap_it_t; 00067 00068 /** Construct \a map as an empty property map. */ 00069 void cucon_umap_init(cucon_umap_t map); 00070 00071 /** Return an empty property map. */ 00072 cucon_umap_t cucon_umap_new(void); 00073 00074 /** Return an empty property map with <tt>void *</tt> keys. */ 00075 00076 /** Construct \a dst as a copy of \a src but dropping all value slots. */ 00077 void cucon_umap_init_copy_void(cucon_umap_t dst, cucon_umap_t src); 00078 00079 /** Return a copy of \a src after dropping all value slots. */ 00080 cucon_umap_t cucon_umap_new_copy_void(cucon_umap_t src); 00081 00082 /** Construct \a dst as a copy of \a src assuming slots are \a slot_size bytes 00083 ** which can be copied with memcpy. */ 00084 void cucon_umap_init_copy_mem(cucon_umap_t dst, cucon_umap_t src, 00085 size_t slot_size); 00086 00087 /** Return a copy of \a src assuming slots are \a slot_size bytes which can be 00088 ** copied with memcpy. */ 00089 cucon_umap_t cucon_umap_new_copy_mem(cucon_umap_t src, size_t slot_size); 00090 00091 /** Copy \a src to \a dst, assuming all slots have the same size, where \a 00092 ** value_init_copy copies the value at \a src_slot to \a dst_slot. */ 00093 void cucon_umap_init_copy_mem_ctor( 00094 cucon_umap_t dst, cucon_umap_t src, size_t slot_size, 00095 cu_clop(value_init_copy, void, void *dst_slot, void *src_slot, 00096 uintptr_t key)); 00097 00098 /** Copy \a src to \a dst where \a src may have variable slot size. \a 00099 ** node_alloc_copy shall call \a cucon_umap_alloc to allocate some \e node, 00100 ** and construct a copy of \a src_slot at the location given by \c 00101 ** cucon_umap_node_get_mem(node). */ 00102 void cucon_umap_init_copy_node( 00103 cucon_umap_t dst, cucon_umap_t src, 00104 cu_clop(node_alloc_copy, cucon_umap_node_t, void *src_slot, uintptr_t key)); 00105 #define cucon_umap_node_alloc(slot_size) \ 00106 cu_galloc(CU_ALIGNED_SIZEOF(struct cucon_umap_node) + slot_size) 00107 #define cucon_umap_node_get_mem(node) \ 00108 CU_ALIGNED_MARG_END(cucon_umap_node_t, node) 00109 00110 /** Swap the contents of \a map0 with \a map1. */ 00111 void cucon_umap_swap(cucon_umap_t map0, cucon_umap_t map1); 00112 00113 /** Insert \a node, which must be prepared with a key, into \a map. */ 00114 cu_bool_t cucon_umap_insert_init_node(cucon_umap_t map, cucon_umap_node_t node); 00115 00116 /** If \a key is not in \a map, allocates a node of size \a node_size, 00117 ** initialises it the key \a key, inserts it, assigns it to \c *\a node_out, 00118 ** and return true. Otherwise, returns false. This works if the full node 00119 ** inherits \c cucon_umap_node <i>at the top</i> of the struct. */ 00120 cu_bool_t cucon_umap_insert_new_node(cucon_umap_t map, uintptr_t key, 00121 size_t node_size, cu_ptr_ptr_t node_out); 00122 00123 /** If \a key has a mapping in \a map, set \c *\a slot to a pointer to the 00124 ** value and return false, else create a new mapping to \a slot_size bytes of 00125 ** assigned to \c *\a slot and return true. This the generic insert which 00126 ** supports arbitrary value types. */ 00127 cu_bool_t cucon_umap_insert_mem(cucon_umap_t map, uintptr_t key, 00128 size_t slot_size, cu_ptr_ptr_t slot); 00129 00130 /** Insert \a key into \a map unless it exists. Returns true iff the insertion 00131 ** was done. */ 00132 CU_SINLINE cu_bool_t cucon_umap_insert_void(cucon_umap_t map, uintptr_t key) 00133 { return cucon_umap_insert_mem(map, key, 0, NULL); } 00134 00135 /** Insert (\a key, \a ptr) into \a map if it does not exist. Returns true iff 00136 ** the insertion was done. This is a shortcut equivalent to calling \ref 00137 ** cucon_umap_insert_mem and initialising the slot with \a ptr. */ 00138 cu_bool_t cucon_umap_insert_ptr(cucon_umap_t map, uintptr_t key, void *ptr); 00139 00140 /** If \a key is not in \a map, map it to \a val and return true, else return 00141 ** false. If \ref cucon_umap_find_int is used, then \a val should not be \c 00142 ** INT_MIN for the obvious reason. This is a shortcut equivalent to calling 00143 ** \ref cucon_umap_insert_mem and initialising the slot with \a val. */ 00144 cu_bool_t cucon_umap_insert_int(cucon_umap_t map, uintptr_t key, int val); 00145 00146 /** If \a key is not in \a map, insert a node allocated with \a alloc_node 00147 ** mapped from \a key and return true, else return false. In any case <tt>*\a 00148 ** node_out</tt> is set to the node of \a key. This function lets you embed a 00149 ** node in your own data structures. \a alloc_node must use garbage 00150 ** collection. */ 00151 cu_bool_t 00152 cucon_umap_insert_general(cucon_umap_t map, uintptr_t key, 00153 cu_clop0(alloc_node, cucon_umap_node_t), 00154 cucon_umap_node_t *node_out); 00155 00156 /** If \a key is bound in \a map, assume it is bound to a pointer, replace the 00157 ** poiter with \a ptr and return the old pointer, else bind \a key to \a ptr 00158 ** and return NULL. 00159 ** \pre The slot of \a key, if present, must hold a pointer. */ 00160 void *cucon_umap_replace_ptr(cucon_umap_t map, uintptr_t key, void *ptr); 00161 00162 /** If \a key has a mapping in \a map, replace it with \a val and return the 00163 ** old mapping, else insert \a val and return \c INT_MIN. As a special case, 00164 ** if \a val is INT_MIN, erase the mapping of \a key and return the old value 00165 ** or \c INT_MIN of none. 00166 ** \pre The solt of \a key, if present, must hold an \c int. */ 00167 int cucon_umap_replace_int(cucon_umap_t map, uintptr_t key, int val); 00168 00169 /** If \a key has a mapping in \a map, erase it and return true, else return 00170 ** false. To optimise for many deletions, use \c _keep_cap variants and call 00171 ** \ref cucon_umap_update_cap once afterwards. */ 00172 cu_bool_t cucon_umap_erase(cucon_umap_t map, uintptr_t key); 00173 00174 /** If \a key has a mapping in \a map, erase it and return the pointer value 00175 ** stored in the slot, else return \c NULL. 00176 ** \pre The slot of \a key, if present, must hold a pointer. */ 00177 void *cucon_umap_erase_ptr(cucon_umap_t map, uintptr_t key); 00178 00179 /** If \a key has a mapping in \a map, erase it and return the \c int value 00180 ** stored in the slot, else return \c * INT_MIN. 00181 ** \pre The slot of \a key, if present, must hold an \c int. */ 00182 int cucon_umap_erase_int(cucon_umap_t map, uintptr_t key); 00183 00184 /** Same as \ref cucon_umap_erase, except the capacity of \a map is kept. */ 00185 cu_bool_t cucon_umap_erase_keep_cap(cucon_umap_t map, uintptr_t key); 00186 00187 /** Erase any element of \a map and return the erased node. This uses a random 00188 ** number generator to prevent compromising the average case structure of \a 00189 ** map. */ 00190 cucon_umap_node_t cucon_umap_pop_any_node(cucon_umap_t map); 00191 00192 /** As \ref cucon_umap_pop_any_node, but return key instead of node. */ 00193 CU_SINLINE uintptr_t cucon_umap_pop_any_key(cucon_umap_t map) 00194 { 00195 cucon_umap_node_t node = cucon_umap_pop_any_node(map); 00196 return node->key; 00197 } 00198 00199 /** Update capacity after \c _keep_cap calls. */ 00200 void cucon_umap_update_cap(cucon_umap_t map); 00201 00202 /** Returns the internal node of \a key, or \c NULL if none. */ 00203 cucon_umap_node_t cucon_umap_find_node(cucon_umap_t map, uintptr_t key); 00204 00205 /** If \a key has a mapping in \a map, return a pointer to the slot, else 00206 ** return \c NULL. */ 00207 void *cucon_umap_find_mem(cucon_umap_t map, uintptr_t key); 00208 00209 /** If \a key has a mapping in \a map, interpret the slot as a pointer and 00210 ** return it, else return \c NULL. */ 00211 void *cucon_umap_find_ptr(cucon_umap_t map, uintptr_t key); 00212 00213 /** If \a key is in \a map, return its mapping, else return \c INT_MIN. 00214 ** \pre The slot of \a key, if present, must hold an integer. */ 00215 int cucon_umap_find_int(cucon_umap_t map, uintptr_t key); 00216 00217 /** True iff \a map contains \a key, ignoring the slot. */ 00218 CU_SINLINE cu_bool_t cucon_umap_find_void(cucon_umap_t map, uintptr_t key) 00219 { return cucon_umap_find_node(map, key) != NULL; } 00220 00221 /** Call \a cb on each key-value pair in \a map. */ 00222 void cucon_umap_iter_mem(cucon_umap_t map, 00223 cu_clop(cb, void, uintptr_t key, void *value)); 00224 /* TODO. cucon_umap_iter_ptr */ 00225 00226 cu_bool_t cucon_umap_conj_general(cucon_umap_t map, size_t node_offset, 00227 cu_clop(cb, cu_bool_t, uintptr_t, void *)); 00228 00229 /** Sequentially conjunct \a cb over (key, value) pairs in \a map. */ 00230 cu_bool_t cucon_umap_conj_mem(cucon_umap_t map, 00231 cu_clop(cb, cu_bool_t, uintptr_t, void *)); 00232 /* TODO. cucon_umap_conj_ptr */ 00233 00234 /** Call \a cb on each key in \a map. */ 00235 void cucon_umap_iter_keys(cucon_umap_t map, cu_clop(cb, void, uintptr_t)); 00236 00237 /** Call \a cb on each key of \a map in increasing order. */ 00238 void cucon_umap_iter_increasing_keys(cucon_umap_t map, 00239 cu_clop(cb, void, uintptr_t)); 00240 00241 /** Perform a sequantial conjunction of \a cb over keys in \a map. */ 00242 cu_bool_t cucon_umap_conj_keys(cucon_umap_t map, 00243 cu_clop(cb, cu_bool_t, uintptr_t)); 00244 00245 /** Sequential conjunction of \a cb over nodes in \a map. */ 00246 cu_bool_t cucon_umap_conj_node(cucon_umap_t map, 00247 cu_clop(cb, cu_bool_t, cucon_umap_node_t node)); 00248 00249 /** Move all pairs of \a map0 with keys not in \a map1 to \a map1. This 00250 ** effectively assigns \a map0 ∩ \a map1 to \a map0 and \a map0 ∪ \a map1 to 00251 ** \a map1, where only keys are considered for the set operation tests. */ 00252 void cucon_umap_assign_isecn_union(cucon_umap_t map0, cucon_umap_t map1); 00253 00254 /** For each element in \a src0 ∩ \a src1, move one pair to \a dst and delete 00255 ** the other. It is unspecified which of the values from the sources are 00256 ** moved. If \a dst already contains the key, the elemets of both sources are 00257 ** simply discarded. */ 00258 void cucon_umap_move_isecn(cucon_umap_t dst, 00259 cucon_umap_t src0, cucon_umap_t src1); 00260 00261 /** Assign to \a dst the intersection \a dst ∩ \a src, keeping the slots. */ 00262 void cucon_umap_assign_isecn(cucon_umap_t dst, cucon_umap_t src); 00263 00264 /** Assign to \a dst the union of \a dst and \a src, with void slots for 00265 ** duplicated nodes. */ 00266 void cucon_umap_assign_union_void(cucon_umap_t dst, cucon_umap_t src); 00267 00268 /** For profiling use. */ 00269 void cucon_umap_dump_stats(cucon_umap_t map, FILE *out); 00270 00271 /** Return the number of elements in \a map. */ 00272 CU_SINLINE size_t cucon_umap_size(cucon_umap_t map) { return map->size; } 00273 00274 /** True iff \a map is empty. */ 00275 CU_SINLINE cu_bool_t cucon_umap_is_empty(cucon_umap_t map) {return!map->size;} 00276 00277 /** True iff \a map0 and \a map1 contains the same sets of keys. */ 00278 cu_bool_t cucon_umap_eq_keys(cucon_umap_t map0, cucon_umap_t map1); 00279 00280 /** True iff \a map0 and \a map1 are equal, assuming slot size is \a slot_size 00281 ** bytes and trivially comparable. */ 00282 cu_bool_t cucon_umap_eq_mem(cucon_umap_t map0, cucon_umap_t map1, 00283 size_t slot_size); 00284 00285 /** True iff \a map0 and \a map1 are equal, assuming slots are pointers with 00286 ** pointer equality. */ 00287 CU_SINLINE cu_bool_t cucon_umap_eq_ptr(cucon_umap_t map0, cucon_umap_t map1) 00288 { return cucon_umap_eq_mem(map0, map1, sizeof(void *)); } 00289 00290 /** Returns a hash of the keys in \a map. */ 00291 cu_hash_t cucon_umap_hash_keys(cucon_umap_t map); 00292 00293 /** Returns a hash of the keys and slots of \a map, assuming slots are \a 00294 ** slot_size bytes long. */ 00295 cu_hash_t cucon_umap_hash_mem(cucon_umap_t map, size_t slot_size); 00296 00297 /** Returns a hash of the keys and slots of \a map, assuming the slots are 00298 ** pointers. */ 00299 CU_SINLINE cu_hash_t cucon_umap_hash_ptr(cucon_umap_t map) 00300 { return cucon_umap_hash_mem(map, sizeof(void *)); } 00301 00302 /** Prints the keys of \a map to \a out in set notation. */ 00303 void cucon_umap_print_keys(cucon_umap_t map, FILE *out); 00304 00305 /* A range over entries in \a map. \ref cucon_umap_end_eq is faster than 00306 * comparing with the result of \ref cucon_umap_end, even if the result of 00307 * \ref cucon_umap_end is stored. */ 00308 cucon_umap_it_t cucon_umap_begin(cucon_umap_t map); 00309 cucon_umap_it_t cucon_umap_end(cucon_umap_t map); 00310 00311 CU_SINLINE cu_bool_t 00312 cucon_umap_end_eq(cucon_umap_t map, cucon_umap_it_t it) 00313 { 00314 return it.node == (void *)-1; 00315 } 00316 00317 #define cucon_umap_it_eq(it0, it1) ((it0.node) == (it1.node)) 00318 00319 cucon_umap_it_t cucon_umap_it_next(cucon_umap_it_t it); 00320 00321 /* Return the key part at 'it'. */ 00322 #define cucon_umap_it_key(it) ((it).node->key) 00323 00324 /* Return the value part at 'it'. */ 00325 #define cucon_umap_it_value_mem(it) ((void*)CU_ALIGNED_PTR_END((it).node)) 00326 #define cucon_umap_it_value_ptr(it) (*(void**)CU_ALIGNED_PTR_END((it).node)) 00327 00328 /*!\deprecated Use \ref cucon_umap_init. */ 00329 #define cucon_umap_cct cucon_umap_init 00330 /*!\deprecated Use \ref cucon_umap_init_copy_void. */ 00331 #define cucon_umap_cct_copy_void cucon_umap_init_copy_void 00332 /*!\deprecated Use \ref cucon_umap_init_copy_mem. */ 00333 #define cucon_umap_cct_copy_mem cucon_umap_init_copy_mem 00334 /*!\deprecated Use \ref cucon_umap_init_copy_mem_ctor. */ 00335 #define cucon_umap_cct_copy_mem_ctor cucon_umap_init_copy_mem_ctor 00336 /*!\deprecated Use \ref cucon_umap_init_copy_node. */ 00337 #define cucon_umap_cct_copy_node cucon_umap_init_copy_node 00338 00339 /** @} */ 00340 CU_END_DECLARATIONS 00341 00342 #endif