Speed up method lookup. Replaced tagging/detagging macros with
[panda.git] / src / st-identity-hashtable.c
blob0360d761a6c52f4746014c0d83736ebf7c53138c
1 /*
2 * st-identity-hashtable.c
4 * Copyright (C) 2008 Vincent Geddes
6 * Permission is hereby granted, free of charge, to any person obtaining a copy
7 * of this software and associated documentation files (the "Software"), to deal
8 * in the Software without restriction, including without limitation the rights
9 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
10 * copies of the Software, and to permit persons to whom the Software is
11 * furnished to do so, subject to the following conditions:
13 * The above copyright notice and this permission notice shall be included in
14 * all copies or substantial portions of the Software.
16 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
19 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
21 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
22 * THE SOFTWARE.
25 #include "st-identity-hashtable.h"
26 #include "st-utils.h"
27 #include "st-dictionary.h"
28 #include "st-universe.h"
30 // power of 2
31 #define INITIAL_CAPACITY 256
34 st_identity_hashtable *
35 st_identity_hashtable_new (void)
37 st_identity_hashtable *ht;
39 ht = st_new (st_identity_hashtable);
41 ht->table = st_malloc0 (sizeof (struct cell) * INITIAL_CAPACITY);
42 ht->alloc = INITIAL_CAPACITY;
43 ht->size = 0;
44 ht->deleted = 0;
45 ht->current_hash = 0;
47 return ht;
50 static st_uint
51 identity_hashtable_find (st_identity_hashtable *ht, st_oop object)
53 /* use this probing function to find an object which may already be stored somewhere in table
55 st_uint mask, i;
57 mask = ht->alloc - 1;
58 i = (st_detag_pointer (object) - memory->start) & mask;
60 while (true) {
61 if (ht->table[i].object == 0 || object == ht->table[i].object)
62 return i;
63 i = (i + ST_ADVANCE_SIZE) & mask;
68 static st_uint
69 identity_hashtable_find_available_cell (st_identity_hashtable *ht, st_oop object)
71 /* use this probing function to find a place to insert object
73 st_uint mask, i;
75 mask = ht->alloc - 1;
76 i = (st_detag_pointer (object) - memory->start) & mask;
78 while (true) {
79 if (ht->table[i].object == 0 || ht->table[i].object == (st_oop) ht)
80 return i;
81 i = (i + ST_ADVANCE_SIZE) & mask;
85 static void
86 identity_hashtable_check_grow (st_identity_hashtable *ht)
88 st_uint alloc, index;
89 struct cell *table;
91 /* ensure table is at least half-full */
92 if ((ht->size + ht->deleted) * 2 <= ht->alloc)
93 return;
95 alloc = ht->alloc;
96 table = ht->table;
97 ht->alloc *= 2;
98 ht->deleted = 0;
99 ht->table = st_malloc0 (sizeof (struct cell) * ht->alloc);
101 for (st_uint i = 0; i <= alloc; i++) {
102 if (table[i].object != 0 && (table[i].object != (st_oop) ht)) {
103 index = identity_hashtable_find_available_cell (ht, table[i].object);
104 ht->table[index].object = table[i].object;
105 ht->table[index].hash = table[i].hash;
109 st_free (table);
112 void
113 st_identity_hashtable_remove (st_identity_hashtable *ht, st_oop object)
115 st_uint index;
117 index = identity_hashtable_find (ht, object);
119 if (ht->table[index].object != 0) {
120 ht->table[index].object = (st_oop) ht;
121 ht->table[index].hash = 0;
122 ht->size--;
123 ht->deleted++;
124 } else {
125 st_assert_not_reached ();
129 st_uint
130 st_identity_hashtable_hash (st_identity_hashtable *ht, st_oop object)
132 /* assigns an identity hash for an object
134 st_uint index;
136 index = identity_hashtable_find (ht, object);
137 if (ht->table[index].object == 0) {
138 ht->size++;
139 ht->table[index].object = object;
140 ht->table[index].hash = ht->current_hash++;
141 identity_hashtable_check_grow (ht);
144 return ht->table[index].hash;
147 void
148 st_identity_hashtable_rehash_object (st_identity_hashtable *ht, st_oop old, st_oop new)
150 st_uint hash, index;
152 index = identity_hashtable_find (ht, old);
153 st_assert (ht->table[index].object != 0);
155 hash = ht->table[index].hash;
156 ht->table[index].object = (st_oop) ht;
157 ht->table[index].hash = 0;
158 ht->deleted++;
160 index = identity_hashtable_find_available_cell (ht, new);
161 if (ht->table[index].object == (st_oop) ht)
162 ht->deleted--;
163 ht->table[index].object = new;
164 ht->table[index].hash = hash;