Crossfire Server, Trunk
hashtable.cpp
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 #include <malloc.h>
40 #else
41 #include <stdint.h>
42 #include <autoconf.h>
43 #endif
44 #ifdef HAVE_LIBDMALLOC
45 #include <dmalloc.h>
46 #endif
47 
48 #include <hashtable.h>
49 
57  (void)memset((void *)hash_table, 0, PTR_ASSOC_TABLESIZE*sizeof(ptr_assoc *));
58 }
59 
71 static int hashptr(void *ptr) {
72  return (int)((uintptr_t)ptr%PTR_ASSOC_TABLESIZE);
73 }
74 
86 static ptr_assoc *new_ptr_assoc(void *key, void *value) {
87  ptr_assoc *assoc;
88 
89  assoc = (ptr_assoc *)malloc(sizeof(ptr_assoc));
90  assoc->previous = NULL;
91  assoc->array = NULL;
92  assoc->next = NULL;
93  assoc->key = key;
94  assoc->value = value;
95  return assoc;
96 }
97 
108 void add_ptr_assoc(ptr_assoc **hash_table, void *key, void *value) {
109  ptr_assoc *assoc;
110  int ind;
111 
112  ind = hashptr(key);
113  assoc = hash_table[ind];
114 
115  /* Is there an entry for that hash? */
116  if (assoc) {
117  /* Simple case first: See if the first pointer matches. */
118  if (key != assoc->key) {
119  /* Apparantly, a association with the same hash value has this
120  * slot. We must see in the list if this perticular key has
121  * been registered before.
122  */
123  while (assoc->next) {
124  assoc = assoc->next;
125  if (key != assoc->key) {
126  /* This wasn't the right key... */
127  continue;
128  }
129  /* We found an entry for this key. Make sure the value
130  * is set as we want it.
131  */
132  assoc->value = value;
133  return;
134  }
135  /* There are no occurences of this key in the hash table. */
136  {
137  ptr_assoc *new_assoc;
138 
139  new_assoc = new_ptr_assoc(key, value);
140  assoc->next = new_assoc;
141  new_assoc->previous = assoc;
142  return;
143  }
144  }
145  return;
146  } else {
147  /* The string isn't registered, and the slot is empty. */
149 
150  hash_table[ind]->array = &(hash_table[ind]);
151 
152  return;
153  }
154 }
155 
168  ptr_assoc *assoc;
169  int ind;
170 
171  ind = hashptr(key);
172  assoc = hash_table[ind];
173 
174  /* Is there an entry for that hash? */
175  if (assoc) {
176  /* Simple case first: Is the first key the right one? */
177  if (assoc->key == key) {
178  return assoc;
179  } else {
180  /* Recurse through the linked list, if there's one. */
181  while (assoc->next) {
182  assoc = assoc->next;
183  if (assoc->key == key) {
184  return assoc;
185  }
186  }
187  /* No match. Fall through. */
188  }
189  }
190  return NULL;
191 }
192 
205  ptr_assoc *assoc;
206 
207  assoc = find_ptr_assoc(hash_table, key);
208  if (!assoc)
209  return NULL;
210  return assoc->value;
211 }
212 
222  ptr_assoc *assoc;
223 
224  assoc = find_ptr_assoc(hash_table, key);
225  if (!assoc)
226  return;
227 
228  if (assoc->array) {
229  /* We must put a new value into the hash_table[].
230  */
231  if (assoc->next) {
232  *(assoc->array) = assoc->next;
233  assoc->next->previous = NULL;
234  assoc->next->array = assoc->array;
235  } else {
236  *(assoc->array) = NULL;
237  }
238  free(assoc);
239  } else {
240  /* Relink and free this struct.
241  */
242  if (assoc->next)
243  assoc->next->previous = assoc->previous;
244  assoc->previous->next = assoc->next;
245  free(assoc);
246  }
247 }
global.h
new_ptr_assoc
static ptr_assoc * new_ptr_assoc(void *key, void *value)
Definition: hashtable.cpp:86
_ptr_assoc::key
void * key
Definition: hashtable.h:11
hashptr
static int hashptr(void *ptr)
Definition: hashtable.cpp:71
_ptr_assoc
Definition: hashtable.h:7
_ptr_assoc::array
struct _ptr_assoc ** array
Definition: hashtable.h:8
hash_table
static shared_string * hash_table[TABLESIZE]
Definition: shstr.cpp:50
_shared_string::array
struct _shared_string ** array
Definition: shstr.h:72
nlohmann::detail::void
j template void())
Definition: json.hpp:4099
PTR_ASSOC_TABLESIZE
#define PTR_ASSOC_TABLESIZE
Definition: hashtable.h:5
find_ptr_assoc
static ptr_assoc * find_ptr_assoc(ptr_assoc **hash_table, void *key)
Definition: hashtable.cpp:167
hashtable.h
find_assoc_value
void * find_assoc_value(ptr_assoc **hash_table, void *key)
Definition: hashtable.cpp:204
_ptr_assoc::next
struct _ptr_assoc * next
Definition: hashtable.h:10
autojail.value
value
Definition: autojail.py:6
castle_read.key
key
Definition: castle_read.py:64
_ptr_assoc::previous
struct _ptr_assoc * previous
Definition: hashtable.h:9
free_ptr_assoc
void free_ptr_assoc(ptr_assoc **hash_table, void *key)
Definition: hashtable.cpp:221
init_ptr_assoc_table
void init_ptr_assoc_table(ptr_assoc **hash_table)
Definition: hashtable.cpp:56
_ptr_assoc::value
void * value
Definition: hashtable.h:12
add_ptr_assoc
void add_ptr_assoc(ptr_assoc **hash_table, void *key, void *value)
Definition: hashtable.cpp:108
autoconf.h