src/cache.c
/* [<][>][^][v][top][bottom][index][help] */
FUNCTIONS
This source file includes following functions.
- vf_cache_create
- c_get_elem
- c_del_elem
- lru_unlink_elem
- lru_put_top
- lru_move_top
- lru_delete_tail
- c_hash
- c_hash_is_interned
- c_hash_intern
- c_hash_unintern
- vf_hash_create
- h_hash_get_object
- h_hash_put_object
- h_hash_del_object
- h_hash_intern
- h_hash_unintern
- h_hash
- vf_table_create
- table_put_obj
- table_put_obj2
- table_get_id_by_key
- table_get_id_by_obj
- table_get_obj_by_id
- table_get_obj_by_key
- table_del_obj_by_id
- table_del_obj_by_key
- table_link_by_id
- table_unlink_by_id
- table_get_nelements
1 /*
2 * cache.c - generic cache module
3 * by Hirotsugu Kakugawa
4 * 5 Aug 1996
5 */
6 /*
7 * Copyright (C) 1996, 1997 Hirotsugu Kakugawa.
8 * All rights reserved.
9 *
10 * This file is part of the VFlib Library. This library is free
11 * software; you can redistribute it and/or modify it under the terms of
12 * the GNU Library General Public License as published by the Free
13 * Software Foundation; either version 2 of the License, or (at your
14 * option) any later version. This library is distributed in the hope
15 * that it will be useful, but WITHOUT ANY WARRANTY; without even the
16 * implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
17 * PURPOSE. See the GNU Library General Public License for more details.
18 * You should have received a copy of the GNU Library General Public
19 * License along with this library; if not, write to the Free Software
20 * Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
21 */
22
23 #include "config.h"
24 #include <stdio.h>
25 #include <stdlib.h>
26 #ifdef HAVE_UNISTD_H
27 # include <unistd.h>
28 #endif
29 #include "VFlib-3_6.h"
30 #include "VFsys.h"
31 #include "cache.h"
32
33
34 /**
35 ** CACHE (lru+hash)
36 **/
37
38 Private void *c_get_elem(VF_CACHE,void*,int);
39 Private void c_del_elem(VF_CACHE,void*,int);
40 Private void lru_move_top(VF_CACHE,VF_CACHE_ELEM);
41 Private void lru_put_top(VF_CACHE,VF_CACHE_ELEM);
42 Private VF_CACHE_ELEM lru_delete_tail(VF_CACHE);
43 Private void lru_unlink_elem(VF_CACHE,VF_CACHE_ELEM);
44 Private int c_hash(VF_CACHE,void*,int);
45 Private VF_CACHE_ELEM c_hash_is_interned(VF_CACHE,void*,int);
46 Private void c_hash_intern(VF_CACHE,VF_CACHE_ELEM,void*,int);
47 Private void c_hash_unintern(VF_CACHE,VF_CACHE_ELEM);
48
49 /* vf_cache_create()
50 * --- Creates a cache object.
51 */
52 Public VF_CACHE
53 vf_cache_create (int cache_size, int hash_size,
/* [<][>][^][v][top][bottom][index][help] */
54 void* (*load_func)(VF_CACHE,void*,int),
55 void (*unload_func)(void*))
56 {
57 int i;
58 VF_CACHE cache;
59 VF_CACHE_ELEM celem;
60
61 if (hash_size < 1)
62 return NULL;
63 ALLOC_IF_ERR(cache, struct s_vf_cache)
64 return NULL;
65
66 celem = NULL;
67 if (cache_size < 0){
68 cache->free_list = NULL;
69 } else {
70 ALLOCN_IF_ERR(celem, struct s_vf_cache_elem, cache_size){
71 vf_free(cache);
72 return NULL;
73 }
74 for (i = 0; i < cache_size; i++)
75 celem[i].h_forw = &celem[i+1];
76 celem[cache_size-1].h_forw = NULL;
77 cache->free_list = &celem[0];
78 }
79
80 ALLOCN_IF_ERR(cache->hash_table, struct s_vf_cache_elem, hash_size){
81 if (celem != NULL)
82 vf_free(celem);
83 vf_free(cache);
84 return NULL;
85 }
86
87 cache->cache_size = cache_size;
88 cache->hash_size = hash_size;
89 cache->get = c_get_elem;
90 cache->del = c_del_elem;
91 cache->load_elem = load_func;
92 cache->unload_elem = unload_func;
93 cache->lru_list.l_forw = &cache->lru_list;
94 cache->lru_list.l_back = &cache->lru_list;
95 for (i = 0; i < hash_size; i++){
96 cache->hash_table[i].h_forw = &cache->hash_table[i];
97 cache->hash_table[i].h_back = &cache->hash_table[i];
98 }
99 return cache;
100 }
101
102 /* c_get_elem()
103 * --- returns a elem. If not chached, reload it.
104 */
105 Private void*
106 c_get_elem(VF_CACHE cache, void *key, int key_len)
/* [<][>][^][v][top][bottom][index][help] */
107 {
108 VF_CACHE_ELEM ce;
109 void *key2;
110
111 if ((ce = c_hash_is_interned(cache, key, key_len)) != NULL){
112 lru_move_top(cache, ce);
113 return (ce->object);
114 }
115
116 if ((ce = cache->free_list) == NULL){
117 if (cache->cache_size > 0){
118 if ((ce = lru_delete_tail(cache)) == NULL){
119 fprintf(stderr, "Internal error in GET of CACHE object\n");
120 abort();
121 }
122 c_hash_unintern(cache, ce);
123 ce->h_forw = cache->free_list;
124 cache->free_list = ce;
125 if (cache->unload_elem != NULL)
126 (cache->unload_elem)(ce->object);
127 else if (ce->object != NULL)
128 vf_free(ce->object);
129 ce->object = NULL;
130 if (ce->key != NULL)
131 vf_free(ce->key);
132 } else {
133 ALLOC_IF_ERR(ce, struct s_vf_cache_elem)
134 return NULL;
135 ce->h_forw = NULL;
136 }
137 }
138 cache->free_list = ce->h_forw;
139 if ((key2 = malloc(key_len)) == NULL)
140 return NULL;
141 memcpy(key2, key, key_len);
142 ce->object = (cache->load_elem)(cache, key, key_len);
143 ce->key = key2;
144 ce->key_len = key_len;
145 c_hash_intern(cache, ce, key2, key_len);
146 lru_put_top(cache, ce);
147 return (ce->object);
148 }
149
150 /* c_del_elem()
151 * --- delete an elem.
152 */
153 Private void
154 c_del_elem(VF_CACHE cache, void *key, int key_len)
/* [<][>][^][v][top][bottom][index][help] */
155 {
156 VF_CACHE_ELEM ce;
157
158 if ((ce = c_hash_is_interned(cache, key, key_len)) == NULL)
159 return;
160 c_hash_unintern(cache, ce);
161 lru_unlink_elem(cache, ce);
162 if (cache->unload_elem != NULL)
163 (cache->unload_elem)(ce->object);
164 else if (ce->object != NULL)
165 vf_free(ce->object);
166 ce->object = NULL;
167
168 if (cache->cache_size > 0){
169 ce->h_forw = cache->free_list;
170 cache->free_list = ce;
171 } else {
172 vf_free(ce);
173 }
174 }
175
176 Private void
177 lru_unlink_elem(VF_CACHE cache, VF_CACHE_ELEM ce)
/* [<][>][^][v][top][bottom][index][help] */
178 {
179 VF_CACHE_ELEM ce_b, ce_f;
180
181 ce_b = ce->l_back;
182 ce_f = ce->l_forw;
183 ce_b->l_forw = ce_f;
184 ce_f->l_back = ce_b;
185 }
186
187 /* lru_put_top()
188 * --- puts an ELEM at the head of LRU list.
189 * The ELEM must not be in LRU list.
190 */
191 Private void
192 lru_put_top(VF_CACHE cache, VF_CACHE_ELEM ce)
/* [<][>][^][v][top][bottom][index][help] */
193 {
194 VF_CACHE_ELEM ce_f;
195
196 ce_f = cache->lru_list.l_forw;
197 ce->l_forw = ce_f;
198 ce_f->l_back = ce;
199 ce->l_back = &cache->lru_list;
200 cache->lru_list.l_forw = ce;
201 }
202
203 /* lru_move_top()
204 * --- moves an ELEM at the top of LRU list.
205 * ELEM must be in LRU list.
206 */
207 Private void
208 lru_move_top(VF_CACHE cache, VF_CACHE_ELEM ce)
/* [<][>][^][v][top][bottom][index][help] */
209 {
210 lru_unlink_elem(cache, ce);
211 lru_put_top(cache, ce);
212 }
213
214 Private VF_CACHE_ELEM
215 lru_delete_tail(VF_CACHE cache) /* NOTE: There must be at least one
/* [<][>][^][v][top][bottom][index][help] */
216 ELEM in LRU list */
217 {
218 VF_CACHE_ELEM ce;
219
220 if ((ce = cache->lru_list.l_back) == &cache->lru_list)
221 return NULL;
222 lru_unlink_elem(cache, ce);
223 return ce;
224 }
225
226 Private int
227 c_hash(VF_CACHE cache, void *key, int key_len)
/* [<][>][^][v][top][bottom][index][help] */
228 {
229 char *p;
230 int i;
231 unsigned int h;
232
233 h = 0;
234 for (i = 0, p = key; i < key_len; i++, p++)
235 h = (h + (unsigned int)*p) % cache->hash_size;
236 return h;
237 }
238
239 Private VF_CACHE_ELEM
240 c_hash_is_interned(VF_CACHE cache, void *key, int key_len)
/* [<][>][^][v][top][bottom][index][help] */
241 {
242 int h;
243 VF_CACHE_ELEM ce, ce0;
244
245 h = c_hash(cache, key, key_len);
246 ce0 = &cache->hash_table[h];
247 for (ce = ce0->h_forw; ce != ce0; ce = ce->h_forw){
248 if ((ce->key_len == key_len) && (memcmp(ce->key, key, key_len) == 0)){
249 if (ce != ce0->h_forw){
250 c_hash_unintern(cache, ce);
251 c_hash_intern(cache, ce, NULL, h); /* MAGIC */
252 }
253 return ce;
254 }
255 }
256 return NULL;
257 }
258
259 Private void
260 c_hash_intern (VF_CACHE cache, VF_CACHE_ELEM ce, void *key, int key_len)
/* [<][>][^][v][top][bottom][index][help] */
261 {
262 int h;
263 VF_CACHE_ELEM ce1;
264
265 if (key == NULL) /* MAGIC */
266 h = key_len;
267 else
268 h = c_hash(cache, key, key_len);
269 ce1 = cache->hash_table[h].h_forw;
270 cache->hash_table[h].h_forw = ce;
271 ce->h_forw = ce1;
272 ce1->h_back = ce;
273 ce->h_back = &cache->hash_table[h];
274 }
275
276 Private void
277 c_hash_unintern(VF_CACHE cache, VF_CACHE_ELEM ce)
/* [<][>][^][v][top][bottom][index][help] */
278 {
279 VF_CACHE_ELEM ce_b, ce_f;
280
281 ce_b = ce->h_back;
282 ce_f = ce->h_forw;
283 ce_b->h_forw = ce_f;
284 ce_f->h_back = ce_b;
285 }
286
287
288
289 /**
290 ** HASH TABLE
291 **
292 ** 1. A hash table object is created by the following function:
293 ** FUNC: vf_hash_create(int hash_size)
294 ** --- Caller must specify the size of hash table. This hash object
295 ** uses `chaining' to store data objects: the hash table can store
296 ** any number of data objects (more than hash_size).
297 ** 2. A data object is stored in hash table by the PUT method.
298 ** FUNC: (HASH_OBJ->put)(HASH_OBJ, DATA_OBJ, KEY, KEY_LENGTH)
299 ** --- A data object, DATA_OBJ, is stored with specifying its
300 ** KEY and KEY_LENGTH, the length (in byte) of the KEY.
301 ** This method does not return any value. If the same data object
302 ** in the sense of KEY and KEY_LENGTH exists in the HASH_OBJ,
303 ** the object is not newly interned and link count is increased.
304 ** 3. Stored data object is extracted by the GET method.
305 ** FUNC: (TABLE_OBJ->get)(HASH, KEY, KEY_ID)
306 ** --- This extracts a data object whose key and key length matches
307 ** KEY and KEY_LENGTH. If NULL is returned, it implies that
308 ** such data is not interned.
309 ** 4. Stored data object can be deleted from the hash table by DEL method.
310 ** FUNC: (TABLE_OBJ->del)(HASH_OBJ, KEY, KEY_ID)
311 ** --- This delets a data object whose key and key length matches
312 ** KEY and KEY_LENGTH. If its link count is more than one,
313 ** the link count is decremented by one and the object is not
314 ** deleted.
315 **/
316 Private void* h_hash_put_object(VF_HASH,void*,void*,int);
317 Private void* h_hash_get_object(VF_HASH,void*,int);
318 Private void h_hash_del_object(VF_HASH,void*,int);
319 Private int h_hash(VF_HASH,void*,int);
320 Private void h_hash_intern(VF_HASH,VF_HASH_ELEM,void*,int);
321 Private void h_hash_unintern(VF_HASH,VF_HASH_ELEM);
322
323 /* vf_hash_create()
324 * --- Creates a hash table object.
325 */
326 Public VF_HASH
327 vf_hash_create (int hash_size)
/* [<][>][^][v][top][bottom][index][help] */
328 {
329 int i;
330 VF_HASH hash;
331
332 if ((hash_size < 1)
333 || ((hash = (VF_HASH)calloc(1, sizeof(struct s_vf_hash))) == NULL))
334 return NULL;
335 hash->table = (VF_HASH_ELEM)calloc(hash_size, sizeof(struct s_vf_hash_elem));
336 if (hash->table == NULL){
337 vf_free(hash);
338 return NULL;
339 }
340
341 hash->hash_size = hash_size;
342 hash->put = h_hash_put_object;
343 hash->get = h_hash_get_object;
344 hash->del = h_hash_del_object;
345 for (i = 0; i < hash_size; i++){
346 hash->table[i].h_forw = &hash->table[i];
347 hash->table[i].h_back = &hash->table[i];
348 }
349 return hash;
350 }
351
352 Private void*
353 h_hash_get_object(VF_HASH hash, void *key, int key_len)
/* [<][>][^][v][top][bottom][index][help] */
354 {
355 int h;
356 VF_HASH_ELEM he, he0;
357
358 h = h_hash(hash, key, key_len);
359 he0 = &hash->table[h];
360 for (he = he0->h_forw; he != he0; he = he->h_forw)
361 if ((he->key_len == key_len) && (memcmp(he->key, key, key_len) == 0)){
362 if (he != he0->h_forw){ /* move top if it is not top */
363 h_hash_unintern(hash, he);
364 h_hash_intern(hash, he, NULL, h); /* MAGIC */
365 }
366 return he->object;
367 }
368 return NULL;
369 }
370
371 Private void*
372 h_hash_put_object(VF_HASH hash, void* object, void *key, int key_len)
/* [<][>][^][v][top][bottom][index][help] */
373 {
374 VF_HASH_ELEM he;
375 void *key2;
376
377 if ((he = h_hash_get_object(hash, key, key_len)) != NULL){
378 ++he->link_cnt;
379 return he->object;
380 }
381
382 he = (VF_HASH_ELEM)calloc(1, sizeof(struct s_vf_hash_elem));
383 key2 = calloc(1, key_len);
384 if ((he == NULL) || (key2 == NULL))
385 return NULL;
386 memcpy(key2, key, key_len);
387 he->link_cnt = 1;
388 he->object = object;
389 he->key = key2;
390 he->key_len = key_len;
391 h_hash_intern(hash, he, key2, key_len);
392 return he->object;
393 }
394
395 Private void
396 h_hash_del_object(VF_HASH hash, void *key, int key_len)
/* [<][>][^][v][top][bottom][index][help] */
397 {
398 VF_HASH_ELEM he;
399
400 if ((he = h_hash_get_object(hash, key, key_len)) == NULL)
401 return; /* not interned */
402
403 if (--he->link_cnt > 0)
404 return;
405
406 h_hash_unintern(hash, he);
407 if (he->key != NULL)
408 vf_free(he->key);
409 vf_free(he);
410 }
411
412 Private void
413 h_hash_intern (VF_HASH hash, VF_HASH_ELEM he, void *key, int key_len)
/* [<][>][^][v][top][bottom][index][help] */
414 {
415 int h;
416 VF_HASH_ELEM he1;
417
418 if (key == NULL) /* MAGIC */
419 h = key_len;
420 else
421 h = h_hash(hash, key, key_len);
422 he1 = hash->table[h].h_forw;
423 hash->table[h].h_forw = he;
424 he->h_forw = he1;
425 he1->h_back = he;
426 he->h_back = &hash->table[h];
427 }
428
429 Private void
430 h_hash_unintern(VF_HASH hash, VF_HASH_ELEM he)
/* [<][>][^][v][top][bottom][index][help] */
431 {
432 VF_HASH_ELEM he_b, he_f;
433
434 he_b = he->h_back;
435 he_f = he->h_forw;
436 he_b->h_forw = he_f;
437 he_f->h_back = he_b;
438 }
439
440 Private int
441 h_hash(VF_HASH hash, void *key, int key_len)
/* [<][>][^][v][top][bottom][index][help] */
442 {
443 char *p;
444 int i;
445 unsigned int h;
446
447 h = 0;
448 for (i = 0, p = key; i < key_len; i++, p++)
449 h = h + (unsigned int)*p;
450 return (h % hash->hash_size);
451 }
452
453
454 /**
455 ** TABLE
456 **
457 ** 1. A table object is created by the following function:
458 ** FUNC: vf_table_create(void)
459 ** --- Table size is need not be specified. It autoatically
460 ** and dynammically allocates memory for table memory.
461 ** 2. A table object stores data object.
462 ** FUNC: (TABLE_OBJ->put_obj)(TABLE_OBJ, DATA_OBJ, KEY, KEY_LENGTH)
463 ** --- A data object, DATA_OBJ, is stored with specifying its
464 ** KEY and KEY_LENGTH, the length (in byte) of the KEY.
465 ** This method returns an ID (a non-negative integer) for the
466 ** DATA_OBJ. If -1 is returned, some error occured internnaly.
467 ** ID is used to extract DATA_OBJ. If the same data object
468 ** in the sense of KEY and KEY_LENGTH exists in the TABLE,
469 ** the object is not newly interned and link count is increased.
470 ** 3. Stored data object is extracted by two ways: by ID and by KEY.
471 ** 3.1 Data extraction by ID.
472 ** FUNC: (TABLE_OBJ->get_obj_by_id)(TABLE_OBJ, ID)
473 ** --- Extract a data object whose id is ID. If NULL is returned,
474 ** ID is wrong (i.e., such data is not interned).
475 ** 3.2 Data extraction by KEY.
476 ** FUNC: (TABLE_OBJ->get_obj_by_key)(TABLE_OBJ, KEY, KEY_LENGTH)
477 ** --- Extract a data object whose key and key length are KEY
478 ** and KEY_LENGTH. If NULL is returned, such data is not interned.
479 ** 4. Stored data object can be deleted from the table by two ways:
480 ** by ID and by KEY.
481 ** 4.1 Data deletion by ID.
482 ** FUNC: (TABLE_OBJ->del_obj_by_id)(TABLE_OBJ, ID)
483 ** --- Delete a data object from the TABLE whose id is ID. Precisely,
484 ** it decreases the link count of the data item. If it is
485 ** zero, the data object is deleted from the TABLE.
486 ** 4.2 Data deletion by KEY.
487 ** FUNC: (TABLE_OBJ->del_obj_by_key)(TABLE_OBJ, KEY, KEY_LENGTH)
488 ** --- Delete a data object whose key and key length are KEY
489 ** and KEY_LENGTH. Precisely, it decreases the link count
490 ** of the data item. If it is
491 ** zero, the data object is deleted from the TABLE.
492 ** 5. Obtaining data ID
493 ** 5.1 Obtain data ID by KEY and KEY_LENGTH.
494 ** FUNC: (TABLE_OBJ->get_id_by_key)(TABLE_OBJ, KEY, KEY_LENGTH)
495 ** --- Return an ID whose key and key length are KEY and KEY_LENGTH.
496 ** 5.2 Obtain data ID by DATA
497 ** FUNC: (TABLE_OBJ->get_id_by_obj)(TABLE_OBJ, DATA)
498 ** --- Return an ID for the DATA.
499 ** 6. Incrementing link count.
500 ** FUNC: (TABLE_OBJ->link_by_id)(TABLE_OBJ, ID)
501 ** --- Increment link count of an entry ID.
502 ** 7. Decrementing link count.
503 ** FUNC: (TABLE_OBJ->unlink_by_id)(TABLE_OBJ, ID)
504 ** --- Decrement link count of an entry ID. If link count becomes zero,
505 ** the entry is deleted from the table.
506 ** 8. The number of elements in the TABLE object can be checked.
507 ** FUNC: (TABLE_OBJ->get_nelements)(TABLE_OBJ)
508 ** --- Return the number of elements in the TABLE.
509 **
510 **/
511 Private int table_put_obj(VF_TABLE,void*,void*,int);
512 Private int table_put_obj2(VF_TABLE,void*,void*,int);
513 Private int table_get_id_by_key(VF_TABLE,void*,int);
514 Private int table_get_id_by_obj(VF_TABLE,void*);
515 Private void *table_get_obj_by_id(VF_TABLE,int);
516 Private void *table_get_obj_by_key(VF_TABLE,void*,int);
517 Private int table_del_obj_by_id(VF_TABLE,int);
518 Private int table_del_obj_by_key(VF_TABLE,void*,int);
519 Private int table_link_by_id(VF_TABLE,int);
520 Private int table_unlink_by_id(VF_TABLE,int);
521 Private int table_get_nelements(VF_TABLE);
522 #ifndef VF_INIT_TABLE_SIZE
523 # define VF_INIT_TABLE_SIZE 16
524 #endif/*VF_INIT_TABLE_SIZE*/
525
526 /* vf_table_create()
527 * --- Creates a table object.
528 */
529 Public VF_TABLE
530 vf_table_create (void)
/* [<][>][^][v][top][bottom][index][help] */
531 {
532 VF_TABLE table;
533
534 if (VF_INIT_TABLE_SIZE < 1){
535 fprintf(stderr, "Internal error: Initial # of elems for TABLE\n");
536 abort();
537 }
538 ALLOC_IF_ERR(table, struct s_vf_table)
539 return NULL;
540 table->put = table_put_obj;
541 table->put2 = table_put_obj2;
542 table->get_id_by_key = table_get_id_by_key;
543 table->get_id_by_obj = table_get_id_by_obj;
544 table->get_obj_by_id = table_get_obj_by_id;
545 table->get_obj_by_key = table_get_obj_by_key;
546 table->del_obj_by_id = table_del_obj_by_id;
547 table->del_obj_by_key = table_del_obj_by_key;
548 table->link_by_id = table_link_by_id;
549 table->unlink_by_id = table_unlink_by_id;
550 table->get_nelements = table_get_nelements;
551 table->nelems = 0;
552 table->next_slot = 0;
553 table->table_size = 0;
554 table->table = NULL;
555 return table;
556 }
557
558 Private int
559 table_put_obj(VF_TABLE table, void *object, void *key, int key_len)
/* [<][>][^][v][top][bottom][index][help] */
560 {
561 int id;
562 VF_TABLE_ELEM te;
563
564 if ((id = table_get_id_by_key(table, key, key_len)) >= 0){
565 te = &table->table[id];
566 ++te->link_cnt;
567 return id;
568 }
569
570 return table_put_obj2(table, object, key, key_len);
571 }
572
573 Private int
574 table_put_obj2(VF_TABLE table, void *object, void *key, int key_len)
/* [<][>][^][v][top][bottom][index][help] */
575 {
576 int id, idz, new_table_size, i;
577 VF_TABLE_ELEM new_table;
578 void *key2;
579
580 if (table->nelems == table->table_size){ /* realloc */
581 if (table->table_size == 0)
582 new_table_size = VF_INIT_TABLE_SIZE;
583 else
584 new_table_size = 2 * table->table_size;
585 ALLOCN_IF_ERR(new_table, struct s_vf_table_elem, new_table_size){
586 return -1;
587 }
588 for (i = 0; i < table->table_size; i++){
589 new_table[i].link_cnt = table->table[i].link_cnt;
590 new_table[i].object = table->table[i].object;
591 new_table[i].key = table->table[i].key;
592 new_table[i].key_len = table->table[i].key_len;
593 }
594 for (i = table->table_size; i < new_table_size; i++){
595 new_table[i].link_cnt = 0;
596 new_table[i].object = NULL;
597 new_table[i].key = NULL;
598 new_table[i].key_len = 0;
599 }
600 table->next_slot = table->table_size; /* possibly, free slot */
601 table->table_size = new_table_size;
602 if (table->table != NULL)
603 vf_free(table->table);
604 table->table = new_table;
605 }
606
607 id = idz = table->next_slot;
608 do {
609 if ((table->table[id].object == NULL) && (table->table[id].key == NULL)
610 && (table->table[id].key_len == 0)){
611 if ((key2 = malloc(key_len)) == NULL)
612 return -1;
613 memcpy(key2, key, key_len);
614 table->table[id].link_cnt = 1;
615 table->table[id].object = object;
616 table->table[id].key = key2;
617 table->table[id].key_len = key_len;
618 table->next_slot = (id + 1) % table->table_size;
619 ++table->nelems;
620 return id;
621 }
622 id = (id + 1) % table->table_size;
623 } while (id != idz);
624
625 fprintf(stderr, "Cannot happen in table_put_obj()\n");
626 abort();
627 return -1;
628 }
629
630 Private int
631 table_get_id_by_key(VF_TABLE table, void *key, int key_len)
/* [<][>][^][v][top][bottom][index][help] */
632 {
633 int id;
634 VF_TABLE_ELEM te;
635
636 for (id = 0; id < table->table_size; id++){
637 te = &table->table[id];
638 if ((te->object == NULL) && (te->key == NULL) && (te->key_len == 0))
639 continue;
640 if ((te->key_len == key_len) && (memcmp(te->key, key, key_len) == 0))
641 return id;
642 }
643 return -1;
644 }
645
646 Private int
647 table_get_id_by_obj(VF_TABLE table, void *obj)
/* [<][>][^][v][top][bottom][index][help] */
648 {
649 int id;
650 VF_TABLE_ELEM te;
651
652 if (obj == NULL)
653 return -1;
654 for (id = 0; id < table->table_size; id++){
655 te = &table->table[id];
656 if (te->object == obj)
657 return id;
658 }
659 return -1;
660 }
661
662 Private void*
663 table_get_obj_by_id(VF_TABLE table, int id)
/* [<][>][^][v][top][bottom][index][help] */
664 {
665 if ((id < 0) && (table->table_size <= id))
666 return NULL;
667 if (table->table == NULL)
668 return NULL;
669 return table->table[id].object;
670 }
671
672 Private void*
673 table_get_obj_by_key(VF_TABLE table, void *key, int key_len)
/* [<][>][^][v][top][bottom][index][help] */
674 {
675 int id;
676
677 if ((id = table_get_id_by_key(table, key, key_len)) < 0)
678 return NULL;
679 return table->table[id].object;
680 }
681
682 Private int
683 table_del_obj_by_id(VF_TABLE table, int id)
/* [<][>][^][v][top][bottom][index][help] */
684 {
685 --table->table[id].link_cnt;
686 if (table->table[id].link_cnt > 0)
687 return table->table[id].link_cnt;
688
689 --table->nelems;
690 if (table->table[id].key != NULL)
691 vf_free(table->table[id].key);
692 table->table[id].object = NULL;
693 table->table[id].key = NULL;
694 table->table[id].key_len = 0;
695 table->table[id].link_cnt = 0;
696
697 return table->table[id].link_cnt;
698 }
699
700 Private int
701 table_del_obj_by_key(VF_TABLE table, void *key, int key_len)
/* [<][>][^][v][top][bottom][index][help] */
702 {
703 int id;
704
705 if ((id = table_get_id_by_key(table, key, key_len)) < 0)
706 return -1;
707 return table_del_obj_by_id(table, id);
708 }
709
710 Private int
711 table_link_by_id(VF_TABLE table, int id)
/* [<][>][^][v][top][bottom][index][help] */
712 {
713 table->table[id].link_cnt++;
714 return table->table[id].link_cnt;
715 }
716
717 Private int
718 table_unlink_by_id(VF_TABLE table, int id)
/* [<][>][^][v][top][bottom][index][help] */
719 {
720 --table->table[id].link_cnt;
721
722 if (table->table[id].link_cnt <= 0){
723 --table->nelems;
724 if (table->table[id].key != NULL)
725 vf_free(table->table[id].key);
726 table->table[id].object = NULL;
727 table->table[id].key = NULL;
728 table->table[id].key_len = 0;
729 table->table[id].link_cnt = 0;
730 return 0;
731 }
732
733 return table->table[id].link_cnt;
734 }
735
736 Private int
737 table_get_nelements(VF_TABLE table)
/* [<][>][^][v][top][bottom][index][help] */
738 {
739 return table->nelems;
740 }
741
742 /*EOF*/