← Back to branch summary

~ubuntu-branches/ubuntu/maverick/swig1.3/maverick

« back to all changes in this revision

Viewing changes to Source/DOH/Doh/hash.c

  • Committer: Bazaar Package Importer
  • Author(s): Torsten Landschoff
  • Date: 2002-03-29 01:56:07 UTC
  • Revision ID: james.westby@ubuntu.com-20020329015607-c0wt03xu8oy9ioj7
Tags: upstream-1.3.11
Import upstream version 1.3.11

Show diffs side-by-side

added added

removed removed

Lines of Context:
Source/DOH/Doh/hash.c
 
1
/* -----------------------------------------------------------------------------
 
2
 * hash.c
 
3
 *
 
4
 *     Implements a simple hash table object.
 
5
 *
 
6
 * Author(s) : David Beazley (beazley@cs.uchicago.edu)
 
7
 *
 
8
 * Copyright (C) 1999-2000.  The University of Chicago
 
9
 * See the file LICENSE for information on usage and redistribution.
 
10
 * ----------------------------------------------------------------------------- */
 
11
 
 
12
static char cvsroot[] = "$Header: /cvs/projects/SWIG/Source/DOH/Doh/hash.c,v 1.31.4.6 2001/12/03 15:39:33 beazley Exp $";
 
13
 
 
14
#include "dohint.h"
 
15
 
 
16
/* Hash node */
 
17
typedef struct HashNode {
 
18
    DOH                  *key;
 
19
    DOH                  *object;
 
20
    struct HashNode     *next;
 
21
} HashNode;
 
22
 
 
23
/* Hash object */
 
24
typedef struct Hash {
 
25
  DOH  *file;
 
26
  int   line;
 
27
  HashNode          **hashtable;
 
28
  int                 hashsize;
 
29
  int                 currentindex;
 
30
  int                 nitems;
 
31
  HashNode           *current;
 
32
} Hash;
 
33
 
 
34
/* Key interning structure */
 
35
typedef struct KeyValue {
 
36
    char   *cstr;
 
37
    DOH    *sstr;
 
38
    struct KeyValue *left;
 
39
    struct KeyValue *right;
 
40
} KeyValue;
 
41
 
 
42
static KeyValue *root = 0;
 
43
 
 
44
/* Find or create a key in the interned key table */
 
45
static DOH *find_key (DOH *doh_c) {
 
46
  char *c = (char *) doh_c;
 
47
  KeyValue *r, *s;
 
48
  int d = 0;
 
49
  /* OK, sure, we use a binary tree for maintaining interned
 
50
     symbols.  Then we use their hash values for accessing secondary
 
51
     hash tables. */     
 
52
  r = root;
 
53
  s = 0;
 
54
  while (r) {
 
55
    s = r;
 
56
    d = strcmp(r->cstr,c);
 
57
    if (d == 0) return r->sstr;
 
58
    if (d < 0) r = r->left;
 
59
    else r = r->right;
 
60
  }
 
61
  /*  fprintf(stderr,"Interning '%s'\n", c);*/
 
62
  r = (KeyValue *) DohMalloc(sizeof(KeyValue));
 
63
  r->cstr = (char *) DohMalloc(strlen(c)+1);
 
64
  strcpy(r->cstr,c);
 
65
  r->sstr = NewString(c);
 
66
  DohIntern(r->sstr);
 
67
  r->left = 0;
 
68
  r->right = 0;
 
69
  if (!s) { root = r; }
 
70
  else {
 
71
    if (d < 0) s->left = r;
 
72
    else s->right = r;
 
73
  }
 
74
  return r->sstr;
 
75
}
 
76
 
 
77
#define HASH_INIT_SIZE   7
 
78
 
 
79
/* Create a new hash node */
 
80
static HashNode *NewNode(DOH *k, void *obj) {
 
81
    HashNode *hn = (HashNode *) DohMalloc(sizeof(HashNode));
 
82
    hn->key = k;
 
83
    Incref(hn->key);
 
84
    hn->object = obj;
 
85
    Incref(obj);
 
86
    hn->next = 0;
 
87
    return hn;
 
88
}
 
89
 
 
90
/* Delete a hash node */
 
91
static void DelNode(HashNode *hn) {
 
92
    Delete(hn->key);
 
93
    Delete(hn->object);
 
94
    DohFree(hn);
 
95
}
 
