ReactOS  0.4.15-dev-1197-g8081ba9
storage.c File Reference
#include <assert.h>
#include <stdlib.h>
#include "wine/debug.h"
#include "dbghelp_private.h"
Include dependency graph for storage.c:

Go to the source code of this file.

Classes

struct  pool_arena
 
struct  key2index
 

Functions

 WINE_DEFAULT_DEBUG_CHANNEL (dbghelp)
 
void pool_init (struct pool *a, size_t arena_size)
 
void pool_destroy (struct pool *pool)
 
voidpool_alloc (struct pool *pool, size_t len)
 
charpool_strdup (struct pool *pool, const char *str)
 
void vector_init (struct vector *v, unsigned esz, unsigned bucket_sz)
 
unsigned vector_length (const struct vector *v)
 
voidvector_at (const struct vector *v, unsigned pos)
 
voidvector_add (struct vector *v, struct pool *pool)
 
void sparse_array_init (struct sparse_array *sa, unsigned elt_sz, unsigned bucket_sz)
 
static struct key2indexsparse_array_lookup (const struct sparse_array *sa, ULONG_PTR key, unsigned *idx)
 
voidsparse_array_find (const struct sparse_array *sa, ULONG_PTR key)
 
voidsparse_array_add (struct sparse_array *sa, ULONG_PTR key, struct pool *pool)
 
unsigned sparse_array_length (const struct sparse_array *sa)
 
static unsigned hash_table_hash (const char *name, unsigned num_buckets)
 
void hash_table_init (struct pool *pool, struct hash_table *ht, unsigned num_buckets)
 
void hash_table_destroy (struct hash_table *ht)
 
void hash_table_add (struct hash_table *ht, struct hash_table_elt *elt)
 
void hash_table_iter_init (const struct hash_table *ht, struct hash_table_iter *hti, const char *name)
 
voidhash_table_iter_up (struct hash_table_iter *hti)
 

Function Documentation

◆ hash_table_add()

void hash_table_add ( struct hash_table ht,
struct hash_table_elt elt 
)

Definition at line 378 of file storage.c.

379 {
380  unsigned hash = hash_table_hash(elt->name, ht->num_buckets);
381 
382  if (!ht->buckets)
383  {
384  ht->buckets = pool_alloc(ht->pool, ht->num_buckets * sizeof(struct hash_table_bucket));
385  assert(ht->buckets);
386  memset(ht->buckets, 0, ht->num_buckets * sizeof(struct hash_table_bucket));
387  }
388 
389  /* in some cases, we need to get back the symbols of same name in the order
390  * in which they've been inserted. So insert new elements at the end of the list.
391  */
392  if (!ht->buckets[hash].first)
393  {
394  ht->buckets[hash].first = elt;
395  }
396  else
397  {
398  ht->buckets[hash].last->next = elt;
399  }
400  ht->buckets[hash].last = elt;
401  elt->next = NULL;
402  ht->num_elts++;
403 }
#define assert(x)
Definition: debug.h:53
int hash
Definition: main.c:58
static unsigned hash_table_hash(const char *name, unsigned num_buckets)
Definition: storage.c:319
const char * name
smooth NULL
Definition: ftsmooth.c:416
void * pool_alloc(struct pool *pool, size_t len)
Definition: storage.c:89
struct hash_table_elt * next
static const struct newhuff ht[]
Definition: huffman.h:296
Definition: _hash_fun.h:40
#define memset(x, y, z)
Definition: compat.h:39

Referenced by elf_hash_symtab(), macho_stabs_def_cb(), pev_set_value(), symt_add_module_ht(), symt_new_basic(), symt_new_typedef(), symt_new_udt(), and symt_ptr2index().

◆ hash_table_destroy()

void hash_table_destroy ( struct hash_table ht)

Definition at line 342 of file storage.c.

