1#include "prism/internal/constant_pool.h"
5#include "prism/internal/arena.h"
6#include "prism/internal/assert.h"
60 PRISM_ASSERT(index < list->capacity);
61 PRISM_ASSERT(list->
ids[index] == PM_CONSTANT_ID_UNSET);
63 list->
ids[index] = id;
73 PRISM_ASSERT(set->capacity != 0);
75 size_t mask = set->capacity - 1;
76 size_t index = ((size_t) pm_constant_id_hash(
id)) & mask;
78 while (set->ids[index] != PM_CONSTANT_ID_UNSET && set->ids[index] !=
id) {
79 index = (index + 1) & mask;
91 PRISM_ASSERT(
id != PM_CONSTANT_ID_UNSET);
97 if (set->size >= (set->capacity / 4 * 3)) {
98 size_t capacity = set->capacity == 0 ? 8 : set->capacity * 2;
101 .capacity = capacity,
105 for (
size_t index = 0; index < set->capacity; index++) {
107 if (moved != PM_CONSTANT_ID_UNSET) grown.ids[pm_constant_id_set_slot(&grown, moved)] = moved;
113 size_t index = pm_constant_id_set_slot(set,
id);
114 if (set->ids[index] ==
id)
return false;
116 set->ids[index] = id;
129pm_constant_pool_hash(
const uint8_t *start,
size_t length) {
133 static const uint64_t secret = 0x517cc1b727220a95ULL;
134 uint64_t hash = (uint64_t) length;
141 memcpy(&a, start, 4);
142 memcpy(&b, start + length - 4, 4);
143 hash ^= (uint64_t) a | ((uint64_t) b << 32);
144 }
else if (length > 0) {
145 hash ^= (uint64_t) start[0] | ((uint64_t) start[length >> 1] << 8) | ((uint64_t) start[length - 1] << 16);
148 }
else if (length <= 16) {
152 memcpy(&word, start, 8);
155 memcpy(&word, start + length - 8, 8);
159 const uint8_t *ptr = start;
160 size_t remaining = length;
162 while (remaining >= 8) {
164 memcpy(&word, ptr, 8);
174 memcpy(&word, start + length - 8, 8);
181 return (uint32_t) hash;
188next_power_of_two(uint32_t v) {
209 uint32_t next_capacity = pool->capacity * 2;
210 const uint32_t mask = next_capacity - 1;
217 for (uint32_t index = 0; index < pool->capacity; index++) {
222 if (bucket->id != PM_CONSTANT_ID_UNSET) {
223 uint32_t next_index = bucket->hash & mask;
228 while (next_buckets[next_index].
id != PM_CONSTANT_ID_UNSET) {
229 next_index = (next_index + 1) & mask;
234 next_buckets[next_index] = *bucket;
239 memcpy(next_constants, pool->constants, pool->size *
sizeof(
pm_constant_t));
241 pool->constants = next_constants;
242 pool->buckets = next_buckets;
243 pool->capacity = next_capacity;
251 capacity = next_power_of_two(capacity);
256 pool->capacity = capacity;
264 PRISM_ASSERT(constant_id != PM_CONSTANT_ID_UNSET && constant_id <= pool->size);
265 return &pool->constants[constant_id - 1];
273pm_constant_pool_find(
const pm_constant_pool_t *pool,
const uint8_t *start,
size_t length) {
274 const uint32_t mask = pool->capacity - 1;
276 uint32_t hash = pm_constant_pool_hash(start, length);
277 uint32_t index = hash & mask;
280 while (bucket = &pool->buckets[index], bucket->id != PM_CONSTANT_ID_UNSET) {
283 if ((bucket->hash == hash) && (bucket->length == length) && memcmp(bucket->start, start, length) == 0) {
287 index = (index + 1) & mask;
290 return PM_CONSTANT_ID_UNSET;
297pm_constant_pool_insert(
pm_arena_t *arena,
pm_constant_pool_t *pool,
const uint8_t *start,
size_t length, pm_constant_pool_bucket_type_t type) {
298 if (pool->size >= (pool->capacity / 4 * 3)) {
299 pm_constant_pool_resize(arena, pool);
302 const uint32_t mask = pool->capacity - 1;
304 uint32_t hash = pm_constant_pool_hash(start, length);
305 uint32_t index = hash & mask;
308 while (bucket = &pool->buckets[index], bucket->id != PM_CONSTANT_ID_UNSET) {
313 if ((bucket->hash == hash) && (bucket->length == length) && memcmp(bucket->start, start, length) == 0) {
317 if (type != PM_CONSTANT_POOL_BUCKET_OWNED && bucket->type == PM_CONSTANT_POOL_BUCKET_OWNED) {
321 bucket->start = start;
322 bucket->type = (
unsigned int) (type & 0x3);
323 pool->constants[bucket->id - 1].start = start;
329 index = (index + 1) & mask;
334 uint32_t
id = ++pool->size;
335 PRISM_ASSERT(pool->size < ((uint32_t) (1 << 30)));
338 .id = (
unsigned int) (
id & 0x3fffffff),
339 .type = (
unsigned int) (type & 0x3),
359 return pm_constant_pool_insert(arena, pool, start, length, PM_CONSTANT_POOL_BUCKET_DEFAULT);
369 return pm_constant_pool_insert(arena, pool, start, length, PM_CONSTANT_POOL_BUCKET_OWNED);
379 return pm_constant_pool_insert(arena, pool, start, length, PM_CONSTANT_POOL_BUCKET_CONSTANT);
387 return constant->start;
394 return constant->length;
#define PRISM_ALIGNOF
Get the alignment requirement of a type.
uint32_t pm_constant_id_t
A constant id is a unique identifier for a constant in the constant pool.
#define PRISM_INLINE
Old Visual Studio versions do not support the inline keyword, so we need to define it to be __inline.
C99 shim for <stdbool.h>.
size_t size
The number of constant ids in the list.
size_t capacity
The number of constant ids that have been allocated in the list.
pm_constant_id_t * ids
The constant ids in the list.