summaryrefslogtreecommitdiff
path: root/libguile/whippet/src/address-set.h
blob: b1c27fa412905b951d25a621709a08c3006798b0 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
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