343 {
344 #if defined(USE_STATS)
345  int i;
346  unsigned len;
347  unsigned min = 0xffffffff, max = 0, sq = 0;
348  struct hash_table_elt* elt;
349  double mean, variance;
350 
351  for (i = 0; i < ht->num_buckets; i++)
352  {
353  for (len = 0, elt = ht->buckets[i]; elt; elt = elt->next) len++;
354  if (len < min) min = len;
355  if (len > max) max = len;
356  sq += len * len;
357  }
358  mean = (double)ht->num_elts / ht->num_buckets;
359  variance = (double)sq / ht->num_buckets - mean * mean;
360  FIXME("STATS: elts[num:%-4u size:%u mean:%f] buckets[min:%-4u variance:%+f max:%-4u]\n",
361  ht->num_elts, ht->num_buckets, mean, min, variance, max);
362 
363  for (i = 0; i < ht->num_buckets; i++)
364  {
365  for (len = 0, elt = ht->buckets[i]; elt; elt = elt->next) len++;
366  if (len == max)
367  {
368  FIXME("Longest bucket:\n");
369  for (elt = ht->buckets[i]; elt; elt = elt->next)
370  FIXME("\t%s\n", elt->name);
371  break;
372  }
373 
374  }
375 #endif
376 }
#define max(a, b)
Definition: svc.c:63
GLsizei GLenum const GLvoid GLsizei GLenum GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean const GLdouble const GLfloat const GLint const GLshort const GLbyte const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLdouble const GLfloat const GLfloat const GLint const GLint const GLshort const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort GLenum GLenum GLenum GLfloat GLenum GLint GLenum GLenum GLenum GLfloat GLenum GLenum GLint GLenum GLfloat GLenum GLint GLint GLushort GLenum GLenum GLfloat GLenum GLenum GLint GLfloat const GLubyte GLenum GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLint GLint GLsizei GLsizei GLint GLenum GLenum const GLvoid GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLenum const GLdouble GLenum GLenum const GLfloat GLenum GLenum const GLint GLsizei GLuint GLfloat GLuint GLbitfield GLfloat GLint GLuint GLboolean GLenum GLfloat GLenum GLbitfield GLenum GLfloat GLfloat GLint GLint const GLfloat GLenum GLfloat GLfloat GLint GLint GLfloat GLfloat GLint GLint const GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat const GLdouble const GLfloat const GLdouble const GLfloat GLint i
Definition: glfuncs.h:248
#define FIXME(fmt,...)
Definition: debug.h:111
const char * name
static const char mbstate_t *static wchar_t const char mbstate_t *static const wchar_t int *static double
Definition: string.c:80
GLenum GLsizei len
Definition: glext.h:6722
struct hash_table_elt * next
static const struct newhuff ht[]
Definition: huffman.h:296
#define min(a, b)
Definition: monoChain.cc:55

Referenced by module_remove(), and module_reset_debug_info().

◆ hash_table_hash()

static unsigned hash_table_hash ( const char name,
unsigned  num_buckets 
)
static

Definition at line 319 of file storage.c.

320 {
321  unsigned hash = 0;
322  while (*name)
323  {
324  hash += *name++;
325  hash += (hash << 10);
326  hash ^= (hash >> 6);
327  }
328  hash += (hash << 3);
329  hash ^= (hash >> 11);
330  hash += (hash << 15);
331  return hash % num_buckets;
332 }
Definition: name.c:38
Definition: _hash_fun.h:40

Referenced by hash_table_add(), and hash_table_iter_init().

◆ hash_table_init()

void hash_table_init ( struct pool pool,
struct hash_table ht,
unsigned  num_buckets 
)

Definition at line 334 of file storage.c.

335 {
336  ht->num_elts = 0;
337  ht->num_buckets = num_buckets;
338  ht->pool = pool;
339  ht->buckets = NULL;
340 }
smooth NULL
Definition: ftsmooth.c:416
static const struct newhuff ht[]
Definition: huffman.h:296

Referenced by elf_load_debug_info(), macho_load_debug_info(), module_new(), and pev_init().

◆ hash_table_iter_init()

void hash_table_iter_init ( const struct hash_table ht,
struct hash_table_iter hti,
const char name 
)

