src/st-hashed-collection.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-hashed-collection.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     5
  35 #define TALLY(collection)    (ST_HASHED_COLLECTION (collection)->tally)
  36 #define ARRAY(collection)    (ST_HASHED_COLLECTION (collection)->array)
  37 #define ARRAY_SIZE(array)    (st_smi_value (ST_ARRAYED_OBJECT (array)->size))
  38
  39 #define ST_HASHED_COLLECTION(oop) ((struct st_hashed_collection *) ST_POINTER (oop))
  40
  41 struct st_hashed_collection
  42 {
  43     struct st_header header;
  44
  45     st_oop tally;
  46     st_oop array;
  47
  48 };
  49
  50 static st_smi  dict_scan_for_object (st_oop dict, st_oop object);
  51
  52 static void    dict_no_check_add    (st_oop dict, st_oop object);
  53
  54 static void    set_no_check_add     (st_oop set, st_oop object);
  55
  56 static st_smi  set_scan_for_object  (st_oop set, st_oop object);
  57
  58
  59 /* Hashed Collection methods */
  60
  61 static st_smi
  62 collection_find_element_or_nil (st_oop collection, st_oop object)
  63 {
  64     st_smi index;
  65
  66     if (st_object_class (collection) == st_dictionary_class)
  67         index = dict_scan_for_object (collection, object);
  68     else if (st_object_class (collection) == st_set_class)
  69         index = set_scan_for_object (collection, object);
  70     else
  71         st_assert_not_reached ();
  72
  73     if (index > 0)
  74         return index;
  75
  76     st_assert_not_reached ();
  77 }
  78
  79 static st_smi
  80 collection_grow_size (st_oop collection)
  81 {
  82     return MAX (ARRAY_SIZE (ARRAY (collection)), 2);
  83 }
  84
  85 static void
  86 collection_grow (st_oop collection)
  87 {
  88     st_oop old_array = ARRAY (collection);
  89
  90     st_smi new_size = ARRAY_SIZE (old_array) + collection_grow_size (collection);
  91
  92     ARRAY (collection) = st_object_new_arrayed (st_array_class, new_size);
  93
  94     st_smi n = ARRAY_SIZE (old_array);
  95
  96     for (st_smi i = 1; i <= n; i++)
  97         if (st_array_at (old_array, i) != st_nil) {
  98
  99             if (st_object_class (collection) == st_dictionary_class) {
 100                 dict_no_check_add (collection, st_array_at (old_array, i));
 101             } else if (st_object_class (collection) == st_set_class) {
 102                 set_no_check_add (collection, st_array_at (old_array, i));
 103             } else {
 104                 st_assert_not_reached ();
 105             }
 106         }
 107 }
 108
 109 static void
 110 collection_full_check (st_oop collection)
 111 {
 112     st_smi array_size = ARRAY_SIZE (ARRAY (collection));
 113     st_smi tally = st_smi_value (TALLY (collection));
 114
 115     if ((array_size - tally) < MAX ((array_size / 4), 1))
 116         collection_grow (collection);
 117 }
 118
 119 static void
 120 collection_at_new_index_put (st_oop collection, st_smi index, st_oop object)
 121 {
 122     st_array_at_put (ARRAY (collection), index, object);
 123
 124     TALLY (collection) = st_smi_increment (TALLY (collection));
 125
 126     collection_full_check (collection);
 127 }
 128
 129 static void
 130 collection_initialize (st_oop collection, st_smi capacity)
 131 {
 132     st_assert (capacity > 0);
 133
 134     TALLY (collection) = st_smi_new (0);
 135     ARRAY (collection) = st_object_new_arrayed (st_array_class, capacity);
 136 }
 137
 138 static st_smi
 139 dict_scan_for_object (st_oop dict, st_oop object)
 140 {
 141     st_smi finish = ARRAY_SIZE (ARRAY (dict));
 142     st_smi start = (st_object_hash (object) % finish) + 1;
 143
 144     for (st_smi i = start; i <= finish; i++) {
 145
 146         st_oop element = st_array_at (ARRAY (dict), i);
 147
 148         if (element == st_nil)
 149             return i;
 150         if (st_object_equal (object, ST_ASSOCIATION_KEY (element)))
 151             return i;
 152     }
 153
 154     for (st_smi i = 1; i <= (start - 1); i++) {
 155
 156         st_oop element = st_array_at (ARRAY (dict), i);
 157
 158         if (element == st_nil)
 159             return i;
 160         if (st_object_equal (object, ST_ASSOCIATION_KEY (element)))
 161             return i;
 162
 163     }
 164
 165     return 0;
 166 }
 167
 168 static void
 169 dict_no_check_add (st_oop dict, st_oop object)
 170 {
 171     st_array_at_put (ARRAY (dict),
 172                      collection_find_element_or_nil (dict, ST_ASSOCIATION_KEY (object)), object);
 173 }
 174
 175 void
 176 st_dictionary_at_put (st_oop dict, st_oop key, st_oop value)
 177 {
 178     st_smi index = collection_find_element_or_nil (dict, key);
 179
 180     st_oop assoc = st_array_at (ARRAY (dict), index);
 181
 182     if (assoc == st_nil) {
 183
 184         assoc = st_association_new (key, value);
 185         collection_at_new_index_put (dict, index, assoc);
 186
 187     } else {
 188         ST_ASSOCIATION (assoc)->value = value;
 189     }
 190 }
 191
 192 st_oop
 193 st_dictionary_at (st_oop dict, st_oop key)
 194 {
 195     st_smi index = collection_find_element_or_nil (dict, key);
 196
 197     st_oop assoc = st_array_at (ARRAY (dict), index);
 198
 199     if (assoc != st_nil)
 200         return ST_ASSOCIATION (assoc)->value;
 201
 202     return st_nil;
 203 }
 204
 205 st_oop
 206 st_dictionary_association_at (st_oop dict, st_oop key)
 207 {
 208     st_smi index = collection_find_element_or_nil (dict, key);
 209
 210     return st_array_at (ARRAY (dict), index);
 211 }
 212
 213 st_oop
 214 st_dictionary_new (void)
 215 {
 216     return st_dictionary_new_with_capacity (DEFAULT_CAPACITY);
 217 }
 218
 219 st_oop
 220 st_dictionary_new_with_capacity (st_smi capacity)
 221 {
 222     st_oop dict;
 223
 224     dict = st_object_new (st_dictionary_class);
 225
 226     collection_initialize (dict, capacity);
 227
 228     return dict;
 229 }
 230
 231 static st_smi
 232 set_scan_for_object (st_oop set, st_oop object)
 233 {
 234     st_smi finish = ARRAY_SIZE (ARRAY (set));
 235     st_smi start = (st_object_hash (object) % finish) + 1;
 236
 237     for (st_smi i = start; i <= finish; i++) {
 238
 239         st_oop element = st_array_at (ARRAY (set), i);
 240
 241         if (element == st_nil)
 242             return i;
 243         if (st_object_equal (object, element))
 244             return i;
 245     }
 246
 247     for (st_smi i = 1; i <= (start - 1); i++) {
 248
 249         st_oop element = st_array_at (ARRAY (set), i);
 250
 251         if (element == st_nil)
 252             return i;
 253         if (st_object_equal (object, element))
 254             return i;
 255
 256     }
 257
 258     return 0;
 259 }
 260
 261 static void
 262 set_no_check_add (st_oop set, st_oop object)
 263 {
 264     st_array_at_put (ARRAY (set), collection_find_element_or_nil (set, object), object);
 265 }
 266
 267 void
 268 st_set_add (st_oop set, st_oop object)
 269 {
 270     st_smi index = collection_find_element_or_nil (set, object);
 271
 272     st_oop element = st_array_at (ARRAY (set), index);
 273
 274     if (element == st_nil)
 275         collection_at_new_index_put (set, index, object);
 276 }
 277
 278 bool
 279 st_set_includes (st_oop set, st_oop object)
 280 {
 281     st_smi index = collection_find_element_or_nil (set, object);
 282
 283     return st_array_at (ARRAY (set), index) != st_nil;
 284 }
 285
 286 st_oop
 287 st_set_like (st_oop set, st_oop object)
 288 {
 289     st_smi index = collection_find_element_or_nil (set, object);
 290
 291     return st_array_at (ARRAY (set), index);
 292 }
 293
 294 st_oop
 295 st_set_new_with_capacity (st_smi capacity)
 296 {
 297     st_oop set;
 298
 299     set = st_object_new (st_set_class);
 300
 301     collection_initialize (set, capacity);
 302
 303     return set;
 304 }
 305
 306 st_oop
 307 st_set_new (void)
 308 {
 309     return st_set_new_with_capacity (DEFAULT_CAPACITY);
 310 }