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
215
216
217
218
219
220
221
222
223
224
225
226
|
/**
* @file pm_constant_pool.h
*
* A data structure that stores a set of strings.
*
* Each string is assigned a unique id, which can be used to compare strings for
* equality. This comparison ends up being much faster than strcmp, since it
* only requires a single integer comparison.
*/
#ifndef PRISM_CONSTANT_POOL_H
#define PRISM_CONSTANT_POOL_H
#include "prism/defines.h"
#include <assert.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
/**
* When we allocate constants into the pool, we reserve 0 to mean that the slot
* is not yet filled. This constant is reused in other places to indicate the
* lack of a constant id.
*/
#define PM_CONSTANT_ID_UNSET 0
/**
* A constant id is a unique identifier for a constant in the constant pool.
*/
typedef uint32_t pm_constant_id_t;
/**
* A list of constant IDs. Usually used to represent a set of locals.
*/
typedef struct {
/** The number of constant ids in the list. */
size_t size;
/** The number of constant ids that have been allocated in the list. */
size_t capacity;
/** The constant ids in the list. */
pm_constant_id_t *ids;
} pm_constant_id_list_t;
/**
* Initialize a list of constant ids.
*
* @param list The list to initialize.
*/
void pm_constant_id_list_init(pm_constant_id_list_t *list);
/**
* Initialize a list of constant ids with a given capacity.
*
* @param list The list to initialize.
* @param capacity The initial capacity of the list.
*/
void pm_constant_id_list_init_capacity(pm_constant_id_list_t *list, size_t capacity);
/**
* Append a constant id to a list of constant ids. Returns false if any
* potential reallocations fail.
*
* @param list The list to append to.
* @param id The id to append.
* @return Whether the append succeeded.
*/
bool pm_constant_id_list_append(pm_constant_id_list_t *list, pm_constant_id_t id);
/**
* Insert a constant id into a list of constant ids at the specified index.
*
* @param list The list to insert into.
* @param index The index at which to insert.
* @param id The id to insert.
*/
void pm_constant_id_list_insert(pm_constant_id_list_t *list, size_t index, pm_constant_id_t id);
/**
* Checks if the current constant id list includes the given constant id.
*
* @param list The list to check.
* @param id The id to check for.
* @return Whether the list includes the given id.
*/
bool pm_constant_id_list_includes(pm_constant_id_list_t *list, pm_constant_id_t id);
/**
* Get the memory size of a list of constant ids.
*
* @param list The list to get the memory size of.
* @return The memory size of the list.
*/
size_t pm_constant_id_list_memsize(pm_constant_id_list_t *list);
/**
* Free the memory associated with a list of constant ids.
*
* @param list The list to free.
*/
void pm_constant_id_list_free(pm_constant_id_list_t *list);
/**
* The type of bucket in the constant pool hash map. This determines how the
* bucket should be freed.
*/
typedef unsigned int pm_constant_pool_bucket_type_t;
/** By default, each constant is a slice of the source. */
static const pm_constant_pool_bucket_type_t PM_CONSTANT_POOL_BUCKET_DEFAULT = 0;
/** An owned constant is one for which memory has been allocated. */
static const pm_constant_pool_bucket_type_t PM_CONSTANT_POOL_BUCKET_OWNED = 1;
/** A constant constant is known at compile time. */
static const pm_constant_pool_bucket_type_t PM_CONSTANT_POOL_BUCKET_CONSTANT = 2;
/** A bucket in the hash map. */
typedef struct {
/** The incremental ID used for indexing back into the pool. */
unsigned int id: 30;
/** The type of the bucket, which determines how to free it. */
pm_constant_pool_bucket_type_t type: 2;
/** The hash of the bucket. */
uint32_t hash;
} pm_constant_pool_bucket_t;
/** A constant in the pool which effectively stores a string. */
typedef struct {
/** A pointer to the start of the string. */
const uint8_t *start;
/** The length of the string. */
size_t length;
} pm_constant_t;
/** The overall constant pool, which stores constants found while parsing. */
typedef struct {
/** The buckets in the hash map. */
pm_constant_pool_bucket_t *buckets;
/** The constants that are stored in the buckets. */
pm_constant_t *constants;
/** The number of buckets in the hash map. */
uint32_t size;
/** The number of buckets that have been allocated in the hash map. */
uint32_t capacity;
} pm_constant_pool_t;
/**
* Initialize a new constant pool with a given capacity.
*
* @param pool The pool to initialize.
* @param capacity The initial capacity of the pool.
* @return Whether the initialization succeeded.
*/
bool pm_constant_pool_init(pm_constant_pool_t *pool, uint32_t capacity);
/**
* Return a pointer to the constant indicated by the given constant id.
*
* @param pool The pool to get the constant from.
* @param constant_id The id of the constant to get.
* @return A pointer to the constant.
*/
pm_constant_t * pm_constant_pool_id_to_constant(const pm_constant_pool_t *pool, pm_constant_id_t constant_id);
/**
* Find a constant in a constant pool. Returns the id of the constant, or 0 if
* the constant is not found.
*
* @param pool The pool to find the constant in.
* @param start A pointer to the start of the constant.
* @param length The length of the constant.
* @return The id of the constant.
*/
pm_constant_id_t pm_constant_pool_find(const pm_constant_pool_t *pool, const uint8_t *start, size_t length);
/**
* Insert a constant into a constant pool that is a slice of a source string.
* Returns the id of the constant, or 0 if any potential calls to resize fail.
*
* @param pool The pool to insert the constant into.
* @param start A pointer to the start of the constant.
* @param length The length of the constant.
* @return The id of the constant.
*/
pm_constant_id_t pm_constant_pool_insert_shared(pm_constant_pool_t *pool, const uint8_t *start, size_t length);
/**
* Insert a constant into a constant pool from memory that is now owned by the
* constant pool. Returns the id of the constant, or 0 if any potential calls to
* resize fail.
*
* @param pool The pool to insert the constant into.
* @param start A pointer to the start of the constant.
* @param length The length of the constant.
* @return The id of the constant.
*/
pm_constant_id_t pm_constant_pool_insert_owned(pm_constant_pool_t *pool, uint8_t *start, size_t length);
/**
* Insert a constant into a constant pool from memory that is constant. Returns
* the id of the constant, or 0 if any potential calls to resize fail.
*
* @param pool The pool to insert the constant into.
* @param start A pointer to the start of the constant.
* @param length The length of the constant.
* @return The id of the constant.
*/
pm_constant_id_t pm_constant_pool_insert_constant(pm_constant_pool_t *pool, const uint8_t *start, size_t length);
/**
* Free the memory associated with a constant pool.
*
* @param pool The pool to free.
*/
void pm_constant_pool_free(pm_constant_pool_t *pool);
#endif
|
