text: /*
     dict.c - dictionary functions
     This file is part of the nss-pam-ldapd library.
  
     Copyright (C) 2007, 2008, 2009, 2010, 2012, 2013 Arthur de Jong
  
     This library is free software; you can redistribute it and/or
     modify it under the terms of the GNU Lesser General Public
     License as published by the Free Software Foundation; either
     version 2.1 of the License, or (at your option) any later version.
  
     This library is distributed in the hope that it will be useful,
     but WITHOUT ANY WARRANTY; without even the implied warranty of
     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
     Lesser General Public License for more details.
  
     You should have received a copy of the GNU Lesser General Public
     License along with this library; if not, write to the Free Software
     Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
     02110-1301 USA
  */
  
  #include "config.h"
  
  #include <ctype.h>
  #include <stdlib.h>
  #include <string.h>
  #include <strings.h>
  #ifdef HAVE_STDINT_H
  #include <stdint.h>
  #endif /* HAVE_STDINT_H */
  
  #include "dict.h"
  
  /*
     This module uses a hashtable to store its key to value mappings. The
     structure is basically as follows:
  
     [struct dictionary]
       \- holds an array of pointers to a linked list of [struct dict_entry]
            \- each entry has a key/value mapping
  
     The hashmap can be resized when the total number of elements in the hashmap
     exceeds a certain load factor.
  
     All the keys are copied in a separate linked list of buffers where each new
     buffer that is allocated is larger than the previous one. The first buffer
     in the linked list is always the current one.
  */
  
  /* an entry stores one key/value pair */
  struct dict_entry
  {
      uint32_t hash;   /* used for quick matching and rehashing */
      const char* key; /* a reference to a copy of the key */
      void* value;     /* the stored value */
      struct dict_entry* next;
  };
  
  /* the initial size of the hashtable */
  #define DICT_INITSIZE 7
  
  /* load factor at which point to grow hashtable */
  #define DICT_LOADPERCENTAGE 400
  
  /* the dictionary is a hashtable */
  struct dictionary
  {
      int size;                  /* size of the hashtable */
      int num;                   /* total number of keys stored */
      struct dict_entry** table; /* the hashtable */
  };
  
  /* Simple hash function that computes the hash value of a string. */
  static uint32_t stringhash(const char* str)
  {
      uint32_t hash = 5381;
      uint32_t c;
      while ((c = *str++) != '\0')
          hash = 33 * hash + c;
      return hash;
  }
  
  /* Grow the hashtable. */
  static void growhashtable(DICT* dict)
  {
      int i;
      int newsize;
      struct dict_entry** newtable;
      struct dict_entry *entry, *tmp;
      newsize = dict->size * 3 + 1;
      /* allocate room for new hashtable */
      newtable =
          (struct dict_entry**)malloc(newsize * sizeof(struct dict_entry*));
      if (newtable == NULL)
          return; /* allocating memory failed continue to fill the existing table
                   */
      /* clear new table */
      for (i = 0; i < newsize; i++)
          newtable[i] = NULL;
      /* copy old hashtable into new table */
      for (i = 0; i < dict->size; i++)
      {
          /* go over elements in linked list */
          entry = dict->table[i];
          while (entry != NULL)
          {
              tmp = entry;
              entry = entry->next;
              /* put in new position */
              tmp->next = newtable[tmp->hash % newsize];
              newtable[tmp->hash % newsize] = tmp;
          }
      }
      /* free the old hashtable */
      free(dict->table);
      /* put new hashtable in place */
      dict->size = newsize;
      dict->table = newtable;
  }
  
  DICT* dict_new(void)
  {
      struct dictionary* dict;
      int i;
      /* allocate room for dictionary information */
      dict = (struct dictionary*)malloc(sizeof(struct dictionary));
      if (dict == NULL)
          return NULL;
      dict->size = DICT_INITSIZE;
      dict->num = 0;
      /* allocate initial hashtable */
      dict->table =
          (struct dict_entry**)malloc(DICT_INITSIZE * sizeof(struct dict_entry*));
      if (dict->table == NULL)
      {
          free(dict);
          return NULL;
      }
      /* clear the hashtable */
      for (i = 0; i < DICT_INITSIZE; i++)
          dict->table[i] = NULL;
      /* we're done */
      return dict;
  }
  
  void dict_free(DICT* dict)
  {
      struct dict_entry *entry, *etmp;
      int i;
      /* free hashtable entries */
      for (i = 0; i < dict->size; i++)
      {
          entry = dict->table[i];
          while (entry != NULL)
          {
              etmp = entry;
              entry = entry->next;
              free(etmp);
          }
      }
      /* free the hashtable */
      free(dict->table);
      /* free dictionary struct itself */
      free(dict);
  }
  
  void* dict_get(DICT* dict, const char* key)
  {
      uint32_t hash;
      struct dict_entry* entry;
      /* calculate the hash */
      hash = stringhash(key);
      /* loop over the linked list in the hashtable */
      for (entry = dict->table[hash % dict->size]; entry != NULL;
           entry = entry->next)
      {
          if ((entry->hash == hash) && (strcmp(entry->key, key) == 0))
              return entry->value;
      }
      /* no matches found */
      return NULL;
  }
  
  const char* dict_getany(DICT* dict)
  {
      int i;
      /* loop over the linked list in the hashtable */
      for (i = 0; i < dict->size; i++)
          if (dict->table[i])
              return dict->table[i]->key;
      /* no matches found */
      return NULL;
  }
  
  int dict_put(DICT* dict, const char* key, void* value)
  {
      uint32_t hash;
      int l;
      char* buf;
      int idx;
      struct dict_entry *entry, *prev;
      /* check if we should grow the hashtable */
      if (dict->num >= ((dict->size * DICT_LOADPERCENTAGE) / 100))
          growhashtable(dict);
      /* calculate the hash and position in the hashtable */
      hash = stringhash(key);
      idx = hash % dict->size;
      /* check if the entry is already present */
      for (entry = dict->table[idx], prev = NULL; entry != NULL;
           prev = entry, entry = entry->next)
      {
          if ((entry->hash == hash) && (strcmp(entry->key, key) == 0))
          {
              /* check if we should unset the entry */
              if (value == NULL)
              {
                  /* remove from linked list */
                  if (prev == NULL)
                      dict->table[idx] = entry->next;
                  else
                      prev->next = entry->next;
                  /* free entry memory and register removal */
                  free(entry);
                  dict->num--;
                  return 0;
              }
              /* just set the new value */
              entry->value = value;
              return 0;
          }
      }
      /* if entry should be unset we're done */
      if (value == NULL)
          return 0;
      /* entry is not present, make new entry */
      l = strlen(key) + 1;
      buf = (char*)malloc(sizeof(struct dict_entry) + l);
      if (buf == NULL)
          return -1;
      entry = (struct dict_entry*)(void*)buf;
      buf += sizeof(struct dict_entry);
      strcpy(buf, key);
      entry->hash = hash;
      entry->key = buf;
      entry->value = value;
      /* insert into hashtable/linked list */
      entry->next = dict->table[idx];
      dict->table[idx] = entry;
      /* increment number of stored items */
      dict->num++;
      return 0;
  }
  
  const char** dict_keys(DICT* dict)
  {
      int i;
      struct dict_entry* entry;
      char* buf;
      const char** values;
      size_t sz;
      int num;
      /* figure out how much memory to allocate */
      num = 0;
      sz = 0;
      for (i = 0; i < dict->size; i++)
      {
          entry = dict->table[i];
          while (entry != NULL)
          {
              num++;
              sz += strlen(entry->key) + 1;
              entry = entry->next;
          }
      }
      /* allocate the needed memory */
      buf = (char*)malloc((num + 1) * sizeof(char*) + sz);
      if (buf == NULL)
          return NULL;
      values = (const char**)(void*)buf;
      buf += (num + 1) * sizeof(char*);
      /* fill the array with the keys */
      num = 0;
      for (i = 0; i < dict->size; i++)
      {
          entry = dict->table[i];
          while (entry != NULL)
          {
              strcpy(buf, entry->key);
              values[num++] = buf;
              buf += strlen(buf) + 1;
              entry = entry->next;
          }
      }
      values[num] = NULL;
      /* done */
      return values;
  }
  