2 * Various storage structures (pool allocation, vector, hash table)
4 * Copyright (C) 1993, Eric Youngdale.
7 * This library is free software; you can redistribute it and/or
8 * modify it under the terms of the GNU Lesser General Public
9 * License as published by the Free Software Foundation; either
10 * version 2.1 of the License, or (at your option) any later version.
12 * This library is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 * Lesser General Public License for more details.
17 * You should have received a copy of the GNU Lesser General Public
18 * License along with this library; if not, write to the Free Software
19 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA
25 #include "wine/debug.h"
27 #include "dbghelp_private.h"
29 WINE_DEFAULT_DEBUG_CHANNEL(dbghelp
);
31 void pool_init(struct pool
* pool
, size_t arena_size
)
33 pool
->heap
= HeapCreate(HEAP_NO_SERIALIZE
, arena_size
, 0);
36 void pool_destroy(struct pool
* pool
)
38 HeapDestroy(pool
->heap
);
41 void* pool_alloc(struct pool
* pool
, size_t len
)
43 return HeapAlloc(pool
->heap
, 0, len
);
46 void* pool_realloc(struct pool
* pool
, void* ptr
, size_t len
)
48 return ptr
? HeapReAlloc(pool
->heap
, 0, ptr
, len
) : pool_alloc(pool
, len
);
51 char* pool_strdup(struct pool
* pool
, const char* str
)
54 if ((ret
= pool_alloc(pool
, strlen(str
) + 1))) strcpy(ret
, str
);
58 void vector_init(struct vector
* v
, unsigned esz
, unsigned bucket_sz
)
61 /* align size on DWORD boundaries */
62 v
->elt_size
= (esz
+ 3) & ~3;
65 case 2: v
->shift
= 1; break;
66 case 4: v
->shift
= 2; break;
67 case 8: v
->shift
= 3; break;
68 case 16: v
->shift
= 4; break;
69 case 32: v
->shift
= 5; break;
70 case 64: v
->shift
= 6; break;
71 case 128: v
->shift
= 7; break;
72 case 256: v
->shift
= 8; break;
73 case 512: v
->shift
= 9; break;
74 case 1024: v
->shift
= 10; break;
78 v
->buckets_allocated
= 0;
82 unsigned vector_length(const struct vector
* v
)
87 void* vector_at(const struct vector
* v
, unsigned pos
)
91 if (pos
>= v
->num_elts
) return NULL
;
92 o
= pos
& ((1 << v
->shift
) - 1);
93 return (char*)v
->buckets
[pos
>> v
->shift
] + o
* v
->elt_size
;
96 void* vector_add(struct vector
* v
, struct pool
* pool
)
98 if (v
->num_elts
== (v
->num_buckets
<< v
->shift
))
100 if (v
->num_buckets
== v
->buckets_allocated
)
102 /* Double the bucket cache, so it scales well with big vectors.*/
103 unsigned new_reserved
= v
->buckets_allocated
? v
->buckets_allocated
* 2 : 1;
106 new = pool_realloc(pool
, v
->buckets
, new_reserved
* sizeof(void*));
107 if (!new) return NULL
;
109 v
->buckets_allocated
= new_reserved
;
111 v
->buckets
[v
->num_buckets
] = pool_alloc(pool
, v
->elt_size
<< v
->shift
);
112 if (!v
->buckets
[v
->num_buckets
]) return NULL
;
114 return v
->buckets
[v
->num_buckets
++];
116 return vector_at(v
, v
->num_elts
++);
119 /* We construct the sparse array as two vectors (of equal size)
120 * The first vector (key2index) is the lookup table between the key and
121 * an index in the second vector (elements)
122 * When inserting an element, it's always appended in second vector (and
123 * never moved in memory later on), only the first vector is reordered
131 void sparse_array_init(struct sparse_array
* sa
, unsigned elt_sz
, unsigned bucket_sz
)
133 vector_init(&sa
->key2index
, sizeof(struct key2index
), bucket_sz
);
134 vector_init(&sa
->elements
, elt_sz
, bucket_sz
);
137 /******************************************************************
138 * sparse_array_lookup
140 * Returns the first index which key is >= at passed key
142 static struct key2index
* sparse_array_lookup(const struct sparse_array
* sa
,
143 ULONG_PTR key
, unsigned* idx
)
145 struct key2index
* pk2i
;
148 if (!sa
->elements
.num_elts
)
153 high
= sa
->elements
.num_elts
;
154 pk2i
= vector_at(&sa
->key2index
, high
- 1);
160 if (pk2i
->key
== key
)
166 pk2i
= vector_at(&sa
->key2index
, low
);
167 if (pk2i
->key
>= key
)
172 /* now we have: sa(lowest key) < key < sa(highest key) */
175 *idx
= (low
+ high
) / 2;
176 pk2i
= vector_at(&sa
->key2index
, *idx
);
177 if (pk2i
->key
> key
) high
= *idx
;
178 else if (pk2i
->key
< key
) low
= *idx
+ 1;
181 /* binary search could return exact item, we search for highest one
185 pk2i
= vector_at(&sa
->key2index
, ++(*idx
));
189 void* sparse_array_find(const struct sparse_array
* sa
, ULONG_PTR key
)
192 struct key2index
* pk2i
;
194 if ((pk2i
= sparse_array_lookup(sa
, key
, &idx
)) && pk2i
->key
== key
)
195 return vector_at(&sa
->elements
, pk2i
->index
);
199 void* sparse_array_add(struct sparse_array
* sa
, ULONG_PTR key
,
203 struct key2index
* pk2i
;
204 struct key2index
* to
;
206 pk2i
= sparse_array_lookup(sa
, key
, &idx
);
207 if (pk2i
&& pk2i
->key
== key
)
209 FIXME("re-adding an existing key\n");
212 to
= vector_add(&sa
->key2index
, pool
);
215 /* we need to shift vector's content... */
216 /* let's do it brute force... (FIXME) */
217 assert(sa
->key2index
.num_elts
>= 2);
218 for (i
= sa
->key2index
.num_elts
- 1; i
> idx
; i
--)
220 pk2i
= vector_at(&sa
->key2index
, i
- 1);
227 to
->index
= sa
->elements
.num_elts
;
229 return vector_add(&sa
->elements
, pool
);
232 unsigned sparse_array_length(const struct sparse_array
* sa
)
234 return sa
->elements
.num_elts
;
237 static unsigned hash_table_hash(const char* name
, unsigned num_buckets
)
243 hash
+= (hash
<< 10);
247 hash
^= (hash
>> 11);
248 hash
+= (hash
<< 15);
249 return hash
% num_buckets
;
252 void hash_table_init(struct pool
* pool
, struct hash_table
* ht
, unsigned num_buckets
)
255 ht
->num_buckets
= num_buckets
;
260 void hash_table_destroy(struct hash_table
* ht
)
262 #if defined(USE_STATS)
265 unsigned min
= 0xffffffff, max
= 0, sq
= 0;
266 struct hash_table_elt
* elt
;
267 double mean
, variance
;
269 for (i
= 0; i
< ht
->num_buckets
; i
++)
271 for (len
= 0, elt
= ht
->buckets
[i
]; elt
; elt
= elt
->next
) len
++;
272 if (len
< min
) min
= len
;
273 if (len
> max
) max
= len
;
276 mean
= (double)ht
->num_elts
/ ht
->num_buckets
;
277 variance
= (double)sq
/ ht
->num_buckets
- mean
* mean
;
278 FIXME("STATS: elts[num:%-4u size:%u mean:%f] buckets[min:%-4u variance:%+f max:%-4u]\n",
279 ht
->num_elts
, ht
->num_buckets
, mean
, min
, variance
, max
);
281 for (i
= 0; i
< ht
->num_buckets
; i
++)
283 for (len
= 0, elt
= ht
->buckets
[i
]; elt
; elt
= elt
->next
) len
++;
286 FIXME("Longest bucket:\n");
287 for (elt
= ht
->buckets
[i
]; elt
; elt
= elt
->next
)
288 FIXME("\t%s\n", elt
->name
);
296 void hash_table_add(struct hash_table
* ht
, struct hash_table_elt
* elt
)
298 unsigned hash
= hash_table_hash(elt
->name
, ht
->num_buckets
);
302 ht
->buckets
= pool_alloc(ht
->pool
, ht
->num_buckets
* sizeof(struct hash_table_bucket
));
304 memset(ht
->buckets
, 0, ht
->num_buckets
* sizeof(struct hash_table_bucket
));
307 /* in some cases, we need to get back the symbols of same name in the order
308 * in which they've been inserted. So insert new elements at the end of the list.
310 if (!ht
->buckets
[hash
].first
)
312 ht
->buckets
[hash
].first
= elt
;
316 ht
->buckets
[hash
].last
->next
= elt
;
318 ht
->buckets
[hash
].last
= elt
;
323 void hash_table_iter_init(const struct hash_table
* ht
,
324 struct hash_table_iter
* hti
, const char* name
)
329 hti
->last
= hash_table_hash(name
, ht
->num_buckets
);
330 hti
->index
= hti
->last
- 1;
334 hti
->last
= ht
->num_buckets
- 1;
340 void* hash_table_iter_up(struct hash_table_iter
* hti
)
342 if (!hti
->ht
->buckets
) return NULL
;
344 if (hti
->element
) hti
->element
= hti
->element
->next
;
345 while (!hti
->element
&& hti
->index
< hti
->last
)
346 hti
->element
= hti
->ht
->buckets
[++hti
->index
].first
;