Crossfire Server, Branch 1.12
R12190
|
00001 /*****************************************************************************/ 00002 /* hashtable.c */ 00003 /* Author: Alex Schultz, 2006 */ 00004 /* Based upon shstr.c, origionally written by Kjetil T. Homme, Oslo 1992. */ 00005 /*****************************************************************************/ 00006 /* This is a pointer association hash table library for plugins to use with */ 00007 /* a simple interface. This file is named as it is for other hash table */ 00008 /* types to be added if people wish to. */ 00009 /*****************************************************************************/ 00010 /* That code is placed under the GNU General Public Licence (GPL) */ 00011 /* (C)2001-2005 by Chachkoff Yann (Feel free to deliver your complaints) */ 00012 /*****************************************************************************/ 00013 /* CrossFire, A Multiplayer game for X-windows */ 00014 /* */ 00015 /* Copyright (C) 2000 Mark Wedel */ 00016 /* Copyright (C) 1992 Frank Tore Johansen */ 00017 /* */ 00018 /* This program is free software; you can redistribute it and/or modify */ 00019 /* it under the terms of the GNU General Public License as published by */ 00020 /* the Free Software Foundation; either version 2 of the License, or */ 00021 /* (at your option) any later version. */ 00022 /* */ 00023 /* This program is distributed in the hope that it will be useful, */ 00024 /* but WITHOUT ANY WARRANTY; without even the implied warranty of */ 00025 /* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the */ 00026 /* GNU General Public License for more details. */ 00027 /* */ 00028 /* You should have received a copy of the GNU General Public License */ 00029 /* along with this program; if not, write to the Free Software */ 00030 /* Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. */ 00031 /* */ 00032 /*****************************************************************************/ 00033 00034 #include <string.h> 00035 #include <stdlib.h> 00036 00037 #ifdef WIN32 00038 #include <global.h> 00039 typedef UINT_PTR uintptr_t; 00040 #include <malloc.h> 00041 #else 00042 #include <stdint.h> 00043 #include <autoconf.h> 00044 #endif 00045 #ifdef HAVE_LIBDMALLOC 00046 #include <dmalloc.h> 00047 #endif 00048 00049 #include <hashtable.h> 00050 00057 void init_ptr_assoc_table(ptr_assoc **hash_table) { 00058 (void)memset((void *)hash_table, 0, PTR_ASSOC_TABLESIZE*sizeof(ptr_assoc *)); 00059 } 00060 00072 static int hashptr(void *ptr) { 00073 return (int)((uintptr_t)ptr%PTR_ASSOC_TABLESIZE); 00074 } 00075 00087 static ptr_assoc *new_ptr_assoc(void *key, void *value) { 00088 ptr_assoc *assoc; 00089 00090 assoc = (ptr_assoc *)malloc(sizeof(ptr_assoc)); 00091 assoc->previous = NULL; 00092 assoc->array = NULL; 00093 assoc->next = NULL; 00094 assoc->key = key; 00095 assoc->value = value; 00096 return assoc; 00097 } 00098 00109 void add_ptr_assoc(ptr_assoc **hash_table, void *key, void *value) { 00110 ptr_assoc *assoc; 00111 int ind; 00112 00113 ind = hashptr(key); 00114 assoc = hash_table[ind]; 00115 00116 /* Is there an entry for that hash? */ 00117 if (assoc) { 00118 /* Simple case first: See if the first pointer matches. */ 00119 if (key != assoc->key) { 00120 /* Apparantly, a association with the same hash value has this 00121 * slot. We must see in the list if this perticular key has 00122 * been registered before. 00123 */ 00124 while (assoc->next) { 00125 assoc = assoc->next; 00126 if (key != assoc->key) { 00127 /* This wasn't the right key... */ 00128 continue; 00129 } 00130 /* We found an entry for this key. Make sure the value 00131 * is set as we want it. 00132 */ 00133 assoc->value = value; 00134 return; 00135 } 00136 /* There are no occurences of this key in the hash table. */ 00137 { 00138 ptr_assoc *new_assoc; 00139 00140 new_assoc = new_ptr_assoc(key, value); 00141 assoc->next = new_assoc; 00142 new_assoc->previous = assoc; 00143 return; 00144 } 00145 } 00146 return; 00147 } else { 00148 /* The string isn't registered, and the slot is empty. */ 00149 hash_table[ind] = new_ptr_assoc(key, value); 00150 00151 hash_table[ind]->array = &(hash_table[ind]); 00152 00153 return; 00154 } 00155 } 00156 00168 static ptr_assoc *find_ptr_assoc(ptr_assoc **hash_table, void *key) { 00169 ptr_assoc *assoc; 00170 int ind; 00171 00172 ind = hashptr(key); 00173 assoc = hash_table[ind]; 00174 00175 /* Is there an entry for that hash? */ 00176 if (assoc) { 00177 /* Simple case first: Is the first key the right one? */ 00178 if (assoc->key == key) { 00179 return assoc; 00180 } else { 00181 /* Recurse through the linked list, if there's one. */ 00182 while (assoc->next) { 00183 assoc = assoc->next; 00184 if (assoc->key == key) { 00185 return assoc; 00186 } 00187 } 00188 /* No match. Fall through. */ 00189 } 00190 } 00191 return NULL; 00192 } 00193 00205 void *find_assoc_value(ptr_assoc **hash_table, void *key) { 00206 ptr_assoc *assoc; 00207 00208 assoc = find_ptr_assoc(hash_table, key); 00209 if (!assoc) 00210 return NULL; 00211 return assoc->value; 00212 } 00213 00222 void free_ptr_assoc(ptr_assoc **hash_table, void *key) { 00223 ptr_assoc *assoc; 00224 00225 assoc = find_ptr_assoc(hash_table, key); 00226 if (!assoc) 00227 return; 00228 00229 if (assoc->array) { 00230 /* We must put a new value into the hash_table[]. 00231 */ 00232 if (assoc->next) { 00233 *(assoc->array) = assoc->next; 00234 assoc->next->previous = NULL; 00235 assoc->next->array = assoc->array; 00236 } else { 00237 *(assoc->array) = NULL; 00238 } 00239 free(assoc); 00240 } else { 00241 /* Relink and free this struct. 00242 */ 00243 if (assoc->next) 00244 assoc->next->previous = assoc->previous; 00245 assoc->previous->next = assoc->next; 00246 free(assoc); 00247 } 00248 }