00001 #include <stdlib.h>
00002 #include "wtab.h"
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012 static int sizes[] = { 1, 3, 5, 7, 11, 19, 29, 37, 47, 59,
00013 71, 89, 107, 127, 151, 181, 211, 239, 257, 281 };
00014
00015 static int sizes_len = 20;
00016
00017 #define MIN_FILL_FACTOR 30
00018 #define MAX_FILL_FACTOR 100
00019 #define DOWNSIZE_RATIO 2
00020
00021 static unsigned long mt_abs(long x)
00022 {
00023 if (x < 0) return -x;
00024 return x;
00025 }
00026
00027
00028
00029
00030
00031 static int choose_size(int size)
00032 {
00033 int new_size;
00034
00035 if (sizes[sizes_len - 1] < size)
00036 {
00037 for (new_size = sizes[sizes_len - 1];
00038 new_size < size;
00039 new_size = new_size * 2 + 1);
00040 }
00041 else
00042 {
00043 int min = -1;
00044 int max = sizes_len - 1;
00045 int pos;
00046
00047 while (max > min + 1)
00048 {
00049 pos = (max + min + 1) / 2;
00050 if (sizes[pos] < size)
00051 min = pos;
00052 else
00053 max = pos;
00054 }
00055
00056 new_size = sizes[max];
00057 }
00058
00059 return new_size;
00060 }
00061
00062 static void resize_table(wtab *t, int size)
00063 {
00064 wtab_node **table = (wtab_node **) calloc(size, sizeof(wtab_node *));
00065
00066 if (table)
00067 {
00068 int i;
00069 wtab_node *ni;
00070 wtab_node **nf;
00071 for (i = 0; i < t->size; i++)
00072 {
00073 ni = t->table[i];
00074 while (ni)
00075 {
00076 nf = &table[ni->key % size];
00077 while (*nf) nf = &(*nf)->next;
00078 *nf = ni;
00079 ni = ni->next;
00080 (*nf)->next = NULL;
00081 }
00082 }
00083
00084 free(t->table);
00085 t->table = table;
00086 t->size = size;
00087 }
00088 }
00089
00090 wtab_node *wtab_node_new(wchar_t key, void *value, void *attr)
00091 {
00092 wtab_node *node = calloc(1, sizeof(wtab_node));
00093 if (node)
00094 {
00095 node->key = key;
00096 node->value = value;
00097 node->attr = attr;
00098 }
00099
00100 return node;
00101 }
00102
00103
00104 wtab *wtab_new(int size)
00105 {
00106 wtab *t = calloc(1, sizeof(wtab));
00107 if (t)
00108 {
00109 t->size = choose_size(size);
00110 t->table = calloc(t->size, sizeof(wtab_node *));
00111 if (t->table == NULL)
00112 {
00113 free(t);
00114 t = NULL;
00115 }
00116 }
00117
00118 return t;
00119 }
00120
00121
00122
00123
00124
00125 void wtab_delete_custom(wtab *t,
00126 void *owner,
00127 wtab_dtr dtr)
00128 {
00129 while (t->size--)
00130 {
00131 wtab_node *curr = t->table[t->size];
00132 wtab_node *tmp;
00133 while (curr)
00134 {
00135 tmp = curr;
00136 curr = curr->next;
00137 (*dtr)(owner, tmp);
00138 free(tmp);
00139 }
00140 }
00141
00142 free(t->table);
00143 free(t);
00144 }
00145
00146 void wtab_delete(wtab *t)
00147 {
00148 while (t->size--)
00149 {
00150 wtab_node *curr = t->table[t->size];
00151 wtab_node *tmp;
00152 while (curr)
00153 {
00154 tmp = curr;
00155 curr = curr->next;
00156 free(tmp);
00157 }
00158 }
00159
00160 free(t->table);
00161 free(t);
00162 }
00163
00164
00165
00166
00167
00168 wtab_node *wtab_put(wtab *t, wchar_t key, void *value, void *attr)
00169 {
00170 wtab_node **loc;
00171
00172 if ((t->items + 1) * 100 > t->size * MAX_FILL_FACTOR)
00173 resize_table(t, choose_size(t->size + 1));
00174
00175 loc = &t->table[key % t->size];
00176 while (*loc && (*loc)->key != key) loc = &(*loc)->next;
00177
00178 if (*loc == NULL)
00179 {
00180 t->items++;
00181 *loc = wtab_node_new(key, value, attr);
00182 }
00183 else
00184 {
00185 (*loc)->value = value;
00186 if ((*loc)->attr) free((*loc)->attr);
00187 (*loc)->attr = attr;
00188 }
00189
00190 return *loc;
00191 }
00192
00193 wtab_node *wtab_get(wtab *t, wchar_t key)
00194 {
00195 wtab_node *node = t->table[key % t->size];
00196
00197 while (node && key != node->key)
00198 node = node->next;
00199
00200 return node;
00201 }
00202
00203
00204
00205
00206
00207 void *wtab_remove(wtab *t, wchar_t key)
00208 {
00209 wtab_node **node;
00210 void *res = NULL;
00211
00212 node = &t->table[key % t->size];
00213
00214 while ((*node) && key != (*node)->key)
00215 node = &(*node)->next;
00216
00217 if (*node)
00218 {
00219 wtab_node *rm = *node;
00220 *node = rm->next;
00221 res = rm->value;
00222 if (rm->attr) free(rm->attr);
00223 free(rm);
00224
00225 t->items--;
00226 }
00227
00228 if (t->items > 0 && t->items * 100 < t->size * MIN_FILL_FACTOR)
00229 resize_table(t, choose_size(t->size / DOWNSIZE_RATIO));
00230
00231 return res;
00232 }
00233
00234 int wtab_count(wtab *t)
00235 {
00236 return t->items;
00237 }
00238
00239 int wtab_callback(wtab *t, cp_callback_fn fn, void *prm)
00240 {
00241 int i;
00242 wtab_node *n;
00243 int count = 0;
00244 int res = 0;
00245
00246 for (i = 0; i < t->size && count < t->items; i++)
00247 {
00248 n = t->table[i];
00249 while (n)
00250 {
00251 count++;
00252 if ((res = (*fn)(n, prm)) != 0) return res;
00253 n = n->next;
00254 }
00255 }
00256
00257 return 0;
00258 }
00259