lnet/ulnds/socklnd/table.c

   1 /* -*- mode: c; c-basic-offset: 8; indent-tabs-mode: nil; -*-
   2  * vim:expandtab:shiftwidth=8:tabstop=8:
   3  *
   4  *  Copyright (c) 2002 Cray Inc.
   5  *  Copyright (c) 2002 Eric Hoffman
   6  *
   7  *   This file is part of Lustre, http://www.lustre.org.
   8  *
   9  *   Lustre is free software; you can redistribute it and/or
  10  *   modify it under the terms of version 2 of the GNU General Public
  11  *   License as published by the Free Software Foundation.
  12  *
  13  *   Lustre is distributed in the hope that it will be useful,
  14  *   but WITHOUT ANY WARRANTY; without even the implied warranty of
  15  *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16  *   GNU General Public License for more details.
  17  *
  18  *   You should have received a copy of the GNU General Public License
  19  *   along with Lustre; if not, write to the Free Software
  20  *   Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  21  */
  22
  23 #include <table.h>
  24 #include <stdlib.h>
  25 #include <string.h>
  26
  27
  28 /* table.c:
  29  * a very simple hash table implementation with paramerterizable
  30  * comparison and key generation functions. it does resize
  31  * in order to accomidate more entries, but never collapses
  32  * the table
  33  */
  34
  35 static table_entry *table_lookup (table t,void *comparator,
  36                                   unsigned int k,
  37                                   int (*compare_function)(void *, void *),
  38                                   int *success)
  39 {
  40     unsigned int key=k%t->size;
  41     table_entry *i;
  42
  43     for (i=&(t->entries[key]);*i;i=&((*i)->next)){
  44         if (compare_function && ((*i)->key==k))
  45             if ((*t->compare_function)((*i)->value,comparator)){
  46                 *success=1;
  47                 return(i);
  48             }
  49     }
  50     *success=0;
  51     return(&(t->entries[key]));
  52 }
  53
  54
  55 static void resize_table(table t, int size)
  56 {
  57     int old_size=t->size;
  58     table_entry *old_entries=t->entries;
  59     int i;
  60     table_entry j,n;
  61     table_entry *position;
  62     int success;
  63
  64     t->size=size;
  65     t->entries=(table_entry *)malloc(sizeof(table_entry)*t->size);
  66     memset(t->entries,0,sizeof(table_entry)*t->size);
  67
  68     for (i=0;i<old_size;i++)
  69         for (j=old_entries[i];j;j=n){
  70             n=j->next;
  71             position=table_lookup(t,0,j->key,0,&success);
  72             j->next= *position;
  73             *position=j;
  74         }
  75     free(old_entries);
  76 }
  77
  78
  79 /* Function: key_from_int
  80  * Arguments: int i: value to compute the key of
  81  * Returns: the key
  82  */
  83 unsigned int key_from_int(int i)
  84 {
  85     return(i);
  86 }
  87
  88
  89 /* Function: key_from_string
  90  * Arguments: char *s: the null terminated string
  91  *                     to compute the key of
  92  * Returns: the key
  93  */
  94 unsigned int key_from_string(char *s)
  95 {
  96     unsigned int result=0, i;
  97     unsigned char *n;
  98
  99     if (!s)
 100             return(1);
 101     for (n = (unsigned char *)s, i = 0; *n; n++, i++)
 102             result ^= (*n * 57) ^ *n * i;
 103
 104     return(result);
 105 }
 106
 107
 108 /* Function: hash_create_table
 109  * Arguments: compare_function: a function to compare
 110  *                              a table instance with a correlator
 111  *            key_function: a function to generate a 32 bit
 112  *                          hash key from a correlator
 113  * Returns: a pointer to the new table
 114  */
 115 table hash_create_table (int (*compare_function)(void *, void *),
 116                     unsigned int (*key_function)(void *))
 117 {
 118     table new=(table)malloc(sizeof(struct table));
 119     memset(new, 0, sizeof(struct table));
 120
 121     new->compare_function=compare_function;
 122     new->key_function=key_function;
 123     new->number_of_entries=0;
 124     new->size=4;
 125     new->entries=(table_entry *)malloc(sizeof(table_entry)*new->size);
 126     memset(new->entries,0,sizeof(table_entry)*new->size);
 127     return(new);
 128 }
 129
 130
 131 /* Function: hash_table_find
 132  * Arguments: t: a table to look in
 133  *            comparator: a value to access the table entry
 134  * Returns: the element references to by comparator, or null
 135  */
 136 void *hash_table_find (table t, void *comparator)
 137 {
 138     int success;
 139     table_entry* entry=table_lookup(t,comparator,
 140                                     (*t->key_function)(comparator),
 141                                     t->compare_function,
 142                                     &success);
 143     if (success)  return((*entry)->value);
 144     return(0);
 145 }
 146
 147
 148 /* Function: hash_table_insert
 149  * Arguments: t: a table to insert the object
 150  *            value: the object to put in the table
 151  *            comparator: the value by which the object
 152  *                        will be addressed
 153  * Returns: nothing
 154  */
 155 void hash_table_insert (table t, void *value, void *comparator)
 156 {
 157     int success;
 158     unsigned int k=(*t->key_function)(comparator);
 159     table_entry *position=table_lookup(t,comparator,k,
 160                                        t->compare_function,&success);
 161     table_entry entry;
 162
 163     if (success) {
 164         entry = *position;
 165     } else {
 166         entry = (table_entry)malloc(sizeof(struct table_entry));
 167         memset(entry, 0, sizeof(struct table_entry));
 168         entry->next= *position;
 169         *position=entry;
 170         t->number_of_entries++;
 171     }
 172     entry->value=value;
 173     entry->key=k;
 174     if (t->number_of_entries > t->size) resize_table(t,t->size*2);
 175 }
 176
 177 /* Function: hash_table_remove
 178  * Arguments: t: the table to remove the object from
 179  *            comparator: the index value of the object to remove
 180  * Returns:
 181  */
 182 void hash_table_remove (table t, void *comparator)
 183 {
 184     int success;
 185     table_entry temp;
 186     table_entry *position=table_lookup(t,comparator,
 187                                        (*t->key_function)(comparator),
 188                                        t->compare_function,&success);
 189     if(success) {
 190         temp=*position;
 191         *position=(*position)->next;
 192         free(temp); /* the value? */
 193         t->number_of_entries--;
 194     }
 195 }
 196
 197 /* Function: hash_iterate_table_entries
 198  * Arguments: t: the table to iterate over
 199  *            handler: a function to call with each element
 200  *                     of the table, along with arg
 201  *            arg: the opaque object to pass to handler
 202  * Returns: nothing
 203  */
 204 void hash_iterate_table_entries(table t,
 205                            void (*handler)(void *,void *),
 206                            void *arg)
 207 {
 208     int i;
 209     table_entry *j,*next;
 210
 211     for (i=0;i<t->size;i++)
 212         for (j=t->entries+i;*j;j=next){
 213             next=&((*j)->next);
 214             (*handler)(arg,(*j)->value);
 215         }
 216 }
 217
 218 /* Function: hash_filter_table_entries
 219  * Arguments: t: the table to iterate over
 220  *            handler: a function to call with each element
 221  *                     of the table, along with arg
 222  *            arg: the opaque object to pass to handler
 223  * Returns: nothing
 224  * Notes: operations on the table inside handler are not safe
 225  *
 226  * filter_table_entires() calls the handler function for each
 227  *   item in the table, passing it and arg. The handler function
 228  *   returns 1 if it is to be retained in the table, and 0
 229  *   if it is to be removed.
 230  */
 231 void hash_filter_table_entries(table t, int (*handler)(void *, void *), void *arg)
 232 {
 233     int i;
 234     table_entry *j,*next,v;
 235
 236     for (i=0;i<t->size;i++)
 237         for (j=t->entries+i;*j;j=next){
 238             next=&((*j)->next);
 239             if (!(*handler)(arg,(*j)->value)){
 240                 next=j;
 241                 v=*j;
 242                 *j=(*j)->next;
 243                 free(v);
 244                 t->number_of_entries--;
 245             }
 246         }
 247 }
 248
 249 /* Function: destroy_table
 250  * Arguments: t: the table to free
 251  *            thunk: a function to call with each element,
 252  *                   most likely free()
 253  * Returns: nothing
 254  */
 255 void hash_destroy_table(table t,void (*thunk)(void *))
 256 {
 257     table_entry j,next;
 258     int i;
 259     for (i=0;i<t->size;i++)
 260         for (j=t->entries[i];j;j=next){
 261             next=j->next;
 262             if (thunk) (*thunk)(j->value);
 263             free(j);
 264         }
 265     free(t->entries);
 266     free(t);
 267 }