1 #ifndef DS_HTABLE_H 2 #define DS_HTABLE_H 3 4 #include "../common.h" 5 6 #define DS_HTABLE_MIN_CAPACITY 8 // Must be a power of 2 7 8 /** 9 * Marker to indicate an invalid index in the buffer. 10 */ 11 #define DS_HTABLE_INVALID_INDEX ((uint32_t) -1) 12 13 /** 14 * Determines the calculated hash of a bucket, before mod. We're using the key's 15 * zval uint32_t "next" to store this value so that we don't need another member 16 * in the bucket struct. 17 */ 18 #define DS_HTABLE_BUCKET_HASH(_bucket) (Z_NEXT((_bucket)->key)) 19 20 /** 21 * Determines the buffer index of the next bucket in the collision chain. 22 * An invalid index indicates that it's the last bucket in the chain. 23 */ 24 #define DS_HTABLE_BUCKET_NEXT(_bucket) (Z_NEXT((_bucket)->value)) 25 26 /** 27 * Determines if a bucket has been deleted. 28 */ 29 #define DS_HTABLE_BUCKET_DELETED(_bucket) (Z_ISUNDEF((_bucket)->key)) 30 31 /** 32 * Finds the start of the collision chain for a given hash. 33 * An invalid index indicates that a chain doesn't exist. 34 */ 35 #define DS_HTABLE_BUCKET_LOOKUP(t, h) ((t)->lookup[h & ((t)->capacity - 1)]) 36 37 /** 38 * Determines if a table is packed, ie. doesn't have deleted buckets. 39 */ 40 #define DS_HTABLE_IS_PACKED(t) ((t)->size == (t)->next) 41 42 /** 43 * Rehashes a bucket into a table. 44 * 45 * 1. Determine where the bucket's chain would start. 46 * 2. Set the bucket's next bucket to be the start of the chain. 47 * 3. Set the start of the chain to the bucket's position in the buffer. 48 * 49 * This means that the next bucket can come before another in the buffer, 50 * because a rehash unshifts the bucket into the chain. 51 */ 52 #define DS_HTABLE_BUCKET_REHASH(table, bucket, mask, idx) \ 53 do { \ 54 ds_htable_bucket_t *_bucket = bucket; \ 55 ds_htable_t *_table = table; \ 56 \ 57 uint32_t hash = DS_HTABLE_BUCKET_HASH(_bucket); \ 58 uint32_t *head = &_table->lookup[hash & (mask)]; \ 59 \ 60 DS_HTABLE_BUCKET_NEXT(_bucket) = *head; \ 61 *head = idx; \ 62 } while (0) 63 64 /** 65 * Copies a bucket's state into another, including: key, value, hash and next. 66 */ 67 #define DS_HTABLE_BUCKET_COPY(dst, src) \ 68 do { \ 69 ds_htable_bucket_t *_src = src; \ 70 ds_htable_bucket_t *_dst = dst; \ 71 ZVAL_COPY(&_dst->key, &_src->key); \ 72 ZVAL_COPY(&_dst->value, &_src->value); \ 73 DS_HTABLE_BUCKET_NEXT(_dst) = DS_HTABLE_BUCKET_NEXT(_src); \ 74 DS_HTABLE_BUCKET_HASH(_dst) = DS_HTABLE_BUCKET_HASH(_src); \ 75 } while (0) 76 77 /** 78 * Marks a bucket as deleted, destructing both the key and the value. 79 */ 80 #define DS_HTABLE_BUCKET_DELETE(b) \ 81 DTOR_AND_UNDEF(&(b)->value); \ 82 DTOR_AND_UNDEF(&(b)->key); \ 83 DS_HTABLE_BUCKET_NEXT((b)) = DS_HTABLE_INVALID_INDEX 84 85 #define DS_HTABLE_FOREACH_BUCKET(h, b) \ 86 do { \ 87 ds_htable_t *_h = h; \ 88 ds_htable_bucket_t *_x = _h->buckets; \ 89 ds_htable_bucket_t *_y = _h->buckets + _h->next; \ 90 for (; _x < _y; ++_x) { \ 91 if (DS_HTABLE_BUCKET_DELETED(_x)) continue; \ 92 b = _x; 93 94 #define DS_HTABLE_FOREACH_BUCKET_REVERSED(h, b) \ 95 do { \ 96 ds_htable_t *_h = h; \ 97 ds_htable_bucket_t *_x = _h->buckets; \ 98 ds_htable_bucket_t *_y = _x + _h->next - 1; \ 99 for (; _y >= _x; --_y) { \ 100 if (DS_HTABLE_BUCKET_DELETED(_y)) continue; \ 101 b = _y; 102 103 #define DS_HTABLE_FOREACH(h, i, k, v) \ 104 do { \ 105 uint32_t _i; \ 106 uint32_t _n = (h)->size; \ 107 ds_htable_bucket_t *_b = (h)->buckets; \ 108 \ 109 for (_i = 0; _i < _n; ++_b) { \ 110 if (DS_HTABLE_BUCKET_DELETED(_b)) continue; \ 111 k = &_b->key; \ 112 v = &_b->value; \ 113 i = _i++; 114 115 #define DS_HTABLE_FOREACH_KEY(h, k) \ 116 do { \ 117 ds_htable_t *_h = h; \ 118 ds_htable_bucket_t *_x = _h->buckets; \ 119 ds_htable_bucket_t *_y = _h->buckets + _h->next; \ 120 for (; _x < _y; ++_x) { \ 121 if (DS_HTABLE_BUCKET_DELETED(_x)) continue; \ 122 k = &_x->key; 123 124 #define DS_HTABLE_FOREACH_VALUE(h, v) \ 125 do { \ 126 ds_htable_t *_h = h; \ 127 ds_htable_bucket_t *_x = _h->buckets; \ 128 ds_htable_bucket_t *_y = _h->buckets + _h->next; \ 129 for (; _x < _y; ++_x) { \ 130 if (DS_HTABLE_BUCKET_DELETED(_x)) continue; \ 131 v = &_x->value; 132 133 #define DS_HTABLE_FOREACH_KEY_VALUE(h, k, v) \ 134 do { \ 135 ds_htable_t *_h = h; \ 136 ds_htable_bucket_t *_x = _h->buckets; \ 137 ds_htable_bucket_t *_y = _h->buckets + _h->next; \ 138 for (; _x < _y; ++_x) { \ 139 if (DS_HTABLE_BUCKET_DELETED(_x)) continue; \ 140 k = &_x->key; \ 141 v = &_x->value; 142 143 #define DS_HTABLE_FOREACH_END() \ 144 } \ 145 } while (0) 146 147 typedef struct _ds_htable_bucket_t { 148 zval key; 149 zval value; 150 } ds_htable_bucket_t; 151 152 typedef struct _ds_htable_t { 153 ds_htable_bucket_t *buckets; // Buffer for the buckets 154 uint32_t *lookup; // Separated hash lookup table 155 uint32_t next; // Next open index in the bucket buffer 156 uint32_t size; // Number of active buckets in the table 157 uint32_t capacity; // Length of the bucket buffer 158 uint32_t min_deleted; // First deleted bucket buffer index 159 } ds_htable_t; 160 161 ds_htable_t *ds_htable(); 162 zval *ds_htable_values(ds_htable_t *table); 163 164 void ds_htable_ensure_capacity(ds_htable_t *table, uint32_t capacity); 165 166 void ds_htable_sort(ds_htable_t *table, compare_func_t compare_func); 167 void ds_htable_sort_by_key(ds_htable_t *table); 168 void ds_htable_sort_by_value(ds_htable_t *table); 169 void ds_htable_sort_by_pair(ds_htable_t *table); 170 void ds_htable_sort_callback_by_key(ds_htable_t *table); 171 void ds_htable_sort_callback_by_value(ds_htable_t *table); 172 173 ds_htable_bucket_t *ds_htable_lookup_by_value(ds_htable_t *h, zval *key); 174 ds_htable_bucket_t *ds_htable_lookup_by_key(ds_htable_t *h, zval *key); 175 ds_htable_bucket_t *ds_htable_lookup_by_position(ds_htable_t *table, uint32_t position); 176 177 bool ds_htable_lookup_or_next(ds_htable_t *table, zval *key, ds_htable_bucket_t **return_value); 178 bool ds_htable_has_keys(ds_htable_t *h, VA_PARAMS); 179 bool ds_htable_has_key(ds_htable_t *table, zval *key); 180 bool ds_htable_has_values(ds_htable_t *h, VA_PARAMS); 181 bool ds_htable_has_value(ds_htable_t *h, zval *value); 182 int ds_htable_remove(ds_htable_t *h, zval *key, zval *return_value); 183 void ds_htable_put(ds_htable_t *h, zval *key, zval *value); 184 void ds_htable_to_array(ds_htable_t *h, zval *arr); 185 void ds_htable_free(ds_htable_t *h); 186 zval *ds_htable_get(ds_htable_t *h, zval *key); 187 ds_htable_t *ds_htable_slice(ds_htable_t *table, zend_long index, zend_long length); 188 189 void ds_htable_clear(ds_htable_t *h); 190 bool ds_htable_isset(ds_htable_t *h, zval *key, bool check_empty); 191 ds_htable_t *ds_htable_clone(ds_htable_t *source); 192 193 zend_string *ds_htable_join_keys(ds_htable_t *table, const char* glue, const size_t len); 194 195 void ds_htable_reverse(ds_htable_t *table); 196 ds_htable_t *ds_htable_reversed(ds_htable_t *table); 197 198 ds_htable_bucket_t *ds_htable_first(ds_htable_t *table); 199 ds_htable_bucket_t *ds_htable_last(ds_htable_t *table); 200 201 ds_htable_t *ds_htable_map(ds_htable_t *table, FCI_PARAMS); 202 ds_htable_t *ds_htable_filter(ds_htable_t *table); 203 ds_htable_t *ds_htable_filter_callback(ds_htable_t *table, FCI_PARAMS); 204 205 void ds_htable_apply(ds_htable_t *table, FCI_PARAMS); 206 void ds_htable_reduce(ds_htable_t *table, FCI_PARAMS, zval *initial, zval *return_value); 207 208 ds_htable_t *ds_htable_xor(ds_htable_t *table, ds_htable_t *other); 209 ds_htable_t *ds_htable_diff(ds_htable_t *table, ds_htable_t *other); 210 ds_htable_t *ds_htable_intersect(ds_htable_t *table, ds_htable_t *other); 211 ds_htable_t *ds_htable_merge(ds_htable_t *table, ds_htable_t *other); 212 213 int ds_htable_serialize(ds_htable_t *table, unsigned char **buffer, size_t *buf_len, zend_serialize_data *data); 214 int ds_htable_unserialize(ds_htable_t *table, const unsigned char *buffer, size_t length, zend_unserialize_data *data); 215 216 #endif 217