96
 
 
97
/* -----------------------------------------------------------------------------
 
98
 * DelHash()
 
99
 *
 
100
 * Delete a hash table.
 
101
 * ----------------------------------------------------------------------------- */
 
102
 
 
103
static void
 
104
DelHash(DOH *ho) {
 
105
    Hash *h = (Hash *) ObjData(ho);
 
106
    HashNode *n,*next;
 
107
    int i;
 
108
 
 
109
    for (i = 0; i < h->hashsize; i++) {
 
110
        if ((n = h->hashtable[i])) {
 
111
            while (n) {
 
112
                next = n->next;
 
113
                DelNode(n);
 
114
                n = next;
 
115
            }
 
116
        }
 
117
    }
 
118
    DohFree(h->hashtable);
 
119
    h->hashtable = 0;
 
120
    h->hashsize = 0;
 
121
    DohFree(h);
 
122
}
 
123
 
 
124
/* -----------------------------------------------------------------------------
 
125
 * Hash_clear()
 
126
 *
 
127
 * Clear all of the entries in the hash table.
 
128
 * ----------------------------------------------------------------------------- */
 
129
 
 
130
static void
 
131
Hash_clear(DOH *ho) {
 
132
    Hash *h = (Hash *) ObjData(ho);
 
133
    HashNode *n,*next;
 
134
    int i;
 
135
 
 
136
    for (i = 0; i < h->hashsize; i++) {
 
137
        if ((n = h->hashtable[i])) {
 
138
            while (n) {
 
139
                next = n->next;
 
140
                DelNode(n);
 
141
                n = next;
 
142
            }
 
143
        }
 
144
        h->hashtable[i] = 0;
 
145
    }
 
146
    h->nitems = 0;
 
147
}
 
148
 
 
149
/* resize the hash table */
 
150
static void resize(Hash *h) {
 
151
    HashNode   *n, *next, **table;
 
152
    int         oldsize, newsize;
 
153
    int         i, p, hv;
 
154
 
 
155
    if (h->nitems < 2*h->hashsize) return;
 
156
 
 
157
    /* Too big. We have to rescale everything now */
 
158
    oldsize = h->hashsize;
 
159
 
 
160
    /* Calculate a new size */
 
161
    newsize = 2*oldsize+1;
 
162
    p = 3;
 
163
    while (p < (newsize >> 1)) {
 
164
        if (((newsize/p)*p) == newsize) {
 
165
            newsize+=2;
 
166
            p = 3;
 
167
            continue;
 
168
        }
 
169
        p = p + 2;
 
170
    }
 
171
 
 
172
    table = (HashNode **) DohMalloc(newsize*sizeof(HashNode *));
 
173
    for (i = 0; i < newsize; i++ ) {
 
174
        table[i] = 0;
 
175
    }
 
176
 
 
177
    /* Walk down the old set of nodes and re-place */
 
178
    h->hashsize = newsize;
 
179
    for (i = 0; i < oldsize; i++) {
 
180
        n = h->hashtable[i];
 
181
        while (n) {
 
182
            hv = Hashval(n->key) % newsize;
 
183
            next = n->next;
 
184
            n->next = table[hv];
 
185
            table[hv] = n;
 
186
            n = next;
 
187
        }
 
188
    }
 
189
    DohFree(h->hashtable);
 
190
    h->hashtable = table;
 
191
}
 
192
 
 
193
/* -----------------------------------------------------------------------------
 
194
 * Hash_setattr()
 
195
 *
 
196
 * Set an attribute in the hash table.  Deletes the existing entry if it already
 
197
 * exists.
 
198
 * ----------------------------------------------------------------------------- */
 
199
 
 
200
static int
 
