prism/util/pm_constant_pool.c

   1 #include "prism/util/pm_constant_pool.h"
   2
   3 /**
   4  * Initialize a list of constant ids.
   5  */
   6 void
   7 pm_constant_id_list_init(pm_constant_id_list_t *list) {
   8     list->ids = NULL;
   9     list->size = 0;
  10     list->capacity = 0;
  11 }
  12
  13 /**
  14  * Initialize a list of constant ids with a given capacity.
  15  */
  16 void
  17 pm_constant_id_list_init_capacity(pm_constant_id_list_t *list, size_t capacity) {
  18     if (capacity) {
  19         list->ids = xcalloc(capacity, sizeof(pm_constant_id_t));
  20         if (list->ids == NULL) abort();
  21     } else {
  22         list->ids = NULL;
  23     }
  24
  25     list->size = 0;
  26     list->capacity = capacity;
  27 }
  28
  29 /**
  30  * Append a constant id to a list of constant ids. Returns false if any
  31  * potential reallocations fail.
  32  */
  33 bool
  34 pm_constant_id_list_append(pm_constant_id_list_t *list, pm_constant_id_t id) {
  35     if (list->size >= list->capacity) {
  36         list->capacity = list->capacity == 0 ? 8 : list->capacity * 2;
  37         list->ids = (pm_constant_id_t *) xrealloc(list->ids, sizeof(pm_constant_id_t) * list->capacity);
  38         if (list->ids == NULL) return false;
  39     }
  40
  41     list->ids[list->size++] = id;
  42     return true;
  43 }
  44
  45 /**
  46  * Insert a constant id into a list of constant ids at the specified index.
  47  */
  48 void
  49 pm_constant_id_list_insert(pm_constant_id_list_t *list, size_t index, pm_constant_id_t id) {
  50     assert(index < list->capacity);
  51     assert(list->ids[index] == PM_CONSTANT_ID_UNSET);
  52
  53     list->ids[index] = id;
  54     list->size++;
  55 }
  56
  57 /**
  58  * Checks if the current constant id list includes the given constant id.
  59  */
  60 bool
  61 pm_constant_id_list_includes(pm_constant_id_list_t *list, pm_constant_id_t id) {
  62     for (size_t index = 0; index < list->size; index++) {
  63         if (list->ids[index] == id) return true;
  64     }
  65     return false;
  66 }
  67
  68 /**
  69  * Free the memory associated with a list of constant ids.
  70  */
  71 void
  72 pm_constant_id_list_free(pm_constant_id_list_t *list) {
  73     if (list->ids != NULL) {
  74         xfree(list->ids);
  75     }
  76 }
  77
  78 /**
  79  * A relatively simple hash function (djb2) that is used to hash strings. We are
  80  * optimizing here for simplicity and speed.
  81  */
  82 static inline uint32_t
  83 pm_constant_pool_hash(const uint8_t *start, size_t length) {
  84     // This is a prime number used as the initial value for the hash function.
  85     uint32_t value = 5381;
  86
  87     for (size_t index = 0; index < length; index++) {
  88         value = ((value << 5) + value) + start[index];
  89     }
  90
  91     return value;
  92 }
  93
  94 /**
  95  * https://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2
  96  */
  97 static uint32_t
  98 next_power_of_two(uint32_t v) {
  99     // Avoid underflow in subtraction on next line.
 100     if (v == 0) {
 101         // 1 is the nearest power of 2 to 0 (2^0)
 102         return 1;
 103     }
 104     v--;
 105     v |= v >> 1;
 106     v |= v >> 2;
 107     v |= v >> 4;
 108     v |= v >> 8;
 109     v |= v >> 16;
 110     v++;
 111     return v;
 112 }
 113
 114 #ifndef NDEBUG
 115 static bool
 116 is_power_of_two(uint32_t size) {
 117     return (size & (size - 1)) == 0;
 118 }
 119 #endif
 120
 121 /**
 122  * Resize a constant pool to a given capacity.
 123  */
 124 static inline bool
 125 pm_constant_pool_resize(pm_constant_pool_t *pool) {
 126     assert(is_power_of_two(pool->capacity));
 127
 128     uint32_t next_capacity = pool->capacity * 2;
 129     if (next_capacity < pool->capacity) return false;
 130
 131     const uint32_t mask = next_capacity - 1;
 132     const size_t element_size = sizeof(pm_constant_pool_bucket_t) + sizeof(pm_constant_t);
 133
 134     void *next = xcalloc(next_capacity, element_size);
 135     if (next == NULL) return false;
 136
 137     pm_constant_pool_bucket_t *next_buckets = next;
 138     pm_constant_t *next_constants = (void *)(((char *) next) + next_capacity * sizeof(pm_constant_pool_bucket_t));
 139
 140     // For each bucket in the current constant pool, find the index in the
 141     // next constant pool, and insert it.
 142     for (uint32_t index = 0; index < pool->capacity; index++) {
 143         pm_constant_pool_bucket_t *bucket = &pool->buckets[index];
 144
 145         // If an id is set on this constant, then we know we have content here.
 146         // In this case we need to insert it into the next constant pool.
 147         if (bucket->id != PM_CONSTANT_ID_UNSET) {
 148             uint32_t next_index = bucket->hash & mask;
 149
 150             // This implements linear scanning to find the next available slot
 151             // in case this index is already taken. We don't need to bother
 152             // comparing the values since we know that the hash is unique.
 153             while (next_buckets[next_index].id != PM_CONSTANT_ID_UNSET) {
 154                 next_index = (next_index + 1) & mask;
 155             }
 156
 157             // Here we copy over the entire bucket, which includes the id so
 158             // that they are consistent between resizes.
 159             next_buckets[next_index] = *bucket;
 160         }
 161     }
 162
 163     // The constants are stable with respect to hash table resizes.
 164     memcpy(next_constants, pool->constants, pool->size * sizeof(pm_constant_t));
 165
 166     // pool->constants and pool->buckets are allocated out of the same chunk
 167     // of memory, with the buckets coming first.
 168     xfree(pool->buckets);
 169     pool->constants = next_constants;
 170     pool->buckets = next_buckets;
 171     pool->capacity = next_capacity;
 172     return true;
 173 }
 174
 175 /**
 176  * Initialize a new constant pool with a given capacity.
 177  */
 178 bool
 179 pm_constant_pool_init(pm_constant_pool_t *pool, uint32_t capacity) {
 180     const uint32_t maximum = (~((uint32_t) 0));
 181     if (capacity >= ((maximum / 2) + 1)) return false;
 182
 183     capacity = next_power_of_two(capacity);
 184     const size_t element_size = sizeof(pm_constant_pool_bucket_t) + sizeof(pm_constant_t);
 185     void *memory = xcalloc(capacity, element_size);
 186     if (memory == NULL) return false;
 187
 188     pool->buckets = memory;
 189     pool->constants = (void *)(((char *)memory) + capacity * sizeof(pm_constant_pool_bucket_t));
 190     pool->size = 0;
 191     pool->capacity = capacity;
 192     return true;
 193 }
 194
 195 /**
 196  * Return a pointer to the constant indicated by the given constant id.
 197  */
 198 pm_constant_t *
 199 pm_constant_pool_id_to_constant(const pm_constant_pool_t *pool, pm_constant_id_t constant_id) {
 200     assert(constant_id != PM_CONSTANT_ID_UNSET && constant_id <= pool->size);
 201     return &pool->constants[constant_id - 1];
 202 }
 203
 204 /**
 205  * Find a constant in a constant pool. Returns the id of the constant, or 0 if
 206  * the constant is not found.
 207  */
 208 pm_constant_id_t
 209 pm_constant_pool_find(const pm_constant_pool_t *pool, const uint8_t *start, size_t length) {
 210     assert(is_power_of_two(pool->capacity));
 211     const uint32_t mask = pool->capacity - 1;
 212
 213     uint32_t hash = pm_constant_pool_hash(start, length);
 214     uint32_t index = hash & mask;
 215     pm_constant_pool_bucket_t *bucket;
 216
 217     while (bucket = &pool->buckets[index], bucket->id != PM_CONSTANT_ID_UNSET) {
 218         pm_constant_t *constant = &pool->constants[bucket->id - 1];
 219         if ((constant->length == length) && memcmp(constant->start, start, length) == 0) {
 220             return bucket->id;
 221         }
 222
 223         index = (index + 1) & mask;
 224     }
 225
 226     return PM_CONSTANT_ID_UNSET;
 227 }
 228
 229 /**
 230  * Insert a constant into a constant pool and return its index in the pool.
 231  */
 232 static inline pm_constant_id_t
 233 pm_constant_pool_insert(pm_constant_pool_t *pool, const uint8_t *start, size_t length, pm_constant_pool_bucket_type_t type) {
 234     if (pool->size >= (pool->capacity / 4 * 3)) {
 235         if (!pm_constant_pool_resize(pool)) return PM_CONSTANT_ID_UNSET;
 236     }
 237
 238     assert(is_power_of_two(pool->capacity));
 239     const uint32_t mask = pool->capacity - 1;
 240
 241     uint32_t hash = pm_constant_pool_hash(start, length);
 242     uint32_t index = hash & mask;
 243     pm_constant_pool_bucket_t *bucket;
 244
 245     while (bucket = &pool->buckets[index], bucket->id != PM_CONSTANT_ID_UNSET) {
 246         // If there is a collision, then we need to check if the content is the
 247         // same as the content we are trying to insert. If it is, then we can
 248         // return the id of the existing constant.
 249         pm_constant_t *constant = &pool->constants[bucket->id - 1];
 250
 251         if ((constant->length == length) && memcmp(constant->start, start, length) == 0) {
 252             // Since we have found a match, we need to check if this is
 253             // attempting to insert a shared or an owned constant. We want to
 254             // prefer shared constants since they don't require allocations.
 255             if (type == PM_CONSTANT_POOL_BUCKET_OWNED) {
 256                 // If we're attempting to insert an owned constant and we have
 257                 // an existing constant, then either way we don't want the given
 258                 // memory. Either it's duplicated with the existing constant or
 259                 // it's not necessary because we have a shared version.
 260                 xfree((void *) start);
 261             } else if (bucket->type == PM_CONSTANT_POOL_BUCKET_OWNED) {
 262                 // If we're attempting to insert a shared constant and the
 263                 // existing constant is owned, then we can free the owned
 264                 // constant and replace it with the shared constant.
 265                 xfree((void *) constant->start);
 266                 constant->start = start;
 267                 bucket->type = (unsigned int) (PM_CONSTANT_POOL_BUCKET_DEFAULT & 0x3);
 268             }
 269
 270             return bucket->id;
 271         }
 272
 273         index = (index + 1) & mask;
 274     }
 275
 276     // IDs are allocated starting at 1, since the value 0 denotes a non-existent
 277     // constant.
 278     uint32_t id = ++pool->size;
 279     assert(pool->size < ((uint32_t) (1 << 30)));
 280
 281     *bucket = (pm_constant_pool_bucket_t) {
 282         .id = (unsigned int) (id & 0x3fffffff),
 283         .type = (unsigned int) (type & 0x3),
 284         .hash = hash
 285     };
 286
 287     pool->constants[id - 1] = (pm_constant_t) {
 288         .start = start,
 289         .length = length,
 290     };
 291
 292     return id;
 293 }
 294
 295 /**
 296  * Insert a constant into a constant pool. Returns the id of the constant, or
 297  * PM_CONSTANT_ID_UNSET if any potential calls to resize fail.
 298  */
 299 pm_constant_id_t
 300 pm_constant_pool_insert_shared(pm_constant_pool_t *pool, const uint8_t *start, size_t length) {
 301     return pm_constant_pool_insert(pool, start, length, PM_CONSTANT_POOL_BUCKET_DEFAULT);
 302 }
 303
 304 /**
 305  * Insert a constant into a constant pool from memory that is now owned by the
 306  * constant pool. Returns the id of the constant, or PM_CONSTANT_ID_UNSET if any
 307  * potential calls to resize fail.
 308  */
 309 pm_constant_id_t
 310 pm_constant_pool_insert_owned(pm_constant_pool_t *pool, uint8_t *start, size_t length) {
 311     return pm_constant_pool_insert(pool, start, length, PM_CONSTANT_POOL_BUCKET_OWNED);
 312 }
 313
 314 /**
 315  * Insert a constant into a constant pool from memory that is constant. Returns
 316  * the id of the constant, or PM_CONSTANT_ID_UNSET if any potential calls to
 317  * resize fail.
 318  */
 319 pm_constant_id_t
 320 pm_constant_pool_insert_constant(pm_constant_pool_t *pool, const uint8_t *start, size_t length) {
 321     return pm_constant_pool_insert(pool, start, length, PM_CONSTANT_POOL_BUCKET_CONSTANT);
 322 }
 323
 324 /**
 325  * Free the memory associated with a constant pool.
 326  */
 327 void
 328 pm_constant_pool_free(pm_constant_pool_t *pool) {
 329     // For each constant in the current constant pool, free the contents if the
 330     // contents are owned.
 331     for (uint32_t index = 0; index < pool->capacity; index++) {
 332         pm_constant_pool_bucket_t *bucket = &pool->buckets[index];
 333
 334         // If an id is set on this constant, then we know we have content here.
 335         if (bucket->id != PM_CONSTANT_ID_UNSET && bucket->type == PM_CONSTANT_POOL_BUCKET_OWNED) {
 336             pm_constant_t *constant = &pool->constants[bucket->id - 1];
 337             xfree((void *) constant->start);
 338         }
 339     }
 340
 341     xfree(pool->buckets);
 342 }