Definition at line 405 of file storage.c.

407 {
408  hti->ht = ht;
409  if (name)
410  {
411  hti->last = hash_table_hash(name, ht->num_buckets);
412  hti->index = hti->last - 1;
413  }
414  else
415  {
416  hti->last = ht->num_buckets - 1;
417  hti->index = -1;
418  }
419  hti->element = NULL;
420 }
static unsigned hash_table_hash(const char *name, unsigned num_buckets)
Definition: storage.c:319
smooth NULL
Definition: ftsmooth.c:416
struct hash_table_elt * element
static const struct newhuff ht[]
Definition: huffman.h:296
const struct hash_table * ht
Definition: name.c:38

Referenced by codeview_add_type_struct(), elf_finish_stabs_info(), elf_lookup_symtab(), elf_new_public_symbols(), elf_new_wine_thunks(), find_name(), macho_finish_stabs(), pe_locate_with_coff_symbol_table(), pev_get_val(), pev_set_value(), SymEnumLines(), symt_enum_module(), symt_find_type_by_name(), and symt_ptr2index().

◆ hash_table_iter_up()

void* hash_table_iter_up ( struct hash_table_iter hti)

Definition at line 422 of file storage.c.

423 {
424  if (!hti->ht->buckets) return NULL;
425 
426  if (hti->element) hti->element = hti->element->next;
427  while (!hti->element && hti->index < hti->last)
428  hti->element = hti->ht->buckets[++hti->index].first;
429  return hti->element;
430 }
smooth NULL
Definition: ftsmooth.c:416
struct hash_table_elt * element
const struct hash_table * ht

Referenced by codeview_add_type_struct(), elf_finish_stabs_info(), elf_lookup_symtab(), elf_new_public_symbols(), elf_new_wine_thunks(), find_name(), macho_finish_stabs(), pe_locate_with_coff_symbol_table(), pev_get_val(), pev_set_value(), SymEnumLines(), symt_enum_module(), symt_find_type_by_name(), and symt_ptr2index().

◆ pool_alloc()

void* pool_alloc ( struct pool pool,
size_t  len 
)

Definition at line 89 of file storage.c.

90 {
91  struct pool_arena* arena;
92  void* ret;
93  size_t size;
94 
95  len = (len + 3) & ~3; /* round up size on DWORD boundary */
96 
98  {
99  if (arena->end - arena->current >= len)
100  {
101  ret = arena->current;
102  arena->current += len;
103  if (arena->current + 16 >= arena->end)
104  {
105  list_remove( &arena->entry );
106  list_add_tail( &pool->arena_full, &arena->entry );
107  }
108  return ret;
109  }
110  }
111 
112  size = max( pool->arena_size, len );
113  arena = HeapAlloc(GetProcessHeap(), 0, size + sizeof(struct pool_arena));
114  if (!arena) return NULL;
115 
116  ret = arena + 1;
117  arena->current = (char*)ret + len;
118  arena->end = (char*)ret + size;
119  if (arena->current + 16 >= arena->end)
120  list_add_tail( &pool->arena_full, &arena->entry );
121  else
122  list_add_head( &pool->arena_list, &arena->entry );
123  return ret;
124 }
struct list arena_list
#define max(a, b)
Definition: svc.c:63
__WINE_SERVER_LIST_INLINE void list_add_head(struct list *list, struct list *elem)
Definition: list.h:96
char * current
Definition: storage.c:39
size_t arena_size
__WINE_SERVER_LIST_INLINE void list_add_tail(struct list *list, struct list *elem)
Definition: list.h:102
#define LIST_FOR_EACH_ENTRY(elem, list, type, field)
Definition: list.h:198
smooth NULL
Definition: ftsmooth.c:416
char * end
Definition: storage.c:40
__WINE_SERVER_LIST_INLINE void list_remove(struct list *elem)
Definition: list.h:108
GLsizeiptr size
Definition: glext.h:5919
struct list arena_full
#define GetProcessHeap()
Definition: compat.h:484
PVOID WINAPI HeapAlloc(HANDLE, DWORD, SIZE_T)
int ret
uint32_t entry
Definition: isohybrid.c:63
GLenum GLsizei len
Definition: glext.h:6722
struct list entry
Definition: storage.c:38

