src/st-dictionary.c

   1 /*
   2  * st-hashed-collection.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-dictionary.h"
  26 #include "st-array.h"
  27 #include "st-small-integer.h"
  28 #include "st-utils.h"
  29 #include "st-universe.h"
  30 #include "st-association.h"
  31 #include "st-object.h"
  32 #include "st-behavior.h"
  33
  34 #define DEFAULT_CAPACITY     8
  35 #define MINIMUM_CAPACITY     4
  36 #define SIZE(collection)     (ST_HASHED_COLLECTION (collection)->size)
  37 #define DELETED(collection)  (ST_HASHED_COLLECTION (collection)->deleted)
  38 #define ARRAY(collection)    (ST_HASHED_COLLECTION (collection)->array)
  39 #define ARRAY_SIZE(array)    (st_smi_value (ST_ARRAYED_OBJECT (array)->size))
  40
  41 // prime number - 1
  42 #define ADVANCE_SIZE         106720
  43
  44 #define ST_HASHED_COLLECTION(oop) ((struct st_hashed_collection *) ST_POINTER (oop))
  45
  46 struct st_hashed_collection
  47 {
  48     struct st_header header;
  49
  50     st_oop size;
  51     st_oop deleted;
  52     st_oop array;
  53
  54 };
  55
  56 static st_uint  dict_find (st_oop dict, st_oop object);
  57 static st_uint  set_find  (st_oop set, st_oop object);
  58 static void     dict_no_check_add    (st_oop dict, st_oop object);
  59 static void     set_no_check_add     (st_oop set, st_oop object);
  60
  61
  62
  63 /* Common methods */
  64
  65 static inline st_uint
  66 occupied (st_oop collection)
  67 {
  68     return st_smi_value (SIZE (collection)) + st_smi_value (DELETED (collection));
  69 }
  70
  71 static st_uint
  72 size_for_capacity (st_uint capacity)
  73 {
  74     st_uint size;
  75
  76     size = MINIMUM_CAPACITY;
  77
  78     while (size < capacity)
  79         size = size + size;
  80
  81     return size;
  82 }
  83
  84 static void
  85 initialize (st_oop collection, int capacity)
  86 {
  87     st_assert (capacity > 0);
  88
  89     capacity = size_for_capacity (capacity);
  90
  91     SIZE (collection) = st_smi_new (0);
  92     DELETED (collection) = st_smi_new (0);
  93     ARRAY (collection) = st_object_new_arrayed (ST_ARRAY_CLASS, capacity);
  94 }
  95
  96 static void
  97 dict_check_grow (st_oop dict)
  98 {
  99     st_oop  old, object;
 100     st_uint size, n;
 101
 102     size = n = ARRAY_SIZE (ARRAY (dict));
 103
 104     if (occupied (dict) * 2 <= size)
 105         return;
 106
 107     size *= 2;
 108     old = ARRAY (dict);
 109     ARRAY (dict)   = st_object_new_arrayed (ST_ARRAY_CLASS, size);
 110     DELETED (dict) = st_smi_new (0);
 111
 112     for (st_uint i = 1; i <= n; i++) {
 113         object = st_array_at (old, i);
 114         if (object != ST_NIL) {
 115             st_array_at_put (ARRAY (dict), dict_find (dict, ST_ASSOCIATION_KEY (object)), object);
 116         }
 117     }
 118 }
 119
 120 static st_uint
 121 dict_find (st_oop dict, st_oop key)
 122 {
 123     st_oop el;
 124     st_uint mask;
 125     st_uint i;
 126
 127     mask = ARRAY_SIZE (ARRAY (dict)) - 1;
 128     i = (st_object_hash (key) & mask) + 1;
 129
 130     while (true) {
 131         el = st_array_at (ARRAY (dict), i);
 132         if (el == ST_NIL || key == ST_ASSOCIATION_KEY (el))
 133             return i;
 134         i = ((i + ADVANCE_SIZE) & mask) + 1;
 135     }
 136 }
 137
 138 void
 139 st_dictionary_at_put (st_oop dict, st_oop key, st_oop value)
 140 {
 141     st_uint index;
 142     st_oop  assoc;
 143
 144     index = dict_find (dict, key);
 145     assoc = st_array_at (ARRAY (dict), index);
 146
 147     if (assoc == ST_NIL) {
 148         st_array_at_put (ARRAY (dict), index, st_association_new (key, value));
 149         SIZE (dict) = st_smi_increment (SIZE (dict));
 150         dict_check_grow (dict);
 151     } else {
 152         ST_ASSOCIATION_VALUE (assoc) = value;
 153     }
 154 }
 155
 156 st_oop
 157 st_dictionary_at (st_oop dict, st_oop key)
 158 {
 159     int index;
 160     st_oop assoc;
 161
 162     assoc = st_array_at (ARRAY (dict), dict_find (dict, key));
 163
 164     if (assoc != ST_NIL)
 165         return ST_ASSOCIATION_VALUE (assoc);
 166
 167     return ST_NIL;
 168 }
 169
 170 st_oop
 171 st_dictionary_association_at (st_oop dict, st_oop key)
 172 {
 173     return st_array_at (ARRAY (dict), dict_find (dict, key));
 174 }
 175
 176 st_oop
 177 st_dictionary_new (void)
 178 {
 179     return st_dictionary_new_with_capacity (DEFAULT_CAPACITY);
 180 }
 181
 182 st_oop
 183 st_dictionary_new_with_capacity (int capacity)
 184 {
 185     st_oop dict;
 186
 187     dict = st_object_new (ST_DICTIONARY_CLASS);
 188     initialize (dict, capacity);
 189
 190     return dict;
 191 }
 192
 193
 194 /* Set implementation */
 195
 196 static st_uint
 197 set_find_cstring (st_oop set, const char *string)
 198 {
 199     st_oop el;
 200     st_uint mask, i;
 201
 202     mask = ARRAY_SIZE (ARRAY (set)) - 1;
 203     i = (st_string_hash (string) & mask) + 1;
 204
 205     while (true) {
 206         el = st_array_at (ARRAY (set), i);
 207         if (el == ST_NIL || (strcmp (st_byte_array_bytes (el), string) == 0))
 208             return i;
 209         i = ((i + ADVANCE_SIZE) & mask) + 1;
 210     }
 211 }
 212
 213 static st_uint
 214 set_find (st_oop set, st_oop object)
 215 {
 216     st_oop el;
 217     st_uint mask, i;
 218
 219     mask = ARRAY_SIZE (ARRAY (set)) - 1;
 220     i = (st_object_hash (object) & mask) + 1;
 221
 222     while (true) {
 223         el = st_array_at (ARRAY (set), i);
 224         if (el == ST_NIL || el == object)
 225             return i;
 226         i = ((i + ADVANCE_SIZE) & mask) + 1;
 227     }
 228 }
 229
 230 static void
 231 set_check_grow (st_oop set)
 232 {
 233     st_oop  old, object;
 234     st_uint size, n;
 235
 236     size = n = ARRAY_SIZE (ARRAY (set));
 237
 238     if (occupied (set) * 2 <= size)
 239         return;
 240
 241     size *= 2;
 242     old = ARRAY (set);
 243     ARRAY (set)   = st_object_new_arrayed (ST_ARRAY_CLASS, size);
 244     DELETED (set) = st_smi_new (0);
 245
 246     for (st_uint i = 1; i <= n; i++) {
 247         object = st_array_at (old, i);
 248         if (object != ST_NIL)
 249             st_array_at_put (ARRAY (set), set_find (set, object), object);
 250     }
 251 }
 252
 253 st_oop
 254 st_set_intern_cstring (st_oop set, const char *string)
 255 {
 256     st_oop  intern;
 257     st_uint i, len;
 258
 259     st_assert (string != NULL);
 260
 261     i = set_find_cstring (set, string);
 262     intern = st_array_at (ARRAY (set), i);
 263     if (intern != ST_NIL)
 264         return intern;
 265
 266     len = strlen (string);
 267     intern = st_object_new_arrayed (ST_SYMBOL_CLASS, len);
 268     memcpy (st_byte_array_bytes (intern), string, len);
 269     st_array_at_put (ARRAY (set), i, intern);
 270     SIZE (set) = st_smi_increment (SIZE (set));
 271     set_check_grow (set);
 272
 273     return intern;
 274 }
 275
 276 void
 277 st_set_add (st_oop set, st_oop object)
 278 {
 279     st_array_at_put (ARRAY (set), set_find (set, object), object);
 280     SIZE (set) = st_smi_increment (SIZE (set));
 281     set_check_grow (set);
 282 }
 283
 284 bool
 285 st_set_includes (st_oop set, st_oop object)
 286 {
 287     return st_array_at (ARRAY (set), set_find (set, object)) != ST_NIL;
 288 }
 289
 290 st_oop
 291 st_set_like (st_oop set, st_oop object)
 292 {
 293     return st_array_at (ARRAY (set), set_find (set, object));
 294 }
 295
 296 st_oop
 297 st_set_new_with_capacity (int capacity)
 298 {
 299     st_oop set;
 300
 301     set = st_object_new (ST_SET_CLASS);
 302     initialize (set, capacity);
 303
 304     return set;
 305 }
 306
 307 st_oop
 308 st_set_new (void)
 309 {
 310     return st_set_new_with_capacity (DEFAULT_CAPACITY);
 311 }