- Timestamp:
- 03/20/15 23:31:05 (9 years ago)
- Location:
- trunk/tommyDS_hashlin
- Files:
-
- 8 edited
Legend:
- Unmodified
- Added
- Removed
-
trunk/tommyDS_hashlin/tommychain.h
r9093 r10636 1 1 /* 2 * Copyright 2010Andrea Mazzoleni. All rights reserved.2 * Copyright (c) 2010, Andrea Mazzoleni. All rights reserved. 3 3 * 4 4 * Redistribution and use in source and binary forms, with or without … … 13 13 * documentation and/or other materials provided with the distribution. 14 14 * 15 * THIS SOFTWARE IS PROVIDED BY ANDREA MAZZOLENI AND CONTRIBUTORS ``AS IS''15 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 16 16 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 17 17 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 18 * ARE DISCLAIMED. IN NO EVENT SHALL ANDREA MAZZOLENIOR CONTRIBUTORS BE18 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE 19 19 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 20 20 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF … … 168 168 * It's used to know which bucket is empty of full. 169 169 */ 170 unsignedcounter;170 tommy_count_t counter; 171 171 tommy_node* node = chain->head; 172 172 tommy_node* tail = chain->tail; 173 unsignedmask;174 unsignedi;173 tommy_count_t mask; 174 tommy_count_t i; 175 175 176 176 counter = 0; … … 211 211 while (mask != 1) { 212 212 mask >>= 1; 213 if (mask & 1) { 214 tommy_chain_merge_degenerated(&bit[i+1], &bit[i], cmp); 215 } else { 216 bit[i+1] = bit[i]; 217 } 213 if (mask & 1) 214 tommy_chain_merge_degenerated(&bit[i + 1], &bit[i], cmp); 215 else 216 bit[i + 1] = bit[i]; 218 217 ++i; 219 218 } -
trunk/tommyDS_hashlin/tommyhash.c
r9737 r10636 1 1 /* 2 * Copyright 2010Andrea Mazzoleni. All rights reserved.2 * Copyright (c) 2010, Andrea Mazzoleni. All rights reserved. 3 3 * 4 4 * Redistribution and use in source and binary forms, with or without … … 13 13 * documentation and/or other materials provided with the distribution. 14 14 * 15 * THIS SOFTWARE IS PROVIDED BY ANDREA MAZZOLENI AND CONTRIBUTORS ``AS IS''15 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 16 16 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 17 17 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 18 * ARE DISCLAIMED. IN NO EVENT SHALL ANDREA MAZZOLENIOR CONTRIBUTORS BE18 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE 19 19 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 20 20 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF … … 36 36 #if defined(__i386__) || defined(_M_IX86) || defined(_X86_) || defined(__x86_64__) || defined(_M_X64) 37 37 /* defines from http://predef.sourceforge.net/ */ 38 return *( tommy_uint32_t*)ptr;38 return *(const tommy_uint32_t*)ptr; 39 39 #else 40 40 const unsigned char* ptr8 = tommy_cast(const unsigned char*, ptr); … … 43 43 } 44 44 45 #define tommy_rot(x, k) \46 (((x) <<(k)) | ((x)>>(32-(k))))45 #define tommy_rot(x, k) \ 46 (((x) << (k)) | ((x) >> (32 - (k)))) 47 47 48 #define tommy_mix(a, b,c) \48 #define tommy_mix(a, b, c) \ 49 49 do { \ 50 50 a -= c; a ^= tommy_rot(c, 4); c += b; \ 51 51 b -= a; b ^= tommy_rot(a, 6); a += c; \ 52 52 c -= b; c ^= tommy_rot(b, 8); b += a; \ 53 a -= c; a ^= tommy_rot(c, 16); c += b; \54 b -= a; b ^= tommy_rot(a, 19); a += c; \53 a -= c; a ^= tommy_rot(c, 16); c += b; \ 54 b -= a; b ^= tommy_rot(a, 19); a += c; \ 55 55 c -= b; c ^= tommy_rot(b, 4); b += a; \ 56 56 } while (0) 57 57 58 #define tommy_final(a, b,c) \58 #define tommy_final(a, b, c) \ 59 59 do { \ 60 c ^= b; c -= tommy_rot(b, 14); \61 a ^= c; a -= tommy_rot(c, 11); \62 b ^= a; b -= tommy_rot(a, 25); \63 c ^= b; c -= tommy_rot(b, 16); \64 a ^= c; a -= tommy_rot(c, 4); \65 b ^= a; b -= tommy_rot(a, 14); \66 c ^= b; c -= tommy_rot(b, 24); \60 c ^= b; c -= tommy_rot(b, 14); \ 61 a ^= c; a -= tommy_rot(c, 11); \ 62 b ^= a; b -= tommy_rot(a, 25); \ 63 c ^= b; c -= tommy_rot(b, 16); \ 64 a ^= c; a -= tommy_rot(c, 4); \ 65 b ^= a; b -= tommy_rot(a, 14); \ 66 c ^= b; c -= tommy_rot(b, 24); \ 67 67 } while (0) 68 68 69 69 tommy_uint32_t tommy_hash_u32(tommy_uint32_t init_val, const void* void_key, tommy_size_t key_len) 70 70 { 71 const unsigned char* key = tommy_cast(const unsigned char*, void_key);71 const unsigned char* key = tommy_cast(const unsigned char*, void_key); 72 72 tommy_uint32_t a, b, c; 73 73 … … 79 79 c += tommy_le_uint32_read(key + 8); 80 80 81 tommy_mix(a, b,c);81 tommy_mix(a, b, c); 82 82 83 83 key_len -= 12; … … 111 111 } 112 112 113 tommy_final(a, b,c);113 tommy_final(a, b, c); 114 114 115 115 return c; … … 118 118 tommy_uint64_t tommy_hash_u64(tommy_uint64_t init_val, const void* void_key, tommy_size_t key_len) 119 119 { 120 const unsigned char* key = tommy_cast(const unsigned char*, void_key);120 const unsigned char* key = tommy_cast(const unsigned char*, void_key); 121 121 tommy_uint32_t a, b, c; 122 122 … … 129 129 c += tommy_le_uint32_read(key + 8); 130 130 131 tommy_mix(a, b,c);131 tommy_mix(a, b, c); 132 132 133 133 key_len -= 12; … … 161 161 } 162 162 163 tommy_final(a, b,c);163 tommy_final(a, b, c); 164 164 165 165 return c + ((tommy_uint64_t)b << 32); -
trunk/tommyDS_hashlin/tommyhash.h
r9093 r10636 1 1 /* 2 * Copyright 2010Andrea Mazzoleni. All rights reserved.2 * Copyright (c) 2010, Andrea Mazzoleni. All rights reserved. 3 3 * 4 4 * Redistribution and use in source and binary forms, with or without … … 13 13 * documentation and/or other materials provided with the distribution. 14 14 * 15 * THIS SOFTWARE IS PROVIDED BY ANDREA MAZZOLENI AND CONTRIBUTORS ``AS IS''15 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 16 16 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 17 17 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 18 * ARE DISCLAIMED. IN NO EVENT SHALL ANDREA MAZZOLENIOR CONTRIBUTORS BE18 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE 19 19 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 20 20 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF … … 25 25 * POSSIBILITY OF SUCH DAMAGE. 26 26 */ 27 27 28 28 /** \file 29 29 * Hash functions for the use with ::tommy_hashtable, ::tommy_hashdyn and ::tommy_hashlin. … … 49 49 * \param init_val Initialization value. 50 50 * Using a different initialization value, you can generate a completely different set of hash values. 51 * Use 0 if not releva lt.51 * Use 0 if not relevant. 52 52 * \param void_key Pointer at the data to hash. 53 53 * \param key_len Size of the data to hash. … … 64 64 * \param init_val Initialization value. 65 65 * Using a different initialization value, you can generate a completely different set of hash values. 66 * Use 0 if not releva lt.66 * Use 0 if not relevant. 67 67 * \param void_key Pointer at the data to hash. 68 * \param key_len Size of the data to hash. 68 * \param key_len Size of the data to hash. 69 69 * \note 70 70 * This function is endianess independent. -
trunk/tommyDS_hashlin/tommyhashlin.c
r9093 r10636 1 1 /* 2 * Copyright 2010Andrea Mazzoleni. All rights reserved.2 * Copyright (c) 2010, Andrea Mazzoleni. All rights reserved. 3 3 * 4 4 * Redistribution and use in source and binary forms, with or without … … 13 13 * documentation and/or other materials provided with the distribution. 14 14 * 15 * THIS SOFTWARE IS PROVIDED BY ANDREA MAZZOLENI AND CONTRIBUTORS ``AS IS''15 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 16 16 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 17 17 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 18 * ARE DISCLAIMED. IN NO EVENT SHALL ANDREA MAZZOLENIOR CONTRIBUTORS BE18 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE 19 19 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 20 20 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF … … 29 29 #include "tommylist.h" 30 30 31 #include <string.h> /* for memset */32 31 #include <assert.h> /* for assert */ 33 32 … … 42 41 #define TOMMY_HASHLIN_STATE_SHRINK 2 43 42 43 /** 44 * Set the hashtable in stable state. 45 */ 46 tommy_inline void tommy_hashlin_stable(tommy_hashlin* hashlin) 47 { 48 hashlin->state = TOMMY_HASHLIN_STATE_STABLE; 49 50 /* setup low_mask/max/split to allow tommy_hashlin_bucket_ref() */ 51 /* and tommy_hashlin_foreach() to work regardless we are in stable state */ 52 hashlin->low_max = hashlin->bucket_max; 53 hashlin->low_mask = hashlin->bucket_mask; 54 hashlin->split = 0; 55 } 56 44 57 void tommy_hashlin_init(tommy_hashlin* hashlin) 45 58 { 59 tommy_uint_t i; 60 46 61 /* fixed initial size */ 47 62 hashlin->bucket_bit = TOMMY_HASHLIN_BIT; 48 63 hashlin->bucket_max = 1 << hashlin->bucket_bit; 49 64 hashlin->bucket_mask = hashlin->bucket_max - 1; 50 hashlin->bucket[0] = tommy_cast(tommy_hashlin_node**, tommy_ malloc(hashlin->bucket_max *sizeof(tommy_hashlin_node*)));51 memset(hashlin->bucket[0], 0, hashlin->bucket_max * sizeof(tommy_hashlin_node*));52 hashlin->bucket_mac = 1;65 hashlin->bucket[0] = tommy_cast(tommy_hashlin_node**, tommy_calloc(hashlin->bucket_max, sizeof(tommy_hashlin_node*))); 66 for (i = 1; i < TOMMY_HASHLIN_BIT; ++i) 67 hashlin->bucket[i] = hashlin->bucket[0]; 53 68 54 69 /* stable state */ 55 hashlin->state = TOMMY_HASHLIN_STATE_STABLE;70 tommy_hashlin_stable(hashlin); 56 71 57 72 hashlin->count = 0; … … 60 75 void tommy_hashlin_done(tommy_hashlin* hashlin) 61 76 { 62 /* we assume to be empty, so we free only the first bucket */ 63 assert(hashlin->bucket_mac == 1); 77 tommy_uint_t i; 64 78 65 79 tommy_free(hashlin->bucket[0]); 66 } 67 68 /** 69 * Return the bucket at the specified pos. 70 */ 71 tommy_inline tommy_hashlin_node** tommy_hashlin_pos(tommy_hashlin* hashlin, tommy_hash_t pos) 72 { 73 unsigned bsr; 74 75 /* special case for the first bucket */ 76 if (pos < (1 << TOMMY_HASHLIN_BIT)) { 77 return &hashlin->bucket[0][pos]; 78 } 79 80 /* get the highest bit set */ 81 bsr = tommy_ilog2_u32(pos); 82 83 /* clear the highest bit */ 84 pos -= 1 << bsr; 85 86 return &hashlin->bucket[bsr - TOMMY_HASHLIN_BIT + 1][pos]; 87 } 88 89 /** 90 * Return the bucket to use. 91 */ 92 tommy_inline tommy_hashlin_node** tommy_hashlin_bucket_ptr(tommy_hashlin* hashlin, tommy_hash_t hash) 93 { 94 unsigned pos; 95 96 /* if we are reallocating */ 97 if (hashlin->state != TOMMY_HASHLIN_STATE_STABLE) { 98 /* compute the old position */ 99 pos = hash & hashlin->low_mask; 100 101 /* if we have not reallocated this position yet */ 102 if (pos >= hashlin->split) { 103 104 /* use it as it was before */ 105 return tommy_hashlin_pos(hashlin, pos); 106 } 107 } 108 109 /* otherwise operates normally */ 110 pos = hash & hashlin->bucket_mask; 111 112 return tommy_hashlin_pos(hashlin, pos); 80 for (i = TOMMY_HASHLIN_BIT; i < hashlin->bucket_bit; ++i) { 81 tommy_hashlin_node** segment = hashlin->bucket[i]; 82 tommy_free(&segment[((tommy_ptrdiff_t)1) << i]); 83 } 113 84 } 114 85 … … 126 97 /* but in backward direction */ 127 98 if (hashlin->state == TOMMY_HASHLIN_STATE_STABLE) { 99 tommy_hashlin_node** segment; 100 128 101 /* set the lower size */ 129 102 hashlin->low_max = hashlin->bucket_max; 130 103 hashlin->low_mask = hashlin->bucket_mask; 131 104 132 /* grow the hash size and allocate */ 105 /* allocate the new vector using malloc() and not calloc() */ 106 /* because data is fully initialized in the split process */ 107 segment = tommy_cast(tommy_hashlin_node**, tommy_malloc(hashlin->low_max * sizeof(tommy_hashlin_node*))); 108 109 /* store it adjusting the offset */ 110 /* cast to ptrdiff_t to ensure to get a negative value */ 111 hashlin->bucket[hashlin->bucket_bit] = &segment[-(tommy_ptrdiff_t)hashlin->low_max]; 112 113 /* grow the hash size */ 133 114 ++hashlin->bucket_bit; 134 115 hashlin->bucket_max = 1 << hashlin->bucket_bit; 135 116 hashlin->bucket_mask = hashlin->bucket_max - 1; 136 hashlin->bucket[hashlin->bucket_mac] = tommy_cast(tommy_hashlin_node**, tommy_malloc(hashlin->low_max * sizeof(tommy_hashlin_node*)));137 ++hashlin->bucket_mac;138 117 139 118 /* start from the beginning going forward */ … … 148 127 if (hashlin->state == TOMMY_HASHLIN_STATE_GROW) { 149 128 /* compute the split target required to finish the reallocation before the next resize */ 150 unsignedsplit_target = 2 * hashlin->count;129 tommy_count_t split_target = 2 * hashlin->count; 151 130 152 131 /* reallocate buckets until the split target */ … … 154 133 tommy_hashlin_node** split[2]; 155 134 tommy_hashlin_node* j; 156 unsignedmask;135 tommy_count_t mask; 157 136 158 137 /* get the low bucket */ … … 160 139 161 140 /* get the high bucket */ 162 /* it's always in the second half, so we can index it directly */ 163 /* without calling tommy_hashlin_pos() */ 164 split[1] = &hashlin->bucket[hashlin->bucket_mac-1][hashlin->split]; 141 split[1] = tommy_hashlin_pos(hashlin, hashlin->split + hashlin->low_max); 165 142 166 143 /* save the low bucket */ … … 171 148 *split[1] = 0; 172 149 173 /* compute the bitto identify the bucket */174 mask = hashlin-> bucket_mask & ~hashlin->low_mask;150 /* the bit used to identify the bucket */ 151 mask = hashlin->low_max; 175 152 176 153 /* flush the bucket */ 177 154 while (j) { 178 155 tommy_hashlin_node* j_next = j->next; 179 unsigned index_= (j->key & mask) != 0;180 if (*split[ index_])181 tommy_list_insert_tail_not_empty(*split[ index_], j);156 tommy_count_t pos = (j->key & mask) != 0; 157 if (*split[pos]) 158 tommy_list_insert_tail_not_empty(*split[pos], j); 182 159 else 183 tommy_list_insert_first(split[ index_], j);160 tommy_list_insert_first(split[pos], j); 184 161 j = j_next; 185 162 } … … 190 167 /* if we have finished, change the state */ 191 168 if (hashlin->split == hashlin->low_max) { 192 hashlin->state = TOMMY_HASHLIN_STATE_STABLE; 169 /* go in stable mode */ 170 tommy_hashlin_stable(hashlin); 193 171 break; 194 172 } … … 228 206 if (hashlin->state == TOMMY_HASHLIN_STATE_SHRINK) { 229 207 /* compute the split target required to finish the reallocation before the next resize */ 230 unsignedsplit_target = 8 * hashlin->count;208 tommy_count_t split_target = 8 * hashlin->count; 231 209 232 210 /* reallocate buckets until the split target */ … … 236 214 /* go backward position */ 237 215 --hashlin->split; 238 216 239 217 /* get the low bucket */ 240 218 split[0] = tommy_hashlin_pos(hashlin, hashlin->split); 241 219 242 220 /* get the high bucket */ 243 /* it's always in the second half, so we can index it directly */ 244 /* without calling tommy_hashlin_pos() */ 245 split[1] = &hashlin->bucket[hashlin->bucket_mac-1][hashlin->split]; 221 split[1] = tommy_hashlin_pos(hashlin, hashlin->split + hashlin->low_max); 246 222 247 223 /* concat the high bucket into the low one */ … … 250 226 /* if we have finished, clean up and change the state */ 251 227 if (hashlin->split == 0) { 252 hashlin->state = TOMMY_HASHLIN_STATE_STABLE;228 tommy_hashlin_node** segment; 253 229 254 230 /* shrink the hash size */ … … 258 234 259 235 /* free the last segment */ 260 --hashlin->bucket_mac; 261 tommy_free(hashlin->bucket[hashlin->bucket_mac]); 236 segment = hashlin->bucket[hashlin->bucket_bit]; 237 tommy_free(&segment[((tommy_ptrdiff_t)1) << hashlin->bucket_bit]); 238 239 /* go in stable mode */ 240 tommy_hashlin_stable(hashlin); 262 241 break; 263 242 } … … 268 247 void tommy_hashlin_insert(tommy_hashlin* hashlin, tommy_hashlin_node* node, void* data, tommy_hash_t hash) 269 248 { 270 tommy_list_insert_tail(tommy_hashlin_bucket_ ptr(hashlin, hash), node, data);249 tommy_list_insert_tail(tommy_hashlin_bucket_ref(hashlin, hash), node, data); 271 250 272 251 node->key = hash; … … 279 258 void* tommy_hashlin_remove_existing(tommy_hashlin* hashlin, tommy_hashlin_node* node) 280 259 { 281 tommy_list_remove_existing(tommy_hashlin_bucket_ ptr(hashlin, node->key), node);260 tommy_list_remove_existing(tommy_hashlin_bucket_ref(hashlin, node->key), node); 282 261 283 262 --hashlin->count; … … 288 267 } 289 268 290 tommy_hashlin_node* tommy_hashlin_bucket(tommy_hashlin* hashlin, tommy_hash_t hash)291 {292 return *tommy_hashlin_bucket_ptr(hashlin, hash);293 }294 295 269 void* tommy_hashlin_remove(tommy_hashlin* hashlin, tommy_search_func* cmp, const void* cmp_arg, tommy_hash_t hash) 296 270 { 297 tommy_hashlin_node** let_ptr = tommy_hashlin_bucket_ ptr(hashlin, hash);298 tommy_hashlin_node* i= *let_ptr;299 300 while ( i) {271 tommy_hashlin_node** let_ptr = tommy_hashlin_bucket_ref(hashlin, hash); 272 tommy_hashlin_node* node = *let_ptr; 273 274 while (node) { 301 275 /* we first check if the hash matches, as in the same bucket we may have multiples hash values */ 302 if ( i->key == hash && cmp(cmp_arg, i->data) == 0) {303 tommy_list_remove_existing(let_ptr, i);276 if (node->key == hash && cmp(cmp_arg, node->data) == 0) { 277 tommy_list_remove_existing(let_ptr, node); 304 278 305 279 --hashlin->count; … … 307 281 hashlin_shrink_step(hashlin); 308 282 309 return i->data;310 } 311 i = i->next;283 return node->data; 284 } 285 node = node->next; 312 286 } 313 287 … … 315 289 } 316 290 291 void tommy_hashlin_foreach(tommy_hashlin* hashlin, tommy_foreach_func* func) 292 { 293 tommy_count_t bucket_max; 294 tommy_count_t pos; 295 296 /* number of valid buckets */ 297 bucket_max = hashlin->low_max + hashlin->split; 298 299 for (pos = 0; pos < bucket_max; ++pos) { 300 tommy_hashlin_node* node = *tommy_hashlin_pos(hashlin, pos); 301 302 while (node) { 303 void* data = node->data; 304 node = node->next; 305 func(data); 306 } 307 } 308 } 309 310 void tommy_hashlin_foreach_arg(tommy_hashlin* hashlin, tommy_foreach_arg_func* func, void* arg) 311 { 312 tommy_count_t bucket_max; 313 tommy_count_t pos; 314 315 /* number of valid buckets */ 316 bucket_max = hashlin->low_max + hashlin->split; 317 318 for (pos = 0; pos < bucket_max; ++pos) { 319 tommy_hashlin_node* node = *tommy_hashlin_pos(hashlin, pos); 320 321 while (node) { 322 void* data = node->data; 323 node = node->next; 324 func(arg, data); 325 } 326 } 327 } 328 317 329 tommy_size_t tommy_hashlin_memory_usage(tommy_hashlin* hashlin) 318 330 { 319 331 return hashlin->bucket_max * (tommy_size_t)sizeof(hashlin->bucket[0][0]) 320 321 } 322 332 + hashlin->count * (tommy_size_t)sizeof(tommy_hashlin_node); 333 } 334 -
trunk/tommyDS_hashlin/tommyhashlin.h
r9093 r10636 1 1 /* 2 * Copyright 2010Andrea Mazzoleni. All rights reserved.2 * Copyright (c) 2010, Andrea Mazzoleni. All rights reserved. 3 3 * 4 4 * Redistribution and use in source and binary forms, with or without … … 13 13 * documentation and/or other materials provided with the distribution. 14 14 * 15 * THIS SOFTWARE IS PROVIDED BY ANDREA MAZZOLENI AND CONTRIBUTORS ``AS IS''15 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 16 16 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 17 17 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 18 * ARE DISCLAIMED. IN NO EVENT SHALL ANDREA MAZZOLENIOR CONTRIBUTORS BE18 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE 19 19 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 20 20 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF … … 85 85 * } 86 86 * 87 * int value_to_find = 1; 87 * int value_to_find = 1; 88 88 * struct object* obj = tommy_hashlin_search(&hashlin, compare, &value_to_find, tommy_inthash_u32(value_to_find)); 89 89 * if (!obj) { … … 100 100 * 101 101 * \code 102 * int value_to_find = 1; 102 * int value_to_find = 1; 103 103 * tommy_node* i = tommy_hashlin_bucket(&hashlin, tommy_inthash_u32(value_to_find)); 104 104 * while (i) { … … 118 118 * 119 119 * \code 120 * struct object* obj = tommy_ trie_remove(&hashtable, compare, &value_to_remove, tommy_inthash_u32(value_to_remove));120 * struct object* obj = tommy_hashlin_remove(&hashlin, compare, &value_to_remove, tommy_inthash_u32(value_to_remove)); 121 121 * if (obj) { 122 122 * free(obj); // frees the object allocated memory … … 131 131 * \endcode 132 132 * 133 * Note that you cannot iterates over all the elements in the hashtable using the 134 * hashtable itself. You have to insert all the elements also in a ::tommy_list, 135 * and use the list to iterate. See the \ref multiindex example for more detail. 133 * If you need to iterate over all the elements in the hashtable, you can use 134 * tommy_hashlin_foreach() or tommy_hashlin_foreach_arg(). 135 * If you need a more precise control with a real iteration, you have to insert 136 * all the elements also in a ::tommy_list, and use the list to iterate. 137 * See the \ref multiindex example for more detail. 136 138 */ 137 139 … … 151 153 152 154 /** 153 * Linear hashtable node.155 * Hashtable node. 154 156 * This is the node that you have to include inside your objects. 155 157 */ … … 162 164 163 165 /** 164 * Linear chained hashtable. 166 * Hashtable container type. 167 * \note Don't use internal fields directly, but access the container only using functions. 165 168 */ 166 169 typedef struct tommy_hashlin_struct { 167 170 tommy_hashlin_node** bucket[TOMMY_HASHLIN_BIT_MAX]; /**< Dynamic array of hash buckets. One list for each hash modulus. */ 168 unsigned bucket_bit; /**< Bits used in the bit mask. */ 169 unsigned bucket_max; /**< Number of buckets. */ 170 unsigned bucket_mask; /**< Bit mask to access the buckets. */ 171 unsigned bucket_mac; /**< Number of vectors allocated. */ 172 unsigned low_max; /**< Low order max value. */ 173 unsigned low_mask; /**< Low order mask value. */ 174 unsigned split; /**< Split position. */ 175 unsigned state; /**< Reallocation state. */ 176 unsigned count; /**< Number of elements. */ 171 tommy_uint_t bucket_bit; /**< Bits used in the bit mask. */ 172 tommy_count_t bucket_max; /**< Number of buckets. */ 173 tommy_count_t bucket_mask; /**< Bit mask to access the buckets. */ 174 tommy_count_t low_max; /**< Low order max value. */ 175 tommy_count_t low_mask; /**< Low order mask value. */ 176 tommy_count_t split; /**< Split position. */ 177 tommy_count_t count; /**< Number of elements. */ 178 tommy_uint_t state; /**< Reallocation state. */ 177 179 } tommy_hashlin; 178 180 … … 184 186 /** 185 187 * Deinitializes the hashtable. 188 * 189 * You can call this function with elements still contained, 190 * but such elements are not going to be freed by this call. 186 191 */ 187 192 void tommy_hashlin_done(tommy_hashlin* hashlin); 188 193 189 194 /** 190 * Inserts an element in the thehashtable.195 * Inserts an element in the hashtable. 191 196 */ 192 197 void tommy_hashlin_insert(tommy_hashlin* hashlin, tommy_hashlin_node* node, void* data, tommy_hash_t hash); … … 197 202 * If the element is not found, 0 is returned. 198 203 * If more equal elements are present, the first one is removed. 199 * This operation is faster than calling tommy_hashlin_bucket() and tommy_hashlin_remove_existing() separately.200 204 * \param cmp Compare function called with cmp_arg as first argument and with the element to compare as a second one. 201 205 * The function should return 0 for equal elements, anything other for different elements. … … 205 209 */ 206 210 void* tommy_hashlin_remove(tommy_hashlin* hashlin, tommy_search_func* cmp, const void* cmp_arg, tommy_hash_t hash); 211 212 /** \internal 213 * Returns the bucket at the specified position. 214 */ 215 tommy_inline tommy_hashlin_node** tommy_hashlin_pos(tommy_hashlin* hashlin, tommy_hash_t pos) 216 { 217 tommy_uint_t bsr; 218 219 /* get the highest bit set, in case of all 0, return 0 */ 220 bsr = tommy_ilog2_u32(pos | 1); 221 222 return &hashlin->bucket[bsr][pos]; 223 } 224 225 /** \internal 226 * Returns a pointer to the bucket of the specified hash. 227 */ 228 tommy_inline tommy_hashlin_node** tommy_hashlin_bucket_ref(tommy_hashlin* hashlin, tommy_hash_t hash) 229 { 230 tommy_count_t pos; 231 tommy_count_t high_pos; 232 233 pos = hash & hashlin->low_mask; 234 high_pos = hash & hashlin->bucket_mask; 235 236 /* if this position is already allocated in the high half */ 237 if (pos < hashlin->split) { 238 /* The following assigment is expected to be implemented */ 239 /* with a conditional move instruction */ 240 /* that results in a little better and constant performance */ 241 /* regardless of the split position. */ 242 /* This affects mostly the worst case, when the split value */ 243 /* is near at its half, resulting in a totally unpredictable */ 244 /* condition by the CPU. */ 245 /* In such case the use of the conditional move is generally faster. */ 246 247 /* use also the high bit */ 248 pos = high_pos; 249 } 250 251 return tommy_hashlin_pos(hashlin, pos); 252 } 207 253 208 254 /** … … 214 260 * \return The head of the bucket, or 0 if empty. 215 261 */ 216 tommy_hashlin_node* tommy_hashlin_bucket(tommy_hashlin* hashlin, tommy_hash_t hash); 262 tommy_inline tommy_hashlin_node* tommy_hashlin_bucket(tommy_hashlin* hashlin, tommy_hash_t hash) 263 { 264 return *tommy_hashlin_bucket_ref(hashlin, hash); 265 } 217 266 218 267 /** … … 229 278 { 230 279 tommy_hashlin_node* i = tommy_hashlin_bucket(hashlin, hash); 280 231 281 while (i) { 232 282 /* we first check if the hash matches, as in the same bucket we may have multiples hash values */ … … 246 296 247 297 /** 298 * Calls the specified function for each element in the hashtable. 299 * 300 * You can use this function to deallocate all the elements inserted. 301 * 302 * \code 303 * tommy_hashlin hashlin; 304 * 305 * // initializes the hashtable 306 * tommy_hashlin_init(&hashlin); 307 * 308 * ... 309 * 310 * // creates an object 311 * struct object* obj = malloc(sizeof(struct object)); 312 * 313 * ... 314 * 315 * // insert it in the hashtable 316 * tommy_hashlin_insert(&hashlin, &obj->node, obj, tommy_inthash_u32(obj->value)); 317 * 318 * ... 319 * 320 * // deallocates all the objects iterating the hashtable 321 * tommy_hashlin_foreach(&hashlin, free); 322 * 323 * // deallocates the hashtable 324 * tommy_hashlin_done(&hashlin); 325 * \endcode 326 */ 327 void tommy_hashlin_foreach(tommy_hashlin* hashlin, tommy_foreach_func* func); 328 329 /** 330 * Calls the specified function with an argument for each element in the hashtable. 331 */ 332 void tommy_hashlin_foreach_arg(tommy_hashlin* hashlin, tommy_foreach_arg_func* func, void* arg); 333 334 /** 248 335 * Gets the number of elements. 249 336 */ 250 tommy_inline unsignedtommy_hashlin_count(tommy_hashlin* hashlin)337 tommy_inline tommy_count_t tommy_hashlin_count(tommy_hashlin* hashlin) 251 338 { 252 339 return hashlin->count; -
trunk/tommyDS_hashlin/tommylist.c
r9093 r10636 1 1 /* 2 * Copyright 2010Andrea Mazzoleni. All rights reserved.2 * Copyright (c) 2010, Andrea Mazzoleni. All rights reserved. 3 3 * 4 4 * Redistribution and use in source and binary forms, with or without … … 13 13 * documentation and/or other materials provided with the distribution. 14 14 * 15 * THIS SOFTWARE IS PROVIDED BY ANDREA MAZZOLENI AND CONTRIBUTORS ``AS IS''15 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 16 16 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 17 17 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 18 * ARE DISCLAIMED. IN NO EVENT SHALL ANDREA MAZZOLENIOR CONTRIBUTORS BE18 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE 19 19 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 20 20 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF … … 35 35 tommy_node* second_head; 36 36 37 if (tommy_list_empty(second)) {37 if (tommy_list_empty(second)) 38 38 return; 39 }40 39 41 40 if (tommy_list_empty(first)) { -
trunk/tommyDS_hashlin/tommylist.h
r9093 r10636 1 1 /* 2 * Copyright 2010Andrea Mazzoleni. All rights reserved.2 * Copyright (c) 2010, Andrea Mazzoleni. All rights reserved. 3 3 * 4 4 * Redistribution and use in source and binary forms, with or without … … 13 13 * documentation and/or other materials provided with the distribution. 14 14 * 15 * THIS SOFTWARE IS PROVIDED BY ANDREA MAZZOLENI AND CONTRIBUTORS ``AS IS''15 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 16 16 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 17 17 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 18 * ARE DISCLAIMED. IN NO EVENT SHALL ANDREA MAZZOLENIOR CONTRIBUTORS BE18 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE 19 19 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 20 20 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF … … 29 29 * Double linked list for collisions into hashtables. 30 30 * 31 * This list is a double linked list mainly targetted for collisions into an hashtables,32 * but useable also as a generic list.31 * This list is a double linked list mainly targetted for handling collisions 32 * into an hashtables, but useable also as a generic list. 33 33 * 34 34 * The main feature of this list is to require only one pointer to represent the 35 * list, compared to a classic implementation requiring a nhead an a tail pointers.35 * list, compared to a classic implementation requiring a head an a tail pointers. 36 36 * This reduces the memory usage in hashtables. 37 37 * … … 40 40 * their insertion order. 41 41 * 42 * To initialize the list, you have to call tommy_list_init(), or simply assign42 * To initialize the list, you have to call tommy_list_init(), or to simply assign 43 43 * to it NULL, as an empty list is represented by the NULL value. 44 44 * … … 70 70 * \endcode 71 71 * 72 * To iterate sover all the elements in the list you have to call72 * To iterate over all the elements in the list you have to call 73 73 * tommy_list_head() to get the head of the list and follow the 74 74 * tommy_node::next pointer until NULL. … … 85 85 * \endcode 86 86 * 87 * To destroy the list you have only to remove all the elements, as the list is 88 * completely inplace and it doesn't allocate memory. 89 * 90 * \code 91 * tommy_node* i = tommy_list_head(&list); 92 * while (i) { 93 * tommy_node* i_next = i->next; // saves the next element before freeing 94 * 95 * free(i->data); // frees the object allocated memory 96 * 97 * i = i_next; // goes to the next element 98 * } 99 * \endcode 87 * To destroy the list you have to remove all the elements, 88 * as the list is completely inplace and it doesn't allocate memory. 89 * This can be done with the tommy_list_foreach() function. 90 * 91 * \code 92 * // deallocates all the objects iterating the list 93 * tommy_list_foreach(&list, free); 94 * \endcode 100 95 */ 101 96 … … 109 104 110 105 /** 111 * Double linked list for collisions into hashtables.106 * Double linked list type. 112 107 */ 113 108 typedef tommy_node* tommy_list; … … 152 147 tommy_inline void tommy_list_insert_first(tommy_list* list, tommy_node* node) 153 148 { 154 /* one element "circular" prev list */ 149 /* one element "circular" prev list */ 155 150 node->prev = node; 156 151 … … 207 202 tommy_node* head = tommy_list_head(list); 208 203 209 if (head) {204 if (head) 210 205 tommy_list_insert_head_not_empty(list, node); 211 } else {206 else 212 207 tommy_list_insert_first(list, node); 213 }214 208 215 209 node->data = data; … … 225 219 tommy_node* head = tommy_list_head(list); 226 220 227 if (head) {221 if (head) 228 222 tommy_list_insert_tail_not_empty(head, node); 229 } else {223 else 230 224 tommy_list_insert_first(list, node); 231 }232 225 233 226 node->data = data; … … 265 258 266 259 /* remove from the "circular" prev list */ 267 if (node->next) {260 if (node->next) 268 261 node->next->prev = node->prev; 269 } else {262 else 270 263 head->prev = node->prev; /* the last */ 271 }272 264 273 265 /* remove from the "0 terminated" next list */ 274 if (head == node) {266 if (head == node) 275 267 *list = node->next; /* the new head, in case 0 */ 276 } else {268 else 277 269 node->prev->next = node->next; 278 }279 270 280 271 return node->data; … … 295 286 * It's faster on degenerated cases like partially ordered lists. 296 287 * \param cmp Compare function called with two elements. 297 * The function should return <0 if the first element is less than the second, == 0 if equal, and >0 if greather.288 * The function should return <0 if the first element is less than the second, ==0 if equal, and >0 if greather. 298 289 */ 299 290 void tommy_list_sort(tommy_list* list, tommy_compare_func* cmp); … … 310 301 /** 311 302 * Calls the specified function for each element in the list. 303 * 304 * You can use this function to deallocate all the elements 305 * inserted in a list. 306 * 307 * \code 308 * tommy_list list; 309 * 310 * // initializes the list 311 * tommy_list_init(&list); 312 * 313 * ... 314 * 315 * // creates an object 316 * struct object* obj = malloc(sizeof(struct object)); 317 * 318 * ... 319 * 320 * // insert it in the list 321 * tommy_list_insert_tail(&list, &obj->node, obj); 322 * 323 * ... 324 * 325 * // deallocates all the objects iterating the list 326 * tommy_list_foreach(&list, free); 327 * \endcode 312 328 */ 313 329 tommy_inline void tommy_list_foreach(tommy_list* list, tommy_foreach_func* func) 314 330 { 315 331 tommy_node* node = tommy_list_head(list); 332 316 333 while (node) { 317 334 void* data = node->data; … … 322 339 323 340 /** 324 * Calls the specified function with a rgument for each element in the list.341 * Calls the specified function with an argument for each element in the list. 325 342 */ 326 343 tommy_inline void tommy_list_foreach_arg(tommy_list* list, tommy_foreach_arg_func* func, void* arg) 327 344 { 328 345 tommy_node* node = tommy_list_head(list); 346 329 347 while (node) { 330 348 void* data = node->data; -
trunk/tommyDS_hashlin/tommytypes.h
r9105 r10636 1 1 /* 2 * Copyright 2010Andrea Mazzoleni. All rights reserved.2 * Copyright (c) 2010, Andrea Mazzoleni. All rights reserved. 3 3 * 4 4 * Redistribution and use in source and binary forms, with or without … … 13 13 * documentation and/or other materials provided with the distribution. 14 14 * 15 * THIS SOFTWARE IS PROVIDED BY ANDREA MAZZOLENI AND CONTRIBUTORS ``AS IS''15 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 16 16 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 17 17 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 18 * ARE DISCLAIMED. IN NO EVENT SHALL ANDREA MAZZOLENIOR CONTRIBUTORS BE18 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE 19 19 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 20 20 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF … … 36 36 /* types */ 37 37 38 #include <stddef.h> 39 38 40 #if defined(_MSC_VER) 39 #include <stddef.h>40 41 typedef unsigned tommy_uint32_t; /**< Generic uint32_t type. */ 41 42 typedef unsigned _int64 tommy_uint64_t; /**< Generic uint64_t type. */ 42 typedef size_t tommy_size_t; /**< Generic size_t type. */43 43 typedef size_t tommy_uintptr_t; /**< Generic uintptr_t type. */ 44 44 #else … … 46 46 typedef uint32_t tommy_uint32_t; /**< Generic uint32_t type. */ 47 47 typedef uint64_t tommy_uint64_t; /**< Generic uint64_t type. */ 48 typedef uintptr_t tommy_size_t; /**< Generic size_t type. */49 48 typedef uintptr_t tommy_uintptr_t; /**< Generic uintptr_t type. */ 50 49 #endif 50 typedef size_t tommy_size_t; /**< Generic size_t type. */ 51 typedef ptrdiff_t tommy_ptrdiff_t; /**< Generic ptrdiff_t type. */ 51 52 typedef int tommy_bool_t; /**< Generic boolean type. */ 53 54 /** 55 * Generic unsigned integer type. 56 * 57 * It has no specific size, as is used to store only small values. 58 * To make the code more efficient, a full 32 bit integer is used. 59 */ 60 typedef tommy_uint32_t tommy_uint_t; 61 62 /** 63 * Generic unsigned integer for counting objects. 64 * 65 * TommyDS doesn't support more than 2^32-1 objects. 66 */ 67 typedef tommy_uint32_t tommy_count_t; 52 68 53 69 /** \internal … … 65 81 /* heap */ 66 82 67 /* by default uses malloc/ realloc/free */68 69 /** 70 * Generic malloc(), realloc() and free() functions.71 * Redefine them to what you need. By default they map to the C malloc(), realloc() and free().72 */ 73 #if !defined(tommy_malloc) && !defined(tommy_realloc) &&!defined(tommy_free)83 /* by default uses malloc/calloc/realloc/free */ 84 85 /** 86 * Generic malloc(), calloc(), realloc() and free() functions. 87 * Redefine them to what you need. By default they map to the C malloc(), calloc(), realloc() and free(). 88 */ 89 #if !defined(tommy_malloc) || !defined(tommy_calloc) || !defined(tommy_realloc) || !defined(tommy_free) 74 90 #include <stdlib.h> 91 #endif 92 #if !defined(tommy_malloc) 75 93 #define tommy_malloc malloc 94 #endif 95 #if !defined(tommy_calloc) 96 #define tommy_calloc calloc 97 #endif 98 #if !defined(tommy_realloc) 76 99 #define tommy_realloc realloc 100 #endif 101 #if !defined(tommy_free) 77 102 #define tommy_free free 78 103 #endif … … 110 135 #if !defined(tommy_likely) 111 136 #if defined(__GNUC__) 112 #define tommy_likely(x) __builtin_expect(!!(x), 1)137 #define tommy_likely(x) __builtin_expect(!!(x), 1) 113 138 #else 114 139 #define tommy_likely(x) (x) … … 121 146 #if !defined(tommy_unlikely) 122 147 #if defined(__GNUC__) 123 #define tommy_unlikely(x) __builtin_expect(!!(x), 0)148 #define tommy_unlikely(x) __builtin_expect(!!(x), 0) 124 149 #else 125 150 #define tommy_unlikely(x) (x) … … 219 244 * \param arg Pointer at the value to search. 220 245 * \param obj Pointer at the object to compare to. 221 * \return ==0 if the value matches the element. != 246 * \return ==0 if the value matches the element. !=0 if different. 222 247 * 223 248 * Note that the first argument is a pointer to the value to search and … … 236 261 * } 237 262 * 238 * int value_to_find = 1; 263 * int value_to_find = 1; 239 264 * struct object* obj = tommy_hashtable_search(&hashtable, compare, &value_to_find, tommy_inthash_u32(value_to_find)); 240 265 * if (!obj) { … … 243 268 * // found 244 269 * } 245 * \endcode 270 * \endcode 246 271 * 247 272 */ … … 272 297 #include <intrin.h> 273 298 #pragma intrinsic(_BitScanReverse) 299 #pragma intrinsic(_BitScanForward) 274 300 #endif 275 301 … … 278 304 * You can use it only for exact power of 2 up to 256. 279 305 */ 280 #define TOMMY_ILOG2(value) ((value) == 256 ? 8 : (value) == 128 ? 7 : (value) == 64 ? 6 : (value) == 32 ? 5 : (value) == 16 ? 4 : (value) == 8 ? 3 : (value) == 4 ? 2 : (value) == 2 ? 1 : 0)306 #define TOMMY_ILOG2(value) ((value) == 256 ? 8 : (value) == 128 ? 7 : (value) == 64 ? 6 : (value) == 32 ? 5 : (value) == 16 ? 4 : (value) == 8 ? 3 : (value) == 4 ? 2 : (value) == 2 ? 1 : 0) 281 307 282 308 /** … … 285 311 * 286 312 * If no bit is set, the result is undefined. 287 * To force a return 0 in this case, you can use tommy_ilog2 (value | 1).288 * 289 * Other interesting ways for bitscan can be foundat:290 * 291 * Bit Twiddling Hacks 292 * http://graphics.stanford.edu/~seander/bithacks.html 313 * To force a return 0 in this case, you can use tommy_ilog2_u32(value | 1). 314 * 315 * Other interesting ways for bitscan are at: 316 * 317 * Bit Twiddling Hacks 318 * http://graphics.stanford.edu/~seander/bithacks.html 293 319 * 294 320 * Chess Programming BitScan … … 296 322 * 297 323 * \param value Value to scan. 0 is not allowed. 298 * \return The index of the most significan bit set.299 */ 300 tommy_inline unsignedtommy_ilog2_u32(tommy_uint32_t value)324 * \return The index of the most significant bit set. 325 */ 326 tommy_inline tommy_uint_t tommy_ilog2_u32(tommy_uint32_t value) 301 327 { 328 #if defined(_MSC_VER) 329 unsigned long count; 330 _BitScanReverse(&count, value); 331 return count; 332 #elif defined(__GNUC__) 333 /* 334 * GCC implements __builtin_clz(x) as "__builtin_clz(x) = bsr(x) ^ 31" 335 * 336 * Where "x ^ 31 = 31 - x", but gcc does not optimize "31 - __builtin_clz(x)" to bsr(x), 337 * but generates 31 - (bsr(x) xor 31). 338 * 339 * So we write "__builtin_clz(x) ^ 31" instead of "31 - __builtin_clz(x)", 340 * to allow the double xor to be optimized out. 341 */ 342 return __builtin_clz(value) ^ 31; 343 #else 302 344 /* Find the log base 2 of an N-bit integer in O(lg(N)) operations with multiply and lookup */ 303 345 /* from http://graphics.stanford.edu/~seander/bithacks.html */ 304 static const intTOMMY_DE_BRUIJN_INDEX_ILOG2[32] = {346 static unsigned char TOMMY_DE_BRUIJN_INDEX_ILOG2[32] = { 305 347 0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30, 306 348 8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31 … … 314 356 315 357 return TOMMY_DE_BRUIJN_INDEX_ILOG2[(tommy_uint32_t)(value * 0x07C4ACDDU) >> 27]; 358 #endif 316 359 } 317 360 … … 322 365 * If no bit is set, the result is undefined. 323 366 * \param value Value to scan. 0 is not allowed. 324 * \return The index of the least significan bit set.325 */ 326 tommy_inline unsignedtommy_ctz_u32(tommy_uint32_t value)367 * \return The index of the least significant bit set. 368 */ 369 tommy_inline tommy_uint_t tommy_ctz_u32(tommy_uint32_t value) 327 370 { 371 #if defined(_MSC_VER) 372 unsigned long count; 373 _BitScanForward(&count, value); 374 return count; 375 #elif defined(__GNUC__) 376 return __builtin_ctz(value); 377 #else 328 378 /* Count the consecutive zero bits (trailing) on the right with multiply and lookup */ 329 379 /* from http://graphics.stanford.edu/~seander/bithacks.html */ 330 static const tommy_uint32_tTOMMY_DE_BRUIJN_INDEX_CTZ[32] = {380 static const unsigned char TOMMY_DE_BRUIJN_INDEX_CTZ[32] = { 331 381 0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8, 332 382 31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9 333 383 }; 334 384 335 return TOMMY_DE_BRUIJN_INDEX_CTZ[(tommy_uint32_t)(((value & -value) * 0x077CB531U)) >> 27]; 385 return TOMMY_DE_BRUIJN_INDEX_CTZ[(tommy_uint32_t)(((value & - value) * 0x077CB531U)) >> 27]; 386 #endif 336 387 } 337 388
Note:
See TracChangeset
for help on using the changeset viewer.