Referenced by dwarf2_compute_location_attr(), dwarf2_get_cpp_name(), dwarf2_parse_abbrev_set(), dwarf2_parse_line_numbers(), dwarf2_parse_variable(), dwarf2_read_one_debug_info(), elf_hash_symtab(), hash_table_add(), macho_stabs_def_cb(), pev_set_value(), pool_strdup(), source_new(), symt_add_enum_element(), symt_add_func_local(), symt_add_function_point(), symt_add_function_signature_parameter(), symt_add_udt_element(), symt_new_array(), symt_new_basic(), symt_new_compiland(), symt_new_constant(), symt_new_enum(), symt_new_function(), symt_new_function_signature(), symt_new_global_variable(), symt_new_label(), symt_new_pointer(), symt_new_public(), symt_new_thunk(), symt_new_typedef(), symt_new_udt(), symt_open_func_block(), symt_ptr2index(), and vector_add().

◆ pool_destroy()

void pool_destroy ( struct pool pool)

Definition at line 50 of file storage.c.

51 {
52  struct pool_arena* arena;
53  struct pool_arena* next;
54 
55 #ifdef USE_STATS
56  size_t alloc, used, num;
57 
58  alloc = used = num = 0;
60  {
61  alloc += arena->end - (char *)arena;
62  used += arena->current - (char*)arena;
63  num++;
64  }
66  {
67  alloc += arena->end - (char *)arena;
68  used += arena->current - (char*)arena;
69  num++;
70  }
71  if (alloc == 0) alloc = 1; /* avoid division by zero */
72  FIXME("STATS: pool %p has allocated %u kbytes, used %u kbytes in %u arenas, non-allocation ratio: %.2f%%\n",
73  pool, (unsigned)(alloc >> 10), (unsigned)(used >> 10), (unsigned)num,
74  100.0 - (float)used / (float)alloc * 100.0);
75 #endif
76 
78  {
79  list_remove( &arena->entry );
80  HeapFree(GetProcessHeap(), 0, arena);
81  }
83  {
84  list_remove( &arena->entry );
85  HeapFree(GetProcessHeap(), 0, arena);
86  }
87 }
struct list arena_list
char * current
Definition: storage.c:39
#define LIST_FOR_EACH_ENTRY(elem, list, type, field)
Definition: list.h:198
#define FIXME(fmt,...)
Definition: debug.h:111
char * end
Definition: storage.c:40
c used
Definition: write.c:2857
__WINE_SERVER_LIST_INLINE void list_remove(struct list *elem)
Definition: list.h:108
struct list arena_full
#define GetProcessHeap()
Definition: compat.h:484
GLuint GLuint num
Definition: glext.h:9618
uint32_t entry
Definition: isohybrid.c:63
static unsigned __int64 next
Definition: rand_nt.c:6
#define LIST_FOR_EACH_ENTRY_SAFE(cursor, cursor2, list, type, field)
Definition: list.h:204
#define alloc
Definition: rosglue.h:13
#define HeapFree(x, y, z)
Definition: compat.h:483
struct list entry
Definition: storage.c:38

Referenced by dwarf2_parse_compilation_unit(), elf_load_debug_info(), macho_load_debug_info(), module_remove(), pev_free(), and rsym_parse().

◆ pool_init()

void pool_init ( struct pool a,
size_t  arena_size 
)

Definition at line 43 of file storage.c.

44 {
45  list_init( &a->arena_list );
46  list_init( &a->arena_full );
47  a->arena_size = arena_size;
48 }
__WINE_SERVER_LIST_INLINE void list_init(struct list *list)
Definition: list.h:149
GLboolean GLboolean GLboolean GLboolean a
Definition: glext.h:6204

