/*
 * hashtable.c
 *
 * Hash table handling for strings
 *
 * © 1994-1998 Straylight
 */

/*----- Licensing note ----------------------------------------------------*
 *
 * This file is part of Straylight's Dynamic Linking System (SDLS)
 *
 * SDLS is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2, or (at your option)
 * any later version.
 *
 * SDLS 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 General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with SDLS.  If not, write to the Free Software Foundation,
 * 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "hashtable.h"
#include "crc32.h"

/*----- Constants ---------------------------------------------------------*/

#define hash__SIZE 512			/* A respectable size table	*/
					/* Note: must be power of 2	*/

/*----- Some good ol' data structures -------------------------------------*/

typedef struct hash__link
{
  struct hash__link *next;		/* Link in hash table bucket 	*/
  struct hash__link *left;		/* Link in ordinal tree		*/
  struct hash__link *right;		/* Link in ordinal tree		*/
  unsigned int ord;			/* Ordinal value		*/
  char string[1];			/* String (unsized array)	*/
}
hash__link;

typedef struct hash__table
{
  hash__link *tbl[hash__SIZE];		/* The actual hash table	*/
  hash__link *root;			/* The ordinal tree root	*/
}
hash__table;

/*----- Private code ------------------------------------------------------*/

#define hash__hash(s) (crc32(0,s,strlen(s),1) & (hash__SIZE - 1))

static int hash__addToTree(hash__link **root,hash__link *l)
{
  if (*root)
  {
    if ((*root)->ord > l->ord)
      return (hash__addToTree(&(*root)->left,l));
    else if ((*root)->ord < l->ord || l->ord == 0xFFFFFFFF)
      return (hash__addToTree(&(*root)->right,l));
    else
      return (1);
  }
  else
  {
    *root=l;
    return (0);
  }
}

static void hash__traverse(hash__link *l,
                           void (*func)(char *string,
                                        unsigned int ord,
                                        void *handle),
                           void *handle)
{
  if (l)
  {
    hash__traverse(l->left,func,handle);
    func(l->string,l->ord,handle);
    hash__traverse(l->right,func,handle);
  }
}

static void hash__dump(char *string,unsigned int ord,void *handle)
{
  handle=handle;
  printf(" ** %s (%08x)\n",string,ord);
}

/*----- Public code -------------------------------------------------------*/

hashtable hash_create(void)
{
  return (calloc(1,sizeof(hash__table)));
}

int hash_find(hashtable h,char *string)
{
  int sh=hash__hash(string);
  hash__link *l;
  for (l=h->tbl[sh];l;l=l->next)
  {
    if (!strcmp(l->string,string))
      return (1);
  }
  return (0);
}

int hash_add(hashtable h,char *string)
{
  return (hash_addWithOrd(h,string,0xFFFFFFFF));
}

int hash_addWithOrd(hashtable h,char *string,unsigned int ord)
{
  int sh=hash__hash(string);
  hash__link *l;
  if (hash_find(h,string))
    return (1);
  if (l=malloc(sizeof(hash__link)+strlen(string)),!l)
    return (0);
  strcpy(l->string,string);
  l->ord=ord;
  l->next=h->tbl[sh];
  h->tbl[sh]=l;
  l->left=l->right=0;
  if (hash__addToTree(&h->root,l))
  {
    l->ord=0xFFFFFFFF;
    hash__addToTree(&h->root,l);
  }
  return (1);
}

void hash_delete(hashtable h)
{
  hash__link *l;
  hash__link *n;
  int i;
  for (i=0;i<hash__SIZE;i++)
  {
    for (l=h->tbl[i];l;l=n)
    {
      n=l->next;
      free(l);
    }
  }
  free(h);
}

int hash_subset(hashtable super,
                hashtable sub,
                void (*proc)(char *p))
{
  hash__link *l;
  int i;
  int s=1;
  for (i=0;i<hash__SIZE;i++)
  {
    for (l=sub->tbl[i];l;l=l->next)
    {
      if (!hash_find(super,l->string))
      {
        s=0;
        proc(l->string);
      }
    }
  }
  return (s);
}

void hash_dump(hashtable h)
{
  hash_enumOrdered(h,hash__dump,0);
}
void hash_enumerate(hashtable h,
                    void (*func)(char *string,void *handle),
                    void *handle)
{
  hash__link *l;
  int i;
  for (i=0;i<hash__SIZE;i++)
  {
    for (l=h->tbl[i];l;l=l->next)
      func(l->string,handle);
  }
}

void hash_enumOrdered(hashtable h,
                      void (*func)(char *string,
                                   unsigned int ord,
                                   void *handle),
                      void *handle)
{
  hash__traverse(h->root,func,handle);
}

int hash_count(hashtable h)
{
  int count=0;
  hash__link *l;
  int i;
  for (i=0;i<hash__SIZE;i++)
  {
    for (l=h->tbl[i];l;l=l->next)
      count++;
  }
  return (count);
}