Home My Page Projects Code Snippets Project Openings SML/NJ
Summary Activity Forums Tracker Lists Tasks Docs Surveys News SCM Files

SCM Repository

[smlnj] Annotation of /sml/trunk/src/runtime/gc/addr-hash.c
ViewVC logotype

Annotation of /sml/trunk/src/runtime/gc/addr-hash.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 651 - (view) (download) (as text)

1 : monnier 249 /* addr-hash.c
2 :     *
3 :     * COPYRIGHT (c) 1993 by AT&T Bell Laboratories.
4 :     *
5 :     * Hash tables for mapping addresses to objects.
6 :     */
7 :    
8 :     #include "ml-base.h"
9 :     #include "addr-hash.h"
10 :    
11 :     typedef struct item { /* items in the hash table */
12 :     Addr_t addr; /* the address the object is keyed on */
13 :     void *obj; /* the object */
14 :     struct item *next; /* the next item in the bucket */
15 :     } item_t;
16 :    
17 :     struct addr_tbl {
18 :     int ignoreBits;
19 :     int size;
20 :     int numItems;
21 :     Addr_t mask;
22 :     item_t **buckets;
23 :     };
24 :    
25 :     #define HASH(tbl,addr) (((addr) >> (tbl)->ignoreBits) & (tbl)->mask)
26 :    
27 :     /* MakeAddrTbl:
28 :     *
29 :     * Allocate an address hash table.
30 :     */
31 :     addr_tbl_t *MakeAddrTbl (int ignoreBits, int size)
32 :     {
33 :     unsigned int nBuckets;
34 :     int i;
35 :     addr_tbl_t *tbl;
36 :    
37 :     /* find smallest power of 2 (but at least 16) that is greater than size */
38 :     for (nBuckets = 16; nBuckets < size; nBuckets <<= 1)
39 :     continue;
40 :    
41 :     tbl = NEW_OBJ(addr_tbl_t);
42 :     tbl->buckets = NEW_VEC(item_t *, nBuckets);
43 :     tbl->ignoreBits = ignoreBits;
44 :     tbl->size = nBuckets;
45 :     tbl->mask = nBuckets-1;
46 :     tbl->numItems = 0;
47 :     for (i = 0; i < nBuckets; i++)
48 :     tbl->buckets[i] = NIL(item_t *);
49 :    
50 :     return tbl;
51 :    
52 :     } /* end of MakeAddrTbl */
53 :    
54 :     /* AddrTblInsert:
55 :     *
56 :     * Insert an object into a address hash table.
57 :     */
58 :     void AddrTblInsert (addr_tbl_t *tbl, Addr_t addr, void *obj)
59 :     {
60 :     int h = HASH(tbl,addr);
61 :     item_t *p;
62 :    
63 :     for (p = tbl->buckets[h]; (p != NIL(item_t *)) && (p->addr != addr); p = p->next)
64 :     continue;
65 :     if (p == NIL(item_t *)) {
66 :     p = NEW_OBJ(item_t);
67 :     p->addr = addr;
68 :     p->obj = obj;
69 :     p->next = tbl->buckets[h];
70 :     tbl->buckets[h] = p;
71 :     tbl->numItems++;
72 :     }
73 :     else if (p->obj != obj)
74 :     Die ("AddrTblInsert: %#x mapped to multiple objects", addr);
75 :    
76 :     } /* end of AddrTblInsert */
77 :    
78 :     /* AddrTblLookup:
79 :     *
80 :     * Return the object associated with the given address; return NIL, if not
81 :     * found.
82 :     */
83 :     void *AddrTblLookup (addr_tbl_t *tbl, Addr_t addr)
84 :     {
85 :     int h = HASH(tbl,addr);
86 :     item_t *p;
87 :    
88 :     for (p = tbl->buckets[h]; (p != NIL(item_t *)) && (p->addr != addr); p = p->next)
89 :     continue;
90 :    
91 :     if (p == NIL(item_t *))
92 :     return NIL(void *);
93 :     else
94 :     return p->obj;
95 :    
96 :     } /* end of AddrTblLookup */
97 :    
98 :     /* AddrTblApply:
99 :     *
100 :     * Apply the given function to the elements of the table.
101 :     */
102 :     void AddrTblApply (addr_tbl_t *tbl, void *clos, void (*f) (Addr_t, void *, void *))
103 :     {
104 :     int i;
105 :     item_t *p;
106 :    
107 :     for (i = 0; i < tbl->size; i++) {
108 :     for (p = tbl->buckets[i]; p != NIL(item_t *); p = p->next) {
109 :     (*f) (p->addr, clos, p->obj);
110 :     }
111 :     }
112 :    
113 :     } /* end of AddrTblApply */
114 :    
115 :     /* FreeAddrTbl:
116 :     *
117 :     * Deallocate the space for an address table; if freeObjs is true, also deallocate
118 :     * the objects.
119 :     */
120 :     void FreeAddrTbl (addr_tbl_t *tbl, bool_t freeObjs)
121 :     {
122 :     int i;
123 :     item_t *p, *q;
124 :    
125 :     for (i = 0; i < tbl->size; i++) {
126 :     for (p = tbl->buckets[i]; p != NIL(item_t *); ) {
127 :     q = p->next;
128 :     if (freeObjs)
129 :     FREE (p->obj);
130 :     FREE (p);
131 :     p = q;
132 :     }
133 :     }
134 :     FREE (tbl->buckets);
135 :     FREE (tbl);
136 :    
137 :     } /* end of FreeAddrTbl. */

root@smlnj-gforge.cs.uchicago.edu
ViewVC Help
Powered by ViewVC 1.0.0