Referenced by dwarf2_parse_compilation_unit(), elf_load_debug_info(), macho_load_debug_info(), module_new(), pev_init(), and rsym_parse().

◆ pool_strdup()

char* pool_strdup ( struct pool pool,
const char str 
)

Definition at line 126 of file storage.c.

127 {
128  char* ret;
129  if ((ret = pool_alloc(pool, strlen(str) + 1))) strcpy(ret, str);
130  return ret;
131 }
ACPI_SIZE strlen(const char *String)
Definition: utclib.c:269
const WCHAR * str
void * pool_alloc(struct pool *pool, size_t len)
Definition: storage.c:89
int ret
char * strcpy(char *DstString, const char *SrcString)
Definition: utclib.c:388

Referenced by dwarf2_parse_variable(), macho_stabs_def_cb(), pev_push(), pev_set_value(), symt_add_enum_element(), symt_add_func_local(), symt_add_function_point(), symt_add_udt_element(), symt_new_basic(), symt_new_constant(), symt_new_enum(), symt_new_function(), symt_new_global_variable(), symt_new_label(), symt_new_public(), symt_new_thunk(), symt_new_typedef(), symt_new_udt(), and symt_ptr2index().

◆ sparse_array_add()

void* sparse_array_add ( struct sparse_array sa,
ULONG_PTR  key,
struct pool pool 
)

Definition at line 281 of file storage.c.

283 {
284  unsigned idx, i;
285  struct key2index* pk2i;
286  struct key2index* to;
287 
288  pk2i = sparse_array_lookup(sa, key, &idx);
289  if (pk2i && pk2i->key == key)
290  {
291  FIXME("re-adding an existing key\n");
292  return NULL;
293  }
294  to = vector_add(&sa->key2index, pool);
295  if (pk2i)
296  {
297  /* we need to shift vector's content... */
298  /* let's do it brute force... (FIXME) */
299  assert(sa->key2index.num_elts >= 2);
300  for (i = sa->key2index.num_elts - 1; i > idx; i--)
301  {
302  pk2i = vector_at(&sa->key2index, i - 1);
303  *to = *pk2i;
304  to = pk2i;
305  }
306  }
307 
308  to->key = key;
309  to->index = sa->elements.num_elts;
310 
311  return vector_add(&sa->elements, pool);
312 }
void * vector_add(struct vector *v, struct pool *pool)
Definition: storage.c:171
ULONG_PTR key
Definition: storage.c:209
unsigned index
Definition: storage.c:210
#define assert(x)
Definition: debug.h:53
GLsizei GLenum const GLvoid GLsizei GLenum GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean const GLdouble const GLfloat const GLint const GLshort const GLbyte const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLdouble const GLfloat const GLfloat const GLint const GLint const GLshort const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort GLenum GLenum GLenum GLfloat GLenum GLint GLenum GLenum GLenum GLfloat GLenum GLenum GLint GLenum GLfloat GLenum GLint GLint GLushort GLenum GLenum GLfloat GLenum GLenum GLint GLfloat const GLubyte GLenum GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLint GLint GLsizei GLsizei GLint GLenum GLenum const GLvoid GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLenum const GLdouble GLenum GLenum const GLfloat GLenum GLenum const GLint GLsizei GLuint GLfloat GLuint GLbitfield GLfloat GLint GLuint GLboolean GLenum GLfloat GLenum GLbitfield GLenum GLfloat GLfloat GLint GLint const GLfloat GLenum GLfloat GLfloat GLint GLint GLfloat GLfloat GLint GLint const GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat const GLdouble const GLfloat const GLdouble const GLfloat GLint i
Definition: glfuncs.h:248
void * vector_at(const struct vector *v, unsigned pos)
Definition: storage.c:162
#define FIXME(fmt,...)
Definition: debug.h:111
unsigned int idx
Definition: utils.c:41
static struct key2index * sparse_array_lookup(const struct sparse_array *sa, ULONG_PTR key, unsigned *idx)
Definition: storage.c:224
smooth NULL
Definition: ftsmooth.c:416
HKEY key
Definition: reg.c:42
static struct sockaddr_in sa
Definition: adnsresfilter.c:69
Definition: path.c:41

