← Back to branch summary

~ubuntu-branches/ubuntu/precise/vflib3/precise

« back to all changes in this revision

Viewing changes to src/cache.c

  • Committer: Bazaar Package Importer
  • Author(s): Masayuki Hatta
  • Date: 2002-04-15 12:10:24 UTC
  • Revision ID: james.westby@ubuntu.com-20020415121024-cann32wucyfbq22f
Tags: upstream-3.6.12
Import upstream version 3.6.12

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/cache.c
 
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, 
 
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)
 
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)
 
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) 
 
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)
 
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)
 
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 
 
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)
 
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)
 
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)
 
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)
 
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)
 
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)
 
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)
 
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)
 
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)
 
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)
 
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)
 
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)
 
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)
 
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)
 
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)
 
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)
 
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)
 
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)
 
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)
 
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)
 
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)
 
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)
 
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)
 
738
{
 
739
  return table->nelems;
 
740
}
 
741
 
 
742
/*EOF*/