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
25 #include "st-identity-hashtable.h"
27 #include "st-dictionary.h"
28 #include "st-universe.h"
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
;
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
58 i
= (st_detag_pointer (object
) - memory
->start
) & mask
;
61 if (ht
->table
[i
].object
== 0 || object
== ht
->table
[i
].object
)
63 i
= (i
+ ST_ADVANCE_SIZE
) & mask
;
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
76 i
= (st_detag_pointer (object
) - memory
->start
) & mask
;
79 if (ht
->table
[i
].object
== 0 || ht
->table
[i
].object
== (st_oop
) ht
)
81 i
= (i
+ ST_ADVANCE_SIZE
) & mask
;
86 identity_hashtable_check_grow (st_identity_hashtable
*ht
)
91 /* ensure table is at least half-full */
92 if ((ht
->size
+ ht
->deleted
) * 2 <= ht
->alloc
)
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
;
113 st_identity_hashtable_remove (st_identity_hashtable
*ht
, st_oop object
)
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;
125 st_assert_not_reached ();
130 st_identity_hashtable_hash (st_identity_hashtable
*ht
, st_oop object
)
132 /* assigns an identity hash for an object
136 index
= identity_hashtable_find (ht
, object
);
137 if (ht
->table
[index
].object
== 0) {
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
;
148 st_identity_hashtable_rehash_object (st_identity_hashtable
*ht
, st_oop old
, st_oop
new)
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;
160 index
= identity_hashtable_find_available_cell (ht
, new);
161 if (ht
->table
[index
].object
== (st_oop
) ht
)
163 ht
->table
[index
].object
= new;
164 ht
->table
[index
].hash
= hash
;