Back to index

glibc  2.9
Classes | Functions
inline-hashtab.h File Reference

Go to the source code of this file.

Classes

struct  hashtab

Functions

void weak_function free (void *ptr)
static unsigned long higher_prime_number (unsigned long n)
static struct hashtabhtab_create (void)
static void htab_delete (struct hashtab *htab)
static void ** find_empty_slot_for_expand (struct hashtab *htab, int hash)
static int htab_expand (struct hashtab *htab, int(*hash_fn)(void *))
static void ** htab_find_slot (struct hashtab *htab, void *ptr, int insert, int(*hash_fn)(void *), int(*eq_fn)(void *, void *))

Function Documentation

static void** find_empty_slot_for_expand ( struct hashtab htab,
int  hash 
) [inline, static]

Definition at line 160 of file inline-hashtab.h.

{
  size_t size = htab->size;
  unsigned int index = hash % size;
  void **slot = htab->entries + index;
  int hash2;

  if (! *slot)
    return slot;

  hash2 = 1 + hash % (size - 2);
  for (;;)
    {
      index += hash2;
      if (index >= size)
       index -= size;

      slot = htab->entries + index;
      if (! *slot)
       return slot;
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

void weak_function free ( void *  ptr)

Definition at line 130 of file dl-minimal.c.

{
  /* We can free only the last block allocated.  */
  if (ptr == alloc_last_block)
    {
      /* Since this is rare, we clear the freed block here
        so that calloc can presume malloc returns cleared memory.  */
      memset (alloc_last_block, '\0', alloc_ptr - alloc_last_block);
      alloc_ptr = alloc_last_block;
    }
}
static unsigned long higher_prime_number ( unsigned long  n) [inline, static]

Definition at line 34 of file inline-hashtab.h.

{
  /* These are primes that are near, but slightly smaller than, a
     power of two.  */
  static const uint32_t primes[] = {
    UINT32_C (7),
    UINT32_C (13),
    UINT32_C (31),
    UINT32_C (61),
    UINT32_C (127),
    UINT32_C (251),
    UINT32_C (509),
    UINT32_C (1021),
    UINT32_C (2039),
    UINT32_C (4093),
    UINT32_C (8191),
    UINT32_C (16381),
    UINT32_C (32749),
    UINT32_C (65521),
    UINT32_C (131071),
    UINT32_C (262139),
    UINT32_C (524287),
    UINT32_C (1048573),
    UINT32_C (2097143),
    UINT32_C (4194301),
    UINT32_C (8388593),
    UINT32_C (16777213),
    UINT32_C (33554393),
    UINT32_C (67108859),
    UINT32_C (134217689),
    UINT32_C (268435399),
    UINT32_C (536870909),
    UINT32_C (1073741789),
    UINT32_C (2147483647),
                                   /* 4294967291L */
    UINT32_C (2147483647) + UINT32_C (2147483644)
  };

  const uint32_t *low = &primes[0];
  const uint32_t *high = &primes[sizeof (primes) / sizeof (primes[0])];

  while (low != high)
    {
      const uint32_t *mid = low + (high - low) / 2;
      if (n > *mid)
       low = mid + 1;
      else
       high = mid;
    }

#if 0
  /* If we've run out of primes, abort.  */
  if (n > *low)
    {
      fprintf (stderr, "Cannot find prime bigger than %lu\n", n);
      abort ();
    }
#endif

  return *low;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static struct hashtab* htab_create ( void  ) [static, read]

Definition at line 114 of file inline-hashtab.h.

{
  struct hashtab *ht = malloc (sizeof (struct hashtab));

  if (! ht)
    return NULL;
  ht->size = 3;
  ht->entries = malloc (sizeof (void *) * ht->size);
  ht->free = free;
  if (! ht->entries)
    {
      if (ht->free)
       ht->free (ht);
      return NULL;
    }

  ht->n_elements = 0;

  memset (ht->entries, 0, sizeof (void *) * ht->size);

  return ht;
}
static void htab_delete ( struct hashtab htab) [inline, static]

Definition at line 140 of file inline-hashtab.h.

{
  int i;

  for (i = htab->size - 1; i >= 0; i--)
    free (htab->entries[i]);

  if (htab->free)
    htab->free (htab->entries);
  free (htab);
}

Here is the caller graph for this function:

static int htab_expand ( struct hashtab htab,
int(*)(void *)  hash_fn 
) [inline, static]

Definition at line 192 of file inline-hashtab.h.

{
  void **oentries;
  void **olimit;
  void **p;
  void **nentries;
  size_t nsize;

  oentries = htab->entries;
  olimit = oentries + htab->size;

  /* Resize only when table after removal of unused elements is either
     too full or too empty.  */
  if (htab->n_elements * 2 > htab->size)
    nsize = higher_prime_number (htab->n_elements * 2);
  else
    nsize = htab->size;

  nentries = malloc (sizeof (void *) * nsize);
  memset (nentries, 0, sizeof (void *) * nsize);
  if (nentries == NULL)
    return 0;
  htab->entries = nentries;
  htab->size = nsize;

  p = oentries;
  do
    {
      if (*p)
       *find_empty_slot_for_expand (htab, hash_fn (*p))
         = *p;

      p++;
    }
  while (p < olimit);

  /* Without recording the free corresponding to the malloc used to
     allocate the table, we couldn't tell whether this was allocated
     by the malloc() built into ld.so or the one in the main
     executable or libc.  Calling free() for something that was
     allocated by the early malloc(), rather than the final run-time
     malloc() could do Very Bad Things (TM).  We will waste memory
     allocated early as long as there's no corresponding free(), but
     this isn't so much memory as to be significant.  */

  if (htab->free)
    htab->free (oentries);

  /* Use the free() corresponding to the malloc() above to free this
     up.  */
  htab->free = free;

  return 1;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static void** htab_find_slot ( struct hashtab htab,
void *  ptr,
int  insert,
int(*)(void *)  hash_fn,
int(*)(void *, void *)  eq_fn 
) [inline, static]

Definition at line 256 of file inline-hashtab.h.

{
  unsigned int index;
  int hash, hash2;
  size_t size;
  void **entry;

  if (htab->size * 3 <= htab->n_elements * 4
      && htab_expand (htab, hash_fn) == 0)
    return NULL;

  hash = hash_fn (ptr);

  size = htab->size;
  index = hash % size;

  entry = &htab->entries[index];
  if (!*entry)
    goto empty_entry;
  else if (eq_fn (*entry, ptr))
    return entry;

  hash2 = 1 + hash % (size - 2);
  for (;;)
    {
      index += hash2;
      if (index >= size)
       index -= size;

      entry = &htab->entries[index];
      if (!*entry)
       goto empty_entry;
      else if (eq_fn (*entry, ptr))
       return entry;
    }

 empty_entry:
  if (!insert)
    return NULL;

  htab->n_elements++;
  return entry;
}

Here is the call graph for this function: