summaryrefslogtreecommitdiff
path: root/libguile/whippet/src/address-set.h
diff options
context:
space:
mode:
Diffstat (limited to 'libguile/whippet/src/address-set.h')
-rw-r--r--libguile/whippet/src/address-set.h214
1 files changed, 214 insertions, 0 deletions
diff --git a/libguile/whippet/src/address-set.h b/libguile/whippet/src/address-set.h
new file mode 100644
index 000000000..b1c27fa41
--- /dev/null
+++ b/libguile/whippet/src/address-set.h
@@ -0,0 +1,214 @@
+#ifndef ADDRESS_SET_H
+#define ADDRESS_SET_H
+
+#include <malloc.h>
+#include <stdint.h>
+#include <string.h>
+
+#include "address-hash.h"
+#include "gc-assert.h"
+
+struct hash_set {
+ uintptr_t *data;
+ size_t size; // total number of slots
+ size_t n_items; // number of items in set
+ uint8_t *bits; // bitvector indicating set slots
+};
+
+static void hash_set_clear(struct hash_set *set) {
+ memset(set->bits, 0, set->size / 8);
+ set->n_items = 0;
+}
+
+// Size must be a power of 2.
+static void hash_set_init(struct hash_set *set, size_t size) {
+ set->size = size;
+ set->data = malloc(sizeof(uintptr_t) * size);
+ if (!set->data) GC_CRASH();
+ set->bits = malloc(size / 8);
+ if (!set->bits) GC_CRASH();
+ hash_set_clear(set);
+}
+static void hash_set_destroy(struct hash_set *set) {
+ free(set->data);
+ free(set->bits);
+}
+
+static size_t hash_set_slot_index(struct hash_set *set, size_t idx) {
+ return idx & (set->size - 1);
+}
+static int hash_set_slot_is_empty(struct hash_set *set, size_t idx) {
+ idx = hash_set_slot_index(set, idx);
+ return (set->bits[idx / 8] & (1 << (idx % 8))) == 0;
+}
+static uintptr_t hash_set_slot_ref(struct hash_set *set, size_t idx) {
+ return set->data[hash_set_slot_index(set, idx)];
+}
+static void hash_set_slot_set(struct hash_set *set, size_t idx, uintptr_t v) {
+ set->data[hash_set_slot_index(set, idx)] = v;
+}
+static void hash_set_slot_acquire(struct hash_set *set, size_t idx) {
+ idx = hash_set_slot_index(set, idx);
+ set->bits[idx / 8] |= (1 << (idx % 8));
+ set->n_items++;
+}
+static void hash_set_slot_release(struct hash_set *set, size_t idx) {
+ idx = hash_set_slot_index(set, idx);
+ set->bits[idx / 8] &= ~(1 << (idx % 8));
+ set->n_items--;
+}
+static size_t hash_set_slot_distance(struct hash_set *set, size_t idx) {
+ return hash_set_slot_index(set, idx - hash_set_slot_ref(set, idx));
+}
+static int hash_set_should_shrink(struct hash_set *set) {
+ return set->size > 8 && set->n_items <= (set->size >> 3);
+}
+static int hash_set_should_grow(struct hash_set *set) {
+ return set->n_items >= set->size - (set->size >> 3);
+}
+
+static void hash_set_do_insert(struct hash_set *set, uintptr_t v) {
+ size_t displacement = 0;
+ while (!hash_set_slot_is_empty(set, v + displacement)
+ && displacement < hash_set_slot_distance(set, v + displacement))
+ displacement++;
+ while (!hash_set_slot_is_empty(set, v + displacement)
+ && displacement == hash_set_slot_distance(set, v + displacement)) {
+ if (hash_set_slot_ref(set, v + displacement) == v)
+ return;
+ displacement++;
+ }
+ size_t idx = v + displacement;
+ size_t slots_to_move = 0;
+ while (!hash_set_slot_is_empty(set, idx + slots_to_move))
+ slots_to_move++;
+ hash_set_slot_acquire(set, idx + slots_to_move);
+ while (slots_to_move--)
+ hash_set_slot_set(set, idx + slots_to_move + 1,
+ hash_set_slot_ref(set, idx + slots_to_move));
+ hash_set_slot_set(set, idx, v);
+}
+
+static void hash_set_populate(struct hash_set *dst, struct hash_set *src) {
+ for (size_t i = 0; i < src->size; i++)
+ if (!hash_set_slot_is_empty(src, i))
+ hash_set_do_insert(dst, hash_set_slot_ref(src, i));
+}
+static void hash_set_grow(struct hash_set *set) {
+ struct hash_set fresh;
+ hash_set_init(&fresh, set->size << 1);
+ hash_set_populate(&fresh, set);
+ hash_set_destroy(set);
+ memcpy(set, &fresh, sizeof(fresh));
+}
+static void hash_set_shrink(struct hash_set *set) {
+ struct hash_set fresh;
+ hash_set_init(&fresh, set->size >> 1);
+ hash_set_populate(&fresh, set);
+ hash_set_destroy(set);
+ memcpy(set, &fresh, sizeof(fresh));
+}
+
+static void hash_set_insert(struct hash_set *set, uintptr_t v) {
+ if (hash_set_should_grow(set))
+ hash_set_grow(set);
+ hash_set_do_insert(set, v);
+}
+
+static void hash_set_remove(struct hash_set *set, uintptr_t v) {
+ size_t slot = v;
+ while (!hash_set_slot_is_empty(set, slot) && hash_set_slot_ref(set, slot) != v)
+ slot++;
+ if (hash_set_slot_is_empty(set, slot))
+ __builtin_trap();
+ while (!hash_set_slot_is_empty(set, slot + 1)
+ && hash_set_slot_distance(set, slot + 1)) {
+ hash_set_slot_set(set, slot, hash_set_slot_ref(set, slot + 1));
+ slot++;
+ }
+ hash_set_slot_release(set, slot);
+ if (hash_set_should_shrink(set))
+ hash_set_shrink(set);
+}
+static int hash_set_contains(struct hash_set *set, uintptr_t v) {
+ for (size_t slot = v; !hash_set_slot_is_empty(set, slot); slot++) {
+ if (hash_set_slot_ref(set, slot) == v)
+ return 1;
+ if (hash_set_slot_distance(set, slot) < (slot - v))
+ return 0;
+ }
+ return 0;
+}
+static inline void hash_set_find(struct hash_set *set,
+ int (*f)(uintptr_t, void*), void *data) __attribute__((always_inline));
+static inline void hash_set_find(struct hash_set *set,
+ int (*f)(uintptr_t, void*), void *data) {
+ for (size_t i = 0; i < set->size; i++)
+ if (!hash_set_slot_is_empty(set, i))
+ if (f(hash_set_slot_ref(set, i), data))
+ return;
+}
+
+struct address_set {
+ struct hash_set hash_set;
+};
+
+static void address_set_init(struct address_set *set) {
+ hash_set_init(&set->hash_set, 8);
+}
+static void address_set_destroy(struct address_set *set) {
+ hash_set_destroy(&set->hash_set);
+}
+static void address_set_clear(struct address_set *set) {
+ hash_set_clear(&set->hash_set);
+}
+
+static void address_set_add(struct address_set *set, uintptr_t addr) {
+ hash_set_insert(&set->hash_set, hash_address(addr));
+}
+static void address_set_remove(struct address_set *set, uintptr_t addr) {
+ hash_set_remove(&set->hash_set, hash_address(addr));
+}
+static int address_set_contains(struct address_set *set, uintptr_t addr) {
+ return hash_set_contains(&set->hash_set, hash_address(addr));
+}
+static void address_set_union(struct address_set *set, struct address_set *other) {
+ while (set->hash_set.size < other->hash_set.size)
+ hash_set_grow(&set->hash_set);
+ hash_set_populate(&set->hash_set, &other->hash_set);
+}
+
+struct address_set_for_each_data {
+ void (*f)(uintptr_t, void *);
+ void *data;
+};
+static int address_set_do_for_each(uintptr_t v, void *data) {
+ struct address_set_for_each_data *for_each_data = data;
+ for_each_data->f(unhash_address(v), for_each_data->data);
+ return 0;
+}
+static inline void address_set_for_each(struct address_set *set,
+ void (*f)(uintptr_t, void*), void *data) __attribute__((always_inline));
+static inline void address_set_for_each(struct address_set *set,
+ void (*f)(uintptr_t, void*), void *data) {
+ struct address_set_for_each_data for_each_data = { f, data };
+ hash_set_find(&set->hash_set, address_set_do_for_each, &for_each_data);
+}
+
+struct address_set_find_data {
+ int (*f)(uintptr_t, void *);
+ void *data;
+};
+static int address_set_do_find(uintptr_t v, void *data) {
+ struct address_set_find_data *find_data = data;
+ return find_data->f(unhash_address(v), find_data->data);
+}
+static inline void address_set_find(struct address_set *set,
+ int (*f)(uintptr_t, void*), void *data) __attribute__((always_inline));
+static inline void address_set_find(struct address_set *set,
+ int (*f)(uintptr_t, void*), void *data) {
+ struct address_set_find_data find_data = { f, data };
+ hash_set_find(&set->hash_set, address_set_do_find, &find_data);
+}
+
+#endif // ADDRESS_SET_H