Crossfire Server, Trunk  R20513
hashtable.c
Go to the documentation of this file.
1 /*****************************************************************************/
2 /* hashtable.c */
3 /* Author: Alex Schultz, 2006 */
4 /* Based upon shstr.c, origionally written by Kjetil T. Homme, Oslo 1992. */
5 /*****************************************************************************/
6 /* This is a pointer association hash table library for plugins to use with */
7 /* a simple interface. This file is named as it is for other hash table */
8 /* types to be added if people wish to. */
9 /*****************************************************************************/
10 /* That code is placed under the GNU General Public Licence (GPL) */
11 /* (C)2001-2005 by Chachkoff Yann (Feel free to deliver your complaints) */
12 /*****************************************************************************/
13 /* CrossFire, A Multiplayer game for X-windows */
14 /* */
15 /* Copyright (C) 2000 Mark Wedel */
16 /* Copyright (C) 1992 Frank Tore Johansen */
17 /* */
18 /* This program is free software; you can redistribute it and/or modify */
19 /* it under the terms of the GNU General Public License as published by */
20 /* the Free Software Foundation; either version 2 of the License, or */
21 /* (at your option) any later version. */
22 /* */
23 /* This program is distributed in the hope that it will be useful, */
24 /* but WITHOUT ANY WARRANTY; without even the implied warranty of */
25 /* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the */
26 /* GNU General Public License for more details. */
27 /* */
28 /* You should have received a copy of the GNU General Public License */
29 /* along with this program; if not, write to the Free Software */
30 /* Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. */
31 /* */
32 /*****************************************************************************/
33 
34 #include <string.h>
35 #include <stdlib.h>
36 
37 #ifdef WIN32
38 #include <global.h>
39 typedef UINT_PTR uintptr_t;
40 #include <malloc.h>
41 #else
42 #include <stdint.h>
43 #include <autoconf.h>
44 #endif
45 #ifdef HAVE_LIBDMALLOC
46 #include <dmalloc.h>
47 #endif
48 
49 #include <hashtable.h>
50 
58  (void)memset((void *)hash_table, 0, PTR_ASSOC_TABLESIZE*sizeof(ptr_assoc *));
59 }
60 
72 static int hashptr(void *ptr) {
73  return (int)((uintptr_t)ptr%PTR_ASSOC_TABLESIZE);
74 }
75 
87 static ptr_assoc *new_ptr_assoc(void *key, void *value) {
88  ptr_assoc *assoc;
89 
90  assoc = (ptr_assoc *)malloc(sizeof(ptr_assoc));
91  assoc->previous = NULL;
92  assoc->array = NULL;
93  assoc->next = NULL;
94  assoc->key = key;
95  assoc->value = value;
96  return assoc;
97 }
98 
109 void add_ptr_assoc(ptr_assoc **hash_table, void *key, void *value) {
110  ptr_assoc *assoc;
111  int ind;
112 
113  ind = hashptr(key);
114  assoc = hash_table[ind];
115 
116  /* Is there an entry for that hash? */
117  if (assoc) {
118  /* Simple case first: See if the first pointer matches. */
119  if (key != assoc->key) {
120  /* Apparantly, a association with the same hash value has this
121  * slot. We must see in the list if this perticular key has
122  * been registered before.
123  */
124  while (assoc->next) {
125  assoc = assoc->next;
126  if (key != assoc->key) {
127  /* This wasn't the right key... */
128  continue;
129  }
130  /* We found an entry for this key. Make sure the value
131  * is set as we want it.
132  */
133  assoc->value = value;
134  return;
135  }
136  /* There are no occurences of this key in the hash table. */
137  {
138  ptr_assoc *new_assoc;
139 
140  new_assoc = new_ptr_assoc(key, value);
141  assoc->next = new_assoc;
142  new_assoc->previous = assoc;
143  return;
144  }
145  }
146  return;
147  } else {
148  /* The string isn't registered, and the slot is empty. */
149  hash_table[ind] = new_ptr_assoc(key, value);
150 
151  hash_table[ind]->array = &(hash_table[ind]);
152 
153  return;
154  }
155 }
156 
169  ptr_assoc *assoc;
170  int ind;
171 
172  ind = hashptr(key);
173  assoc = hash_table[ind];
174 
175  /* Is there an entry for that hash? */
176  if (assoc) {
177  /* Simple case first: Is the first key the right one? */
178  if (assoc->key == key) {
179  return assoc;
180  } else {
181  /* Recurse through the linked list, if there's one. */
182  while (assoc->next) {
183  assoc = assoc->next;
184  if (assoc->key == key) {
185  return assoc;
186  }
187  }
188  /* No match. Fall through. */
189  }
190  }
191  return NULL;
192 }
193 
205 void *find_assoc_value(ptr_assoc **hash_table, void *key) {
206  ptr_assoc *assoc;
207 
208  assoc = find_ptr_assoc(hash_table, key);
209  if (!assoc)
210  return NULL;
211  return assoc->value;
212 }
213 
222 void free_ptr_assoc(ptr_assoc **hash_table, void *key) {
223  ptr_assoc *assoc;
224 
225  assoc = find_ptr_assoc(hash_table, key);
226  if (!assoc)
227  return;
228 
229  if (assoc->array) {
230  /* We must put a new value into the hash_table[].
231  */
232  if (assoc->next) {
233  *(assoc->array) = assoc->next;
234  assoc->next->previous = NULL;
235  assoc->next->array = assoc->array;
236  } else {
237  *(assoc->array) = NULL;
238  }
239  free(assoc);
240  } else {
241  /* Relink and free this struct.
242  */
243  if (assoc->next)
244  assoc->next->previous = assoc->previous;
245  assoc->previous->next = assoc->next;
246  free(assoc);
247  }
248 }
static ptr_assoc * new_ptr_assoc(void *key, void *value)
Allocates and initialises a new ptr_assoc structure.
Definition: hashtable.c:87
Global type definitions and header inclusions.
static int hashptr(void *ptr)
Hashing-function used by the pointer association library.
Definition: hashtable.c:72
struct _ptr_assoc * next
Definition: hashtable.h:10
void * key
Definition: hashtable.h:11
void * value
Definition: hashtable.h:12
void * find_assoc_value(ptr_assoc **hash_table, void *key)
Find the value associated with a given key.
Definition: hashtable.c:205
static shared_string * hash_table[TABLESIZE]
Hash table to store our string.
Definition: shstr.c:50
void add_ptr_assoc(ptr_assoc **hash_table, void *key, void *value)
Adds a value to a hash table which one can lookup with key.
Definition: hashtable.c:109
struct _ptr_assoc * previous
Definition: hashtable.h:9
void init_ptr_assoc_table(ptr_assoc **hash_table)
Initialises the hash table for a pointer association table.
Definition: hashtable.c:57
static ptr_assoc * find_ptr_assoc(ptr_assoc **hash_table, void *key)
Find the ptr_assoc with a given key.
Definition: hashtable.c:168
struct _ptr_assoc ** array
Definition: hashtable.h:8
#define PTR_ASSOC_TABLESIZE
Definition: hashtable.h:5
void free_ptr_assoc(ptr_assoc **hash_table, void *key)
Remove the association with a given key.
Definition: hashtable.c:222