201
Hash_setattr(DOH *ho, DOH *k, DOH *obj) {
 
202
    int hv;
 
203
    HashNode *n, *prev;
 
204
    Hash *h = (Hash *) ObjData(ho);
 
205
    
 
206
    if (!obj) {
 
207
      return DohDelattr(ho,k);
 
208
    }
 
209
    if (!DohCheck(k)) k = find_key(k);
 
210
    if (!DohCheck(obj)) {
 
211
      obj = NewString((char *) obj);
 
212
      Decref(obj);
 
213
    }
 
214
    hv = (Hashval(k)) % h->hashsize;
 
215
    n = h->hashtable[hv];
 
216
    prev = 0;
 
217
    while (n) {
 
218
      if (Cmp(n->key,k) == 0) {
 
219
        /* Node already exists.  Just replace its contents */
 
220
        if (n->object == obj) {
 
221
          /* Whoa. Same object.  Do nothing */
 
222
          return 1;
 
223
        }
 
224
        Delete(n->object);
 
225
        n->object = obj;
 
226
        Incref(obj);
 
227
        return 1;      /* Return 1 to indicate a replacement */
 
228
      } else {
 
229
        prev = n;
 
230
        n = n->next;
 
231
      }
 
232
    }
 
233
    /* Add this to the table */
 
234
    n = NewNode(k,obj);
 
235
    if (prev) prev->next = n;
 
236
    else h->hashtable[hv] = n;
 
237
    h->nitems++;
 
238
    resize(h);
 
239
    return 0;
 
240
}
 
241
 
 
242
/* -----------------------------------------------------------------------------
 
243
 * Hash_getattr()
 
244
 *
 
245
 * Get an attribute from the hash table. Returns 0 if it doesn't exist.
 
246
 * ----------------------------------------------------------------------------- */
 
247
 
 
248
static DOH *
 
249
Hash_getattr(DOH *ho, DOH *k) {
 
250
    int hv;
 
251
    HashNode *n;
 
252
    Hash *h = (Hash *) ObjData(ho);
 
253
 
 
254
    if (!DohCheck(k)) k = find_key(k);
 
255
    hv = Hashval(k) % h->hashsize;
 
256
    n = h->hashtable[hv];
 
257
    while (n) {
 
258
      if (Cmp(n->key, k) == 0) return n->object;
 
259
      n = n->next;
 
260
    }
 
261
    return 0;
 
262
}
 
263
 
 
264
/* -----------------------------------------------------------------------------
 
265
 * Hash_delattr()
 
266
 *
 
267
 * Delete an object from the hash table.
 
268
 * ----------------------------------------------------------------------------- */
 
269
 
 
270
static int
 
271
Hash_delattr(DOH *ho, DOH *k) {
 
272
    HashNode *n, *prev;
 
273
    int hv;
 
274
    Hash *h = (Hash *) ObjData(ho);
 
275
 
 
276
    if (!DohCheck(k)) k = find_key(k);
 
277
    hv = Hashval(k) % h->hashsize;
 
278
    n = h->hashtable[hv];
 
279
    prev = 0;
 
280
    while (n) {
 
281
        if (Cmp(n->key, k) == 0) {
 
282
            /* Found it, kill it */
 
283
 
 
284
            if (prev) {
 
285
                prev->next = n->next;
 
286
            } else {
 
287
                h->hashtable[hv] = n->next;
 
288
            }
 
289
            /* Need to check for iterator location */
 
290
            if (n == h->current) {
 
291
              h->current = prev;                   /* Move back to previous node.  When next is called, will move to next node */
 
292
              if (!h->current) h->currentindex--;  /* No previous node.  Move back one slot */
 
293
            }
 
294
            DelNode(n);
 
295
            h->nitems--;
 
296
            return 1;
 
297
        }
 
298
        prev = n;
 
299
        n = n->next;
 
300
    }
 
301
    return 0;
 
302
}
 
303
 
 
304
/* General purpose iterators */
 
305
static HashNode *
 
306
hash_first(DOH *ho) {
 
307
    Hash *h = (Hash *) ObjData(ho);
 
308
    h->currentindex = 0;
 
309
    h->current = 0;
 
310
    while ((h->currentindex < h->hashsize) && !h->hashtable[h->currentindex])
 
311
        h->currentindex++;
 
312
    if (h->currentindex >= h->hashsize) return 0;
 
313
    h->current = h->hashtable[h->currentindex];
 
314
    return h->current;
 
315
}
 
316
 
 
317
static HashNode *
 
318
hash_next(DOH *ho) {
 
319
    Hash *h = (Hash *) ObjData(ho);
 
320
    if (h->currentindex < 0) return hash_first(ho);
 
321
 
 
322
    /* Try to move to the next entry */
 
323
    if (h->current) {
 
324
      h->current = h->current->next;
 
325
    }
 
326
    if (h->current) {
 
327
        return h->current;
 
328
    }
 
329
    h->currentindex++;
 
330
    while ((h->currentindex < h->hashsize) && !h->hashtable[h->currentindex])
 
331
        h->currentindex++;
 
332
    if (h->currentindex >= h->hashsize) return 0;
 
333
    h->current = h->hashtable[h->currentindex];
 
334
    return h->current;
 
335
}
 
336
 
 
337
/* -----------------------------------------------------------------------------
 
338
 * Hash_firstkey()
 
339
 *
 
340
 * Return first hash-table key.
 
341
 * ----------------------------------------------------------------------------- */
 
342
 
 
343
static DOH *
 
344
Hash_firstkey(DOH *ho) {
 
345
    HashNode *hn = hash_first(ho);
 
346
    if (hn) return hn->key;
 
347
    return 0;
 
348
}
 
349
 
 
350
/* -----------------------------------------------------------------------------
 
351
 * Hash_nextkey()
 
352
 *
 
353
 * Return next hash table key.
 
354
 * ----------------------------------------------------------------------------- */
 
355
 
 
356
static DOH *
 
357
Hash_nextkey(DOH *ho) {
 
358
    HashNode *hn = hash_next(ho);
 
359
    if (hn) return hn->key;
 
360
    return 0;
 
361
}
 
362
 
 
363
/* -----------------------------------------------------------------------------
 
364
 * Hash_str()
 
365
 *
 
366
 * Create a string representation of a hash table (mainly for debugging).
 
367
 * ----------------------------------------------------------------------------- */
 
368
 
 
369
static DOH *
 
370
Hash_str(DOH *ho) {
 
371
    int i,j;
 
372
    HashNode *n;
 
373
    DOH *s;
 
374
    static int indent = 4;
 
375
    Hash *h = (Hash *) ObjData(ho);
 
376
 
 
377
    s = NewString("");
 
378
    if (ObjGetMark(ho)) {
 
379
      Printf(s,"Hash(0x%x)",ho);
 
380
      return s;
 
381
    }
 
382
    ObjSetMark(ho,1);
 
383
    Printf(s,"Hash {\n");
 
384
    for (i = 0; i < h->hashsize; i++) {
 
385
        n = h->hashtable[i];
 
386
        while (n) {
 
387
          for (j = 0; j < indent; j++) Putc(' ',s);
 
388
          indent+=4;
 
389
          Printf(s,"'%s' : %s, \n", n->key, n->object);
 
390
          indent-=4;
 
391
          n = n->next;
 
392
        }
 
393
    }
 
394
    for (j = 0; j < (indent-4); j++) Putc(' ',s);
 
395
    Printf(s,"}\n");
 
396
    ObjSetMark(ho,0);
 
397
    return s;
 
398
}
 
399
 
 
400
/* -----------------------------------------------------------------------------
 
401
 * Hash_len()
 
402
 *
 
403
 * Return number of entries in the hash table.
 
404
 * ----------------------------------------------------------------------------- */
 
405
 
 
406
static int
 
407
Hash_len(DOH *ho) {
 
408
  Hash *h = (Hash *) ObjData(ho);
 
409
  return h->nitems;
 
410
}
 
411
 
 
412
/* -----------------------------------------------------------------------------
 
413
 * Hash_keys(DOH *)
 
414
 *
 
415
 * Return a list of keys
 
416
 * ----------------------------------------------------------------------------- */
 
417
DOH *
 
418
Hash_keys(DOH *so) {
 
419
  DOH *keys;
 
420
  DOH *k;
 
421
 
 
422
  keys = NewList();
 
423
  k = Firstkey(so);
 
424
  while (k) {
 
425
    Append(keys,k);
 
426
    k = Nextkey(so);
 
427
  }
 
428
  /*   List_sort(keys); */
 
429
  return keys;
 
430
}
 
431
 
 
432
/* -----------------------------------------------------------------------------
 
433
 * CopyHash()
 
434
 *
 
435
 * Make a copy of a hash table.  Note: this is a shallow copy.
 
436
 * ----------------------------------------------------------------------------- */
 
437
 
 
438
static DOH *
 
439
CopyHash(DOH *ho) {
 
440
    Hash *h, *nh;
 
441
    HashNode *n;
 
442
    DOH *nho;
 
443
    
 
444
    int   i;
 
445
    h = (Hash *) ObjData(ho);
 
446
    nh = (Hash *) DohMalloc(sizeof(Hash));
 
447
    nh->hashsize = h->hashsize;
 
448
    nh->hashtable = (HashNode **) DohMalloc(nh->hashsize*sizeof(HashNode *));
 
449
    for (i = 0; i < nh->hashsize; i++) {
 
450
        nh->hashtable[i] = 0;
 
451
    }
 
452
    nh->currentindex = -1;
 
453
    nh->current = 0;
 
454
    nh->nitems = 0;
 
455
    nh->line = h->line;
 
456
    nh->file = h->file;
 
457
    if (nh->file) Incref(nh->file);
 
458
 
 
459
    nho = DohObjMalloc(DOHTYPE_HASH, nh);
 
460
    for (i = 0; i < h->hashsize; i++) {
 
461
        if ((n = h->hashtable[i])) {
 
462
            while (n) {
 
463
                Hash_setattr(nho, n->key, n->object);
 
464
                n = n->next;
 
465
            }
 
466
        }
 
467
    }
 
468
    return nho;
 
469
}
 
470
 
 
471
 
 
472
 
 
473
void Hash_setfile(DOH *ho, DOH *file) {
 
474
  DOH *fo;
 
475
  Hash *h = (Hash *) ObjData(ho);
 
476
 
 
477
  if (!DohCheck(file)) {
 
478
    fo = NewString(file);
 
479
    Decref(fo);
 
480
  } else fo = file;
 
481
  Incref(fo);
 
482
  Delete(h->file);
 
483
  h->file = fo;
 
484
}
 
485
 
 
486
DOH *Hash_getfile(DOH *ho) {
 
487
  Hash *h = (Hash *) ObjData(ho);
 
488
  return h->file;
 
489
}
 
490
 
 
491
void Hash_setline(DOH *ho, int line) {
 
492
  Hash *h = (Hash *) ObjData(ho);
 
493
  h->line = line;
 
494
}
 
495
 
 
496
int Hash_getline(DOH *ho) {
 
497
  Hash *h = (Hash *) ObjData(ho);
 
498
  return h->line;
 
499
}
 
500
 
 
501
/* -----------------------------------------------------------------------------
 
502
 * type information
 
503
 * ----------------------------------------------------------------------------- */
 
504
 
 
505
static DohHashMethods HashHashMethods = {
 
506
  Hash_getattr,
 
507
  Hash_setattr,
 
508
  Hash_delattr,
 
509
  Hash_firstkey,
 
510
  Hash_nextkey,
 
511
};
 
512
 
 
513
static DohObjInfo HashType = {
 
514
    "Hash",          /* objname */
 
515
    DelHash,         /* doh_del */
 
516
    CopyHash,        /* doh_copy */
 
517
    Hash_clear,      /* doh_clear */
 
518
    Hash_str,        /* doh_str */
 
519
    0,               /* doh_data */
 
520
    0,               /* doh_dump */
 
521
    Hash_len,        /* doh_len */
 
522
    0,               /* doh_hash    */
 
523
    0,               /* doh_cmp */
 
524
    Hash_setfile,               /* doh_setfile */
 
525
    Hash_getfile,               /* doh_getfile */
 
526
    Hash_setline,               /* doh_setline */
 
527
    Hash_getline,               /* doh_getline */
 
528
    &HashHashMethods, /* doh_mapping */
 
529
    0,                /* doh_sequence */
 
530
    0,                /* doh_file */
 
531
    0,                /* doh_string */
 
532
    0,                /* doh_positional */
 
533
    0,
 
534
};
 
535
 
 
536
/* -----------------------------------------------------------------------------
 
537
 * NewHash()
 
538
 *
 
539
 * Create a new hash table.
 
540
 * ----------------------------------------------------------------------------- */
 
541
 
 
542
DOH *
 
543
NewHash() {
 
544
    Hash *h;
 
545
    int   i;
 
546
    static int init = 0;
 
547
    if (!init) {
 
548
      DohRegisterType(DOHTYPE_HASH, &HashType);
 
549
      init = 1;
 
550
    }
 
551
    h = (Hash *) DohMalloc(sizeof(Hash));
 
552
    h->hashsize = HASH_INIT_SIZE;
 
553
    h->hashtable = (HashNode **) DohMalloc(h->hashsize*sizeof(HashNode *));
 
554
    for (i = 0; i < h->hashsize; i++) {
 
555
        h->hashtable[i] = 0;
 
556
    }
 
557
    h->currentindex = -1;
 
558
    h->current = 0;
 
559
    h->nitems = 0;
 
560
    h->file = 0;
 
561
    h->line = 0;
 
562
    return DohObjMalloc(DOHTYPE_HASH,h);
 
563
}