/*

   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 <stdlib.h>

#include <string.h>

#include <strings.h>

#include <ctype.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;

}