1 /* hash.c - hash tables for opkg
3 Steven M. Ayer, Jamey Hicks
5 Copyright (C) 2002 Compaq Computer Corporation
7 This program is free software; you can redistribute it and/or
8 modify it under the terms of the GNU General Public License as
9 published by the Free Software Foundation; either version 2, or (at
10 your option) any later version.
12 This program is distributed in the hope that it will be useful, but
13 WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 General Public License for more details.
22 #include "hash_table.h"
23 #include "opkg_message.h"
26 static int hash_index(hash_table_t
*hash
, const char *pkg_name
);
27 static int rotating(const char *key
, int len
, int prime
);
29 static int hash_index(hash_table_t
*hash
, const char *pkg_name
)
31 return rotating(pkg_name
, strlen(pkg_name
), hash
->n_entries
);
34 static int rotating(const char *key
, int len
, int prime
)
37 for (hash
=len
, i
=0; i
<len
; ++i
)
38 hash
= (hash
<<4)^(hash
>>28)^key
[i
];
39 return (hash
% prime
);
44 * this is an open table keyed by strings
46 int hash_table_init(const char *name
, hash_table_t
*hash
, int len
)
48 static int primes_table
[] = {
49 379, 761, 983, 1423, 2711, 3361, 3931, 4679, 5519, 6701, 9587,
50 19471, 23143, 33961, 46499, 49727, 99529, 0
54 if (hash
->entries
!= NULL
) {
55 /* we have been here already */
62 hash
->hash_entry_key
= NULL
;
64 picker
= primes_table
;
65 while(*picker
&& (*picker
++ < len
));
67 fprintf(stderr
, "%s: primes table might not be big enough (! << %d)\n", __FUNCTION__
, len
);
70 hash
->n_entries
= *picker
;
71 hash
->entries
= (hash_entry_t
*)calloc(hash
->n_entries
, sizeof(hash_entry_t
));
72 if (hash
->entries
== NULL
) {
73 fprintf(stderr
, "%s: Out of memory.\n", __FUNCTION__
);
79 void hash_table_deinit(hash_table_t
*hash
)
85 /* free the reminaing entries */
86 for (i
= 0; i
< hash
->n_entries
; i
++) {
87 hash_entry_t
*hash_entry
= (hash
->entries
+ i
);
88 free (hash_entry
->key
);
89 /* skip the first entry as this is part of the array */
90 hash_entry
= hash_entry
->next
;
93 hash_entry_t
*old
= hash_entry
;
94 hash_entry
= hash_entry
->next
;
100 free (hash
->entries
);
102 hash
->entries
= NULL
;
106 void *hash_table_get(hash_table_t
*hash
, const char *key
)
108 int ndx
= hash_index(hash
, key
);
109 hash_entry_t
*hash_entry
= hash
->entries
+ ndx
;
114 if (strcmp(key
, hash_entry
->key
) == 0) {
115 // opkg_message(NULL, OPKG_DEBUG, "Function: %s. Key found for '%s' \n", __FUNCTION__, key);
116 return hash_entry
->data
;
119 hash_entry
= hash_entry
->next
;
124 int hash_table_insert(hash_table_t
*hash
, const char *key
, void *value
)
126 int ndx
= hash_index(hash
, key
);
127 hash_entry_t
*hash_entry
= hash
->entries
+ ndx
;
128 if (0) opkg_message(NULL
, OPKG_DEBUG2
, "Function: %s. Inserting in hash for '%s' \n", __FUNCTION__
, key
);
129 if (hash_entry
->key
) {
130 if (strcmp(hash_entry
->key
, key
) == 0) {
131 /* alread in table, update the value */
132 if (0) opkg_message(NULL
, OPKG_DEBUG2
, "Function: %s. Value already in hash for '%s' \n", __FUNCTION__
, key
);
133 hash_entry
->data
= value
;
137 * if this is a collision, we have to go to the end of the ll,
138 * then add a new entry
139 * before we can hook up the value
141 if (0) opkg_message(NULL
, OPKG_DEBUG2
, "Function: %s. Value already in hash by collision for '%s' \n", __FUNCTION__
, key
);
142 while (hash_entry
->next
) {
143 hash_entry
= hash_entry
->next
;
144 if (strcmp(hash_entry
->key
, key
) == 0) {
145 hash_entry
->data
= value
;
149 hash_entry
->next
= (hash_entry_t
*)calloc(1, sizeof(hash_entry_t
));
150 if (!hash_entry
->next
) {
153 hash_entry
= hash_entry
->next
;
154 hash_entry
->next
= NULL
;
158 hash_entry
->key
= strdup(key
);
159 hash_entry
->data
= value
;
164 int hash_table_remove(hash_table_t
*hash
, const char *key
)
166 int ndx
= hash_index(hash
, key
);
167 hash_entry_t
*hash_entry
= hash
->entries
+ ndx
;
168 hash_entry_t
*next_entry
=NULL
, *last_entry
=NULL
;
173 if (strcmp(key
, hash_entry
->key
) == 0) {
174 free(hash_entry
->key
);
176 last_entry
->next
= hash_entry
->next
;
179 next_entry
= hash_entry
->next
;
181 memmove(hash_entry
, next_entry
, sizeof(hash_entry_t
));
184 memset(hash_entry
, 0 , sizeof(hash_entry_t
));
190 last_entry
= hash_entry
;
191 hash_entry
= hash_entry
->next
;
196 void hash_table_foreach(hash_table_t
*hash
, void (*f
)(const char *key
, void *entry
, void *data
), void *data
)
202 for (i
= 0; i
< hash
->n_entries
; i
++) {
203 hash_entry_t
*hash_entry
= (hash
->entries
+ i
);
205 if(hash_entry
->key
) {
206 f(hash_entry
->key
, hash_entry
->data
, data
);
208 } while((hash_entry
= hash_entry
->next
));