hash.c 3.59 KB
Newer Older
Thomas Roessler's avatar
Thomas Roessler committed
1
/*
2
 * Copyright (C) 1996-2000 Michael R. Elkins <me@cs.hmc.edu>
Thomas Roessler's avatar
Thomas Roessler committed
3 4 5 6 7 8 9 10 11 12 13 14 15
 *
 *     This program 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 of the License, or
 *     (at your option) any later version.
 * 
 *     This program 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 this program; if not, write to the Free Software
16
 *     Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111, USA.
Thomas Roessler's avatar
Thomas Roessler committed
17 18 19 20 21 22 23 24
 */ 

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

#include "mutt.h"

25 26
#define SOMEPRIME 149711

Thomas Roessler's avatar
Thomas Roessler committed
27 28 29
int hash_string (const unsigned char *s, int n)
{
  int h = 0;
30 31

#if 0
Thomas Roessler's avatar
Thomas Roessler committed
32 33
  while (*s)
    h += *s++;
34 35 36 37 38 39 40
#else
  while (*s)
    h += (h << 7) + *s++;
  h = (h * SOMEPRIME) % n;
  h = (h >= 0) ? h : h + n;
#endif

Thomas Roessler's avatar
Thomas Roessler committed
41 42 43 44 45 46 47 48 49 50 51 52
  return (h % n);
}

HASH *hash_create (int nelem)
{
  HASH *table = safe_malloc (sizeof (HASH));
  table->nelem = nelem;
  table->table = safe_calloc (nelem, sizeof (struct hash_elem *));
  return table;
}

/* table        hash table to update
53 54 55 56
 * key          key to hash on
 * data         data to associate with `key'
 * allow_dup    if nonzero, duplicate keys are allowed in the table 
 */
Thomas Roessler's avatar
Thomas Roessler committed
57 58
int hash_insert (HASH * table, const char *key, void *data, int allow_dup)
{
Thomas Roessler's avatar
Thomas Roessler committed
59 60
  struct hash_elem *ptr;
  int h;
Thomas Roessler's avatar
Thomas Roessler committed
61

Thomas Roessler's avatar
Thomas Roessler committed
62 63
  ptr = (struct hash_elem *) safe_malloc (sizeof (struct hash_elem));
  h = hash_string ((unsigned char *) key, table->nelem);
Thomas Roessler's avatar
Thomas Roessler committed
64 65 66 67 68 69 70 71 72 73 74 75 76 77 78
  ptr->key = key;
  ptr->data = data;

  if (allow_dup)
  {
    ptr->next = table->table[h];
    table->table[h] = ptr;
  }
  else
  {
    struct hash_elem *tmp, *last;
    int r;

    for (tmp = table->table[h], last = NULL; tmp; last = tmp, tmp = tmp->next)
    {
79
      r = mutt_strcmp (tmp->key, key);
Thomas Roessler's avatar
Thomas Roessler committed
80 81
      if (r == 0)
      {
Thomas Roessler's avatar
Thomas Roessler committed
82
	FREE (&ptr);
Thomas Roessler's avatar
Thomas Roessler committed
83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101
	return (-1);
      }
      if (r > 0)
	break;
    }
    if (last)
      last->next = ptr;
    else
      table->table[h] = ptr;
    ptr->next = tmp;
  }
  return h;
}

void *hash_find_hash (const HASH * table, int hash, const char *key)
{
  struct hash_elem *ptr = table->table[hash];
  for (; ptr; ptr = ptr->next)
  {
102
    if (mutt_strcmp (key, ptr->key) == 0)
Thomas Roessler's avatar
Thomas Roessler committed
103 104 105 106 107 108 109 110 111
      return (ptr->data);
  }
  return NULL;
}

void hash_delete_hash (HASH * table, int hash, const char *key, const void *data,
		       void (*destroy) (void *))
{
  struct hash_elem *ptr = table->table[hash];
112 113 114
  struct hash_elem **last = &table->table[hash];

  for (; ptr; last = &ptr->next, ptr = ptr->next)
Thomas Roessler's avatar
Thomas Roessler committed
115 116
  {
    /* if `data' is given, look for a matching ->data member.  this is
117 118 119 120
     * required for the case where we have multiple entries with the same
     * key
     */
    if ((data == ptr->data) || (!data && mutt_strcmp (ptr->key, key) == 0))
Thomas Roessler's avatar
Thomas Roessler committed
121
    {
122 123
      *last = ptr->next;
      if (destroy) destroy (ptr->data);
Thomas Roessler's avatar
Thomas Roessler committed
124
      FREE (&ptr);
Thomas Roessler's avatar
Thomas Roessler committed
125 126 127 128 129 130
      return;
    }
  }
}

/* ptr		pointer to the hash table to be freed
131 132
 * destroy()	function to call to free the ->data member (optional) 
 */
Thomas Roessler's avatar
Thomas Roessler committed
133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152
void hash_destroy (HASH **ptr, void (*destroy) (void *))
{
  int i;
  HASH *pptr = *ptr;
  struct hash_elem *elem, *tmp;

  for (i = 0 ; i < pptr->nelem; i++)
  {
    for (elem = pptr->table[i]; elem; )
    {
      tmp = elem;
      elem = elem->next;
      if (destroy)
	destroy (tmp->data);
      safe_free ((void **) &tmp);
    }
  }
  safe_free ((void **) &pptr->table);
  safe_free ((void **) ptr);
}