Referenced by dwarf2_parse_abbrev_set(), dwarf2_read_one_debug_info(), and rsym_parse().

◆ sparse_array_find()

void* sparse_array_find ( const struct sparse_array sa,
ULONG_PTR  key 
)

Definition at line 271 of file storage.c.

272 {
273  unsigned idx;
274  struct key2index* pk2i;
275 
276  if ((pk2i = sparse_array_lookup(sa, key, &idx)) && pk2i->key == key)
277  return vector_at(&sa->elements, pk2i->index);
278  return NULL;
279 }
ULONG_PTR key
Definition: storage.c:209
unsigned index
Definition: storage.c:210
void * vector_at(const struct vector *v, unsigned pos)
Definition: storage.c:162
unsigned int idx
Definition: utils.c:41
static struct key2index * sparse_array_lookup(const struct sparse_array *sa, ULONG_PTR key, unsigned *idx)
Definition: storage.c:224
smooth NULL
Definition: ftsmooth.c:416
static struct sockaddr_in sa
Definition: adnsresfilter.c:69
Definition: path.c:41

Referenced by dwarf2_abbrev_table_find_entry(), dwarf2_find_attribute(), dwarf2_get_cpp_name(), dwarf2_get_di_children(), dwarf2_lookup_type(), and rsym_parse().

◆ sparse_array_init()

void sparse_array_init ( struct sparse_array sa,
unsigned  elt_sz,
unsigned  bucket_sz 
)

Definition at line 213 of file storage.c.

214 {
215  vector_init(&sa->key2index, sizeof(struct key2index), bucket_sz);
216  vector_init(&sa->elements, elt_sz, bucket_sz);
217 }
void vector_init(struct vector *v, unsigned esz, unsigned bucket_sz)
Definition: storage.c:133
static struct sockaddr_in sa
Definition: adnsresfilter.c:69

Referenced by dwarf2_parse_abbrev_set(), dwarf2_parse_compilation_unit(), and rsym_parse().

◆ sparse_array_length()

unsigned sparse_array_length ( const struct sparse_array sa)

Definition at line 314 of file storage.c.

315 {
316  return sa->elements.num_elts;
317 }
static struct sockaddr_in sa
Definition: adnsresfilter.c:69

Referenced by dwarf2_parse_abbrev_set().

◆ sparse_array_lookup()

static struct key2index* sparse_array_lookup ( const struct sparse_array sa,
ULONG_PTR  key,
unsigned idx 
)
static

Definition at line 224 of file storage.c.

226 {
227  struct key2index* pk2i;
228  unsigned low, high;
229 
230  if (!sa->elements.num_elts)
231  {
232  *idx = 0;
233  return NULL;
234  }
235  high = sa->elements.num_elts;
236  pk2i = vector_at(&sa->key2index, high - 1);
237  if (pk2i->key < key)
238  {
239  *idx = high;
240  return NULL;
241  }
242  if (pk2i->key == key)
243  {
244  *idx = high - 1;
245  return pk2i;
246  }
247  low = 0;
248  pk2i = vector_at(&sa->key2index, low);
249  if (pk2i->key >= key)
250  {
251  *idx = 0;
252  return pk2i;
253  }
254  /* now we have: sa(lowest key) < key < sa(highest key) */
255  while (low < high)
256  {
257  *idx = (low + high) / 2;
258  pk2i = vector_at(&sa->key2index, *idx);
259  if (pk2i->key > key) high = *idx;
260  else if (pk2i->key < key) low = *idx + 1;
261  else return pk2i;
262  }
263  /* binary search could return exact item, we search for highest one
264  * below the key
265  */
266  if (pk2i->key < key)
267  pk2i = vector_at(&sa->key2index, ++(*idx));
268  return pk2i;
269 }
ULONG_PTR key
Definition: storage.c:209
void * vector_at(const struct vector *v, unsigned pos)
Definition: storage.c:162
unsigned int idx
Definition: utils.c:41
smooth NULL
Definition: ftsmooth.c:416
static struct sockaddr_in sa
Definition: adnsresfilter.c:69
Definition: path.c:41

