src/st-identity-hashtable.c

   1 /*
   2  * st-identity-hashtable.c
   3  *
   4  * Copyright (C) 2008 Vincent Geddes
   5  *
   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:
  12  *
  13  * The above copyright notice and this permission notice shall be included in
  14  * all copies or substantial portions of the Software.
  15  *
  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.
  23  */
  24
  25 #include "st-identity-hashtable.h"
  26 #include "st-utils.h"
  27 #include "st-dictionary.h"
  28 #include "st-universe.h"
  29
  30 // power of 2
  31 #define INITIAL_CAPACITY 256
  32
  33
  34 st_identity_hashtable *
  35 st_identity_hashtable_new (void)
  36 {
  37     st_identity_hashtable *ht;
  38
  39     ht = st_new (st_identity_hashtable);
  40
  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;
  46
  47     return ht;
  48 }
  49
  50 static st_uint
  51 identity_hashtable_find (st_identity_hashtable *ht, st_oop object)
  52 {
  53     /* use this probing function to find an object which may already be stored somewhere in table
  54      */
  55     st_uint mask, i;
  56
  57     mask = ht->alloc - 1;
  58     i = (st_detag_pointer (object) - memory->start) & mask;
  59
  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;
  64     }
  65 }
  66
  67
  68 static st_uint
  69 identity_hashtable_find_available_cell (st_identity_hashtable *ht, st_oop object)
  70 {
  71     /* use this probing function to find a place to insert object
  72      */
  73     st_uint mask, i;
  74
  75     mask = ht->alloc - 1;
  76     i = (st_detag_pointer (object) - memory->start) & mask;
  77
  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;
  82     }
  83 }
  84
  85 static void
  86 identity_hashtable_check_grow (st_identity_hashtable *ht)
  87 {
  88     st_uint alloc, index;
  89     struct cell *table;
  90
  91     /* ensure table is at least half-full */
  92     if ((ht->size + ht->deleted) * 2 <= ht->alloc)
  93         return;
  94
  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);
 100
 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;
 106         }
 107     }
 108
 109     st_free (table);
 110 }
 111
 112 void
 113 st_identity_hashtable_remove (st_identity_hashtable *ht, st_oop object)
 114 {
 115     st_uint index;
 116
 117     index = identity_hashtable_find (ht, object);
 118
 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 ();
 126     }
 127 }
 128
 129 st_uint
 130 st_identity_hashtable_hash (st_identity_hashtable *ht, st_oop object)
 131 {
 132     /* assigns an identity hash for an object
 133      */
 134     st_uint index;
 135
 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);
 142     }
 143
 144     return ht->table[index].hash;
 145 }
 146
 147 void
 148 st_identity_hashtable_rehash_object (st_identity_hashtable *ht, st_oop old, st_oop new)
 149 {
 150     st_uint hash, index;
 151
 152     index = identity_hashtable_find (ht, old);
 153     st_assert (ht->table[index].object != 0);
 154
 155     hash = ht->table[index].hash;
 156     ht->table[index].object = (st_oop) ht;
 157     ht->table[index].hash   = 0;
 158     ht->deleted++;
 159
 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;
 165 }