Back to index

glibc  2.9
Classes | Typedefs | Functions
hsearch_r.c File Reference
#include <errno.h>
#include <malloc.h>
#include <string.h>
#include <search.h>

Go to the source code of this file.

Classes

struct  _ENTRY

Typedefs

typedef struct _ENTRY _ENTRY

Functions

static int isprime (unsigned int number)
int hcreate_r (size_t nel, struct hsearch_data *htab)
 libc_hidden_def (hcreate_r)
 libc_hidden_def (hdestroy_r)

Class Documentation

struct _ENTRY

Definition at line 34 of file hsearch_r.c.

Collaboration diagram for _ENTRY:
Class Members
ENTRY entry
unsigned int used

Typedef Documentation

typedef struct _ENTRY _ENTRY

Function Documentation

int hcreate_r ( size_t  nel,
struct hsearch_data htab 
)

Definition at line 67 of file hsearch_r.c.

{
  /* Test for correct arguments.  */
  if (htab == NULL)
    {
      __set_errno (EINVAL);
      return 0;
    }

  /* There is still another table active. Return with error. */
  if (htab->table != NULL)
    return 0;

  /* Change nel to the first prime number not smaller as nel. */
  nel |= 1;      /* make odd */
  while (!isprime (nel))
    nel += 2;

  htab->size = nel;
  htab->filled = 0;

  /* allocate memory and zero out */
  htab->table = (_ENTRY *) calloc (htab->size + 1, sizeof (_ENTRY));
  if (htab->table == NULL)
    return 0;

  /* everything went alright */
  return 1;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static int isprime ( unsigned int  number) [static]

Definition at line 48 of file hsearch_r.c.

{
  /* no even number will be passed */
  unsigned int div = 3;

  while (div * div < number && number % div != 0)
    div += 2;

  return number % div != 0;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Definition at line 98 of file hsearch_r.c.

{
  /* Test for correct arguments.  */
  if (htab == NULL)
    {
      __set_errno (EINVAL);
      return;
    }

  /* Free used memory.  */
  free (htab->table);

  /* the sign for an existing table is an value != NULL in htable */
  htab->table = NULL;
}
libc_hidden_def ( hdestroy_r  )

Definition at line 120 of file hsearch_r.c.

{
  unsigned int hval;
  unsigned int count;
  unsigned int len = strlen (item.key);
  unsigned int idx;

  /* Compute an value for the given string. Perhaps use a better method. */
  hval = len;
  count = len;
  while (count-- > 0)
    {
      hval <<= 4;
      hval += item.key[count];
    }

  /* First hash function: simply take the modul but prevent zero. */
  idx = hval % htab->size + 1;

  if (htab->table[idx].used)
    {
      /* Further action might be required according to the action value. */
      if (htab->table[idx].used == hval
         && strcmp (item.key, htab->table[idx].entry.key) == 0)
       {
         *retval = &htab->table[idx].entry;
         return 1;
       }

      /* Second hash function, as suggested in [Knuth] */
      unsigned int hval2 = 1 + hval % (htab->size - 2);
      unsigned int first_idx = idx;

      do
       {
         /* Because SIZE is prime this guarantees to step through all
             available indeces.  */
          if (idx <= hval2)
           idx = htab->size + idx - hval2;
         else
           idx -= hval2;

         /* If we visited all entries leave the loop unsuccessfully.  */
         if (idx == first_idx)
           break;

            /* If entry is found use it. */
          if (htab->table[idx].used == hval
             && strcmp (item.key, htab->table[idx].entry.key) == 0)
           {
             *retval = &htab->table[idx].entry;
             return 1;
           }
       }
      while (htab->table[idx].used);
    }

  /* An empty bucket has been found. */
  if (action == ENTER)
    {
      /* If table is full and another entry should be entered return
        with error.  */
      if (htab->filled == htab->size)
       {
         __set_errno (ENOMEM);
         *retval = NULL;
         return 0;
       }

      htab->table[idx].used  = hval;
      htab->table[idx].entry = item;

      ++htab->filled;

      *retval = &htab->table[idx].entry;
      return 1;
    }

  __set_errno (ESRCH);
  *retval = NULL;
  return 0;
}

Here is the call graph for this function: