Whamcloud - gitweb
. fixed ia64 format warnings
[fs/lustre-release.git] / 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;
97     unsigned char *n;
98     int i;
99     if (!s) return(1);
100     for (n=s,i=0;*n;n++,i++) result^=(*n*57)^*n*i;
101     return(result);
102 }
103
104
105 /* Function: hash_create_table
106  * Arguments: compare_function: a function to compare
107  *                              a table instance with a correlator
108  *            key_function: a function to generate a 32 bit 
109  *                          hash key from a correlator
110  * Returns: a pointer to the new table
111  */
112 table hash_create_table (int (*compare_function)(void *, void *),
113                     unsigned int (*key_function)(unsigned int *))
114 {
115     table new=(table)malloc(sizeof(struct table));
116     memset(new, 0, sizeof(struct table));
117
118     new->compare_function=compare_function;
119     new->key_function=key_function;
120     new->number_of_entries=0;
121     new->size=4;
122     new->entries=(table_entry *)malloc(sizeof(table_entry)*new->size);
123     memset(new->entries,0,sizeof(table_entry)*new->size);
124     return(new);
125 }
126
127
128 /* Function: hash_table_find
129  * Arguments: t: a table to look in
130  *            comparator: a value to access the table entry
131  * Returns: the element references to by comparator, or null
132  */
133 void *hash_table_find (table t, void *comparator)
134 {
135     int success;
136     table_entry* entry=table_lookup(t,comparator,
137                                     (*t->key_function)(comparator),
138                                     t->compare_function,
139                                     &success);
140     if (success)  return((*entry)->value);
141     return(0);
142 }
143
144
145 /* Function: hash_table_insert
146  * Arguments: t: a table to insert the object
147  *            value: the object to put in the table
148  *            comparator: the value by which the object 
149  *                        will be addressed
150  * Returns: nothing
151  */
152 void hash_table_insert (table t, void *value, void *comparator)
153 {
154     int success;
155     unsigned int k=(*t->key_function)(comparator);
156     table_entry *position=table_lookup(t,comparator,k,
157                                        t->compare_function,&success);
158     table_entry entry;
159
160     if (success) {
161         entry = *position;
162     } else {
163         entry = (table_entry)malloc(sizeof(struct table_entry));
164         memset(entry, 0, sizeof(struct table_entry));
165         entry->next= *position;
166         *position=entry;
167         t->number_of_entries++;
168     }
169     entry->value=value;
170     entry->key=k;
171     if (t->number_of_entries > t->size) resize_table(t,t->size*2);
172 }
173
174 /* Function: hash_table_remove
175  * Arguments: t: the table to remove the object from
176  *            comparator: the index value of the object to remove
177  * Returns: 
178  */
179 void hash_table_remove (table t, void *comparator)
180 {
181     int success;
182     table_entry temp;
183     table_entry *position=table_lookup(t,comparator,
184                                        (*t->key_function)(comparator),
185                                        t->compare_function,&success);
186     if(success) {
187         temp=*position;
188         *position=(*position)->next;
189         free(temp); /* the value? */
190         t->number_of_entries--;
191     }
192 }
193
194 /* Function: hash_iterate_table_entries
195  * Arguments: t: the table to iterate over
196  *            handler: a function to call with each element
197  *                     of the table, along with arg
198  *            arg: the opaque object to pass to handler
199  * Returns: nothing
200  */
201 void hash_iterate_table_entries(table t,
202                            void (*handler)(void *,void *), 
203                            void *arg)
204 {
205     int i;
206     table_entry *j,*next;
207   
208     for (i=0;i<t->size;i++)
209         for (j=t->entries+i;*j;j=next){
210             next=&((*j)->next);
211             (*handler)(arg,(*j)->value);
212         }
213 }
214
215 /* Function: hash_filter_table_entries
216  * Arguments: t: the table to iterate over
217  *            handler: a function to call with each element
218  *                     of the table, along with arg
219  *            arg: the opaque object to pass to handler
220  * Returns: nothing
221  * Notes: operations on the table inside handler are not safe
222  *
223  * filter_table_entires() calls the handler function for each
224  *   item in the table, passing it and arg. The handler function
225  *   returns 1 if it is to be retained in the table, and 0
226  *   if it is to be removed.
227  */
228 void hash_filter_table_entries(table t, int (*handler)(void *, void *), void *arg)
229 {
230     int i;
231     table_entry *j,*next,v;
232   
233     for (i=0;i<t->size;i++)
234         for (j=t->entries+i;*j;j=next){
235             next=&((*j)->next);
236             if (!(*handler)(arg,(*j)->value)){
237                 next=j;
238                 v=*j;
239                 *j=(*j)->next;
240                 free(v);
241                 t->number_of_entries--;
242             }
243         }
244 }
245
246 /* Function: destroy_table
247  * Arguments: t: the table to free
248  *            thunk: a function to call with each element,
249  *                   most likely free()
250  * Returns: nothing
251  */
252 void hash_destroy_table(table t,void (*thunk)(void *))
253 {
254     table_entry j,next;
255     int i;
256     for (i=0;i<t->size;i++)
257         for (j=t->entries[i];j;j=next){
258             next=j->next;
259             if (thunk) (*thunk)(j->value);
260             free(j);
261         }
262     free(t->entries);
263     free(t);
264 }