Referenced by sparse_array_add(), and sparse_array_find().

◆ vector_add()

void* vector_add ( struct vector v,
struct pool pool 
)

Definition at line 171 of file storage.c.

172 {
173  unsigned ncurr = v->num_elts++;
174 
175  /* check that we don't wrap around */
176  assert(v->num_elts > ncurr);
177  if (ncurr == (v->num_buckets << v->shift))
178  {
179  if(v->num_buckets == v->buckets_allocated)
180  {
181  /* Double the bucket cache, so it scales well with big vectors.*/
182  unsigned new_reserved;
183  void* new;
184 
185  new_reserved = 2*v->buckets_allocated;
186  if(new_reserved == 0) new_reserved = 1;
187 
188  /* Don't even try to resize memory.
189  Pool datastructure is very inefficient with reallocs. */
190  new = pool_alloc(pool, new_reserved * sizeof(void*));
191  memcpy(new, v->buckets, v->buckets_allocated * sizeof(void*));
192  v->buckets = new;
193  v->buckets_allocated = new_reserved;
194  }
195  v->buckets[v->num_buckets] = pool_alloc(pool, v->elt_size << v->shift);
196  return v->buckets[v->num_buckets++];
197  }
198  return vector_at(v, ncurr);
199 }
#define assert(x)
Definition: debug.h:53
void * vector_at(const struct vector *v, unsigned pos)
Definition: storage.c:162
void * pool_alloc(struct pool *pool, size_t len)
Definition: storage.c:89
#define memcpy(s1, s2, n)
Definition: mkisofs.h:878
const GLdouble * v
Definition: gl.h:2040

Referenced by dwarf2_parse_line_numbers(), dwarf2_read_one_debug_info(), pev_push(), sparse_array_add(), symt_add_enum_element(), symt_add_func_line(), symt_add_func_local(), symt_add_function_point(), symt_add_function_signature_parameter(), symt_add_type(), symt_add_udt_element(), symt_new_constant(), symt_new_function(), symt_new_global_variable(), symt_new_label(), symt_new_public(), symt_new_thunk(), symt_open_func_block(), and symt_ptr2index().

◆ vector_at()

◆ vector_init()

void vector_init ( struct vector v,
unsigned  esz,
unsigned  bucket_sz 
)

Definition at line 133 of file storage.c.

134 {
135  v->buckets = NULL;
136  /* align size on DWORD boundaries */
137  v->elt_size = (esz + 3) & ~3;
138  switch (bucket_sz)
139  {
140  case 2: v->shift = 1; break;
141  case 4: v->shift = 2; break;
142  case 8: v->shift = 3; break;
143  case 16: v->shift = 4; break;
144  case 32: v->shift = 5; break;
145  case 64: v->shift = 6; break;
146  case 128: v->shift = 7; break;
147  case 256: v->shift = 8; break;
148  case 512: v->shift = 9; break;
149  case 1024: v->shift = 10; break;
150  default: assert(0);
151  }
152  v->num_buckets = 0;
153  v->buckets_allocated = 0;
154  v->num_elts = 0;
155 }
#define assert(x)
Definition: debug.h:53
smooth NULL
Definition: ftsmooth.c:416
const GLdouble * v
Definition: gl.h:2040

Referenced by dwarf2_parse_line_numbers(), dwarf2_read_one_debug_info(), module_new(), pev_init(), sparse_array_init(), symt_new_compiland(), symt_new_enum(), symt_new_function(), symt_new_function_signature(), symt_new_udt(), and symt_open_func_block().

◆ vector_length()

◆ WINE_DEFAULT_DEBUG_CHANNEL()

WINE_DEFAULT_DEBUG_CHANNEL ( dbghelp  )