prism/util/pm_constant_pool.h

   1 /**
   2  * @file pm_constant_pool.h
   3  *
   4  * A data structure that stores a set of strings.
   5  *
   6  * Each string is assigned a unique id, which can be used to compare strings for
   7  * equality. This comparison ends up being much faster than strcmp, since it
   8  * only requires a single integer comparison.
   9  */
  10 #ifndef PRISM_CONSTANT_POOL_H
  11 #define PRISM_CONSTANT_POOL_H
  12
  13 #include "prism/defines.h"
  14
  15 #include <assert.h>
  16 #include <stdbool.h>
  17 #include <stdint.h>
  18 #include <stdlib.h>
  19 #include <string.h>
  20
  21 /**
  22  * When we allocate constants into the pool, we reserve 0 to mean that the slot
  23  * is not yet filled. This constant is reused in other places to indicate the
  24  * lack of a constant id.
  25  */
  26 #define PM_CONSTANT_ID_UNSET 0
  27
  28 /**
  29  * A constant id is a unique identifier for a constant in the constant pool.
  30  */
  31 typedef uint32_t pm_constant_id_t;
  32
  33 /**
  34  * A list of constant IDs. Usually used to represent a set of locals.
  35  */
  36 typedef struct {
  37     /** The number of constant ids in the list. */
  38     size_t size;
  39
  40     /** The number of constant ids that have been allocated in the list. */
  41     size_t capacity;
  42
  43     /** The constant ids in the list. */
  44     pm_constant_id_t *ids;
  45 } pm_constant_id_list_t;
  46
  47 /**
  48  * Initialize a list of constant ids.
  49  *
  50  * @param list The list to initialize.
  51  */
  52 void pm_constant_id_list_init(pm_constant_id_list_t *list);
  53
  54 /**
  55  * Initialize a list of constant ids with a given capacity.
  56  *
  57  * @param list The list to initialize.
  58  * @param capacity The initial capacity of the list.
  59  */
  60 void pm_constant_id_list_init_capacity(pm_constant_id_list_t *list, size_t capacity);
  61
  62 /**
  63  * Append a constant id to a list of constant ids. Returns false if any
  64  * potential reallocations fail.
  65  *
  66  * @param list The list to append to.
  67  * @param id The id to append.
  68  * @return Whether the append succeeded.
  69  */
  70 bool pm_constant_id_list_append(pm_constant_id_list_t *list, pm_constant_id_t id);
  71
  72 /**
  73  * Insert a constant id into a list of constant ids at the specified index.
  74  *
  75  * @param list The list to insert into.
  76  * @param index The index at which to insert.
  77  * @param id The id to insert.
  78  */
  79 void pm_constant_id_list_insert(pm_constant_id_list_t *list, size_t index, pm_constant_id_t id);
  80
  81 /**
  82  * Checks if the current constant id list includes the given constant id.
  83  *
  84  * @param list The list to check.
  85  * @param id The id to check for.
  86  * @return Whether the list includes the given id.
  87  */
  88 bool pm_constant_id_list_includes(pm_constant_id_list_t *list, pm_constant_id_t id);
  89
  90 /**
  91  * Free the memory associated with a list of constant ids.
  92  *
  93  * @param list The list to free.
  94  */
  95 void pm_constant_id_list_free(pm_constant_id_list_t *list);
  96
  97 /**
  98  * The type of bucket in the constant pool hash map. This determines how the
  99  * bucket should be freed.
 100  */
 101 typedef unsigned int pm_constant_pool_bucket_type_t;
 102
 103 /** By default, each constant is a slice of the source. */
 104 static const pm_constant_pool_bucket_type_t PM_CONSTANT_POOL_BUCKET_DEFAULT = 0;
 105
 106 /** An owned constant is one for which memory has been allocated. */
 107 static const pm_constant_pool_bucket_type_t PM_CONSTANT_POOL_BUCKET_OWNED = 1;
 108
 109 /** A constant constant is known at compile time. */
 110 static const pm_constant_pool_bucket_type_t PM_CONSTANT_POOL_BUCKET_CONSTANT = 2;
 111
 112 /** A bucket in the hash map. */
 113 typedef struct {
 114     /** The incremental ID used for indexing back into the pool. */
 115     unsigned int id: 30;
 116
 117     /** The type of the bucket, which determines how to free it. */
 118     pm_constant_pool_bucket_type_t type: 2;
 119
 120     /** The hash of the bucket. */
 121     uint32_t hash;
 122 } pm_constant_pool_bucket_t;
 123
 124 /** A constant in the pool which effectively stores a string. */
 125 typedef struct {
 126     /** A pointer to the start of the string. */
 127     const uint8_t *start;
 128
 129     /** The length of the string. */
 130     size_t length;
 131 } pm_constant_t;
 132
 133 /** The overall constant pool, which stores constants found while parsing. */
 134 typedef struct {
 135     /** The buckets in the hash map. */
 136     pm_constant_pool_bucket_t *buckets;
 137
 138     /** The constants that are stored in the buckets. */
 139     pm_constant_t *constants;
 140
 141     /** The number of buckets in the hash map. */
 142     uint32_t size;
 143
 144     /** The number of buckets that have been allocated in the hash map. */
 145     uint32_t capacity;
 146 } pm_constant_pool_t;
 147
 148 /**
 149  * Initialize a new constant pool with a given capacity.
 150  *
 151  * @param pool The pool to initialize.
 152  * @param capacity The initial capacity of the pool.
 153  * @return Whether the initialization succeeded.
 154  */
 155 bool pm_constant_pool_init(pm_constant_pool_t *pool, uint32_t capacity);
 156
 157 /**
 158  * Return a pointer to the constant indicated by the given constant id.
 159  *
 160  * @param pool The pool to get the constant from.
 161  * @param constant_id The id of the constant to get.
 162  * @return A pointer to the constant.
 163  */
 164 pm_constant_t * pm_constant_pool_id_to_constant(const pm_constant_pool_t *pool, pm_constant_id_t constant_id);
 165
 166 /**
 167  * Find a constant in a constant pool. Returns the id of the constant, or 0 if
 168  * the constant is not found.
 169  *
 170  * @param pool The pool to find the constant in.
 171  * @param start A pointer to the start of the constant.
 172  * @param length The length of the constant.
 173  * @return The id of the constant.
 174  */
 175 pm_constant_id_t pm_constant_pool_find(const pm_constant_pool_t *pool, const uint8_t *start, size_t length);
 176
 177 /**
 178  * Insert a constant into a constant pool that is a slice of a source string.
 179  * Returns the id of the constant, or 0 if any potential calls to resize fail.
 180  *
 181  * @param pool The pool to insert the constant into.
 182  * @param start A pointer to the start of the constant.
 183  * @param length The length of the constant.
 184  * @return The id of the constant.
 185  */
 186 pm_constant_id_t pm_constant_pool_insert_shared(pm_constant_pool_t *pool, const uint8_t *start, size_t length);
 187
 188 /**
 189  * Insert a constant into a constant pool from memory that is now owned by the
 190  * constant pool. Returns the id of the constant, or 0 if any potential calls to
 191  * resize fail.
 192  *
 193  * @param pool The pool to insert the constant into.
 194  * @param start A pointer to the start of the constant.
 195  * @param length The length of the constant.
 196  * @return The id of the constant.
 197  */
 198 pm_constant_id_t pm_constant_pool_insert_owned(pm_constant_pool_t *pool, uint8_t *start, size_t length);
 199
 200 /**
 201  * Insert a constant into a constant pool from memory that is constant. Returns
 202  * the id of the constant, or 0 if any potential calls to resize fail.
 203  *
 204  * @param pool The pool to insert the constant into.
 205  * @param start A pointer to the start of the constant.
 206  * @param length The length of the constant.
 207  * @return The id of the constant.
 208  */
 209 pm_constant_id_t pm_constant_pool_insert_constant(pm_constant_pool_t *pool, const uint8_t *start, size_t length);
 210
 211 /**
 212  * Free the memory associated with a constant pool.
 213  *
 214  * @param pool The pool to free.
 215  */
 216 void pm_constant_pool_free(pm_constant_pool_t *pool);
 217
 218 #endif