php-internal-docs 8.4.8
Unofficial docs for php/php-src
Loading...
Searching...
No Matches
ir_strtab.c
Go to the documentation of this file.
1/*
2 * IR - Lightweight JIT Compilation Framework
3 * (String table)
4 * Copyright (C) 2022 Zend by Perforce.
5 * Authors: Dmitry Stogov <dmitry@php.net>
6 */
7
8#include "ir.h"
9#include "ir_private.h"
10
11typedef struct _ir_strtab_bucket {
12 uint32_t h;
13 uint32_t len;
14 const char *str;
15 uint32_t next;
18
19static uint32_t ir_str_hash(const char *str, size_t len)
20{
21 size_t i;
22 uint32_t h = 5381;
23
24 for (i = 0; i < len; i++) {
25 h = ((h << 5) + h) + *str;
26 str++;
27 }
28 return h | 0x10000000;
29}
30
31static uint32_t ir_strtab_hash_size(uint32_t size)
32{
33 /* Use big enough power of 2 */
34 size -= 1;
35 size |= (size >> 1);
36 size |= (size >> 2);
37 size |= (size >> 4);
38 size |= (size >> 8);
39 size |= (size >> 16);
40 return size + 1;
41}
42
43static void ir_strtab_resize(ir_strtab *strtab)
44{
45 uint32_t old_hash_size = (uint32_t)(-(int32_t)strtab->mask);
46 char *old_data = strtab->data;
47 uint32_t size = strtab->size * 2;
48 uint32_t hash_size = ir_strtab_hash_size(size);
49 char *data = ir_mem_malloc(hash_size * sizeof(uint32_t) + size * sizeof(ir_strtab_bucket));
51 uint32_t pos, i;
52
53 memset(data, IR_INVALID_IDX, hash_size * sizeof(uint32_t));
54 strtab->data = data + (hash_size * sizeof(uint32_t));
55 strtab->mask = (uint32_t)(-(int32_t)hash_size);
56 strtab->size = size;
57
58 memcpy(strtab->data, old_data, strtab->count * sizeof(ir_strtab_bucket));
59 ir_mem_free(old_data - (old_hash_size * sizeof(uint32_t)));
60
61 i = strtab->count;
62 pos = 0;
63 p = (ir_strtab_bucket*)strtab->data;
64 do {
65 uint32_t h = p->h | strtab->mask;
66 p->next = ((uint32_t*)strtab->data)[(int32_t)h];
67 ((uint32_t*)strtab->data)[(int32_t)h] = pos;
68 pos += sizeof(ir_strtab_bucket);
69 p++;
70 } while (--i);
71}
72
73static void ir_strtab_grow_buf(ir_strtab *strtab, uint32_t len)
74{
75 intptr_t old = (intptr_t)strtab->buf;
76
77 do {
78 strtab->buf_size *= 2;
79 } while (UNEXPECTED(strtab->buf_size - strtab->buf_top < len + 1));
80
81 strtab->buf = ir_mem_realloc(strtab->buf, strtab->buf_size);
82 if ((intptr_t)strtab->buf != old) {
83 intptr_t offset = (intptr_t)strtab->buf - old;
84 ir_strtab_bucket *p = (ir_strtab_bucket*)strtab->data;
85 uint32_t i;
86 for (i = strtab->count; i > 0; i--) {
87 p->str += offset;
88 p++;
89 }
90 }
91}
92
93void ir_strtab_init(ir_strtab *strtab, uint32_t size, uint32_t buf_size)
94{
95 IR_ASSERT(size > 0);
96 uint32_t hash_size = ir_strtab_hash_size(size);
97 char *data = ir_mem_malloc(hash_size * sizeof(uint32_t) + size * sizeof(ir_strtab_bucket));
98 memset(data, IR_INVALID_IDX, hash_size * sizeof(uint32_t));
99 strtab->data = (data + (hash_size * sizeof(uint32_t)));
100 strtab->mask = (uint32_t)(-(int32_t)hash_size);
101 strtab->size = size;
102 strtab->count = 0;
103 strtab->pos = 0;
104 if (buf_size) {
105 strtab->buf = ir_mem_malloc(buf_size);
106 strtab->buf_size = buf_size;
107 strtab->buf_top = 0;
108 } else {
109 strtab->buf = NULL;
110 strtab->buf_size = 0;
111 strtab->buf_top = 0;
112 }
113}
114
115ir_ref ir_strtab_find(const ir_strtab *strtab, const char *str, uint32_t len)
116{
117 uint32_t h = ir_str_hash(str, len);
118 const char *data = (const char*)strtab->data;
119 uint32_t pos = ((uint32_t*)data)[(int32_t)(h | strtab->mask)];
121
122 while (pos != IR_INVALID_IDX) {
123 p = (ir_strtab_bucket*)(data + pos);
124 if (p->h == h
125 && p->len == len
126 && memcmp(p->str, str, len) == 0) {
127 return p->val;
128 }
129 pos = p->next;
130 }
131 return 0;
132}
133
134ir_ref ir_strtab_lookup(ir_strtab *strtab, const char *str, uint32_t len, ir_ref val)
135{
136 uint32_t h = ir_str_hash(str, len);
137 char *data = (char*)strtab->data;
138 uint32_t pos = ((uint32_t*)data)[(int32_t)(h | strtab->mask)];
140
141 while (pos != IR_INVALID_IDX) {
142 p = (ir_strtab_bucket*)(data + pos);
143 if (p->h == h
144 && p->len == len
145 && memcmp(p->str, str, len) == 0) {
146 return p->val;
147 }
148 pos = p->next;
149 }
150
151 IR_ASSERT(val != 0);
152
153 if (UNEXPECTED(strtab->count >= strtab->size)) {
154 ir_strtab_resize(strtab);
155 data = strtab->data;
156 }
157
158 if (strtab->buf) {
159 if (UNEXPECTED(strtab->buf_size - strtab->buf_top < len + 1)) {
160 ir_strtab_grow_buf(strtab, len + 1);
161 }
162
163 memcpy(strtab->buf + strtab->buf_top, str, len);
164 strtab->buf[strtab->buf_top + len] = 0;
165 str = (const char*)strtab->buf + strtab->buf_top;
166 strtab->buf_top += len + 1;
167 }
168
169 pos = strtab->pos;
170 strtab->pos += sizeof(ir_strtab_bucket);
171 strtab->count++;
172 p = (ir_strtab_bucket*)(data + pos);
173 p->h = h;
174 p->len = len;
175 p->str = str;
176 h |= strtab->mask;
177 p->next = ((uint32_t*)data)[(int32_t)h];
178 ((uint32_t*)data)[(int32_t)h] = pos;
179 p->val = val;
180 return val;
181}
182
183ir_ref ir_strtab_update(ir_strtab *strtab, const char *str, uint32_t len, ir_ref val)
184{
185 uint32_t h = ir_str_hash(str, len);
186 char *data = (char*)strtab->data;
187 uint32_t pos = ((uint32_t*)data)[(int32_t)(h | strtab->mask)];
189
190 while (pos != IR_INVALID_IDX) {
191 p = (ir_strtab_bucket*)(data + pos);
192 if (p->h == h
193 && p->len == len
194 && memcmp(p->str, str, len) == 0) {
195 return p->val = val;
196 }
197 pos = p->next;
198 }
199 return 0;
200}
201
202const char *ir_strtab_str(const ir_strtab *strtab, ir_ref idx)
203{
204 IR_ASSERT(idx >= 0 && (uint32_t)idx < strtab->count);
205 return ((const ir_strtab_bucket*)strtab->data)[idx].str;
206}
207
208const char *ir_strtab_strl(const ir_strtab *strtab, ir_ref idx, size_t *len)
209{
210 const ir_strtab_bucket *b = ((const ir_strtab_bucket*)strtab->data) + idx;
211 IR_ASSERT(idx >= 0 && (uint32_t)idx < strtab->count);
212 *len = b->len;
213 return b->str;
214}
215
217{
218 uint32_t hash_size = (uint32_t)(-(int32_t)strtab->mask);
219 char *data = (char*)strtab->data - (hash_size * sizeof(uint32_t));
221 strtab->data = NULL;
222 if (strtab->buf) {
223 ir_mem_free(strtab->buf);
224 strtab->buf = NULL;
225 }
226}
227
229{
230 uint32_t i;
231
232 for (i = 0; i < strtab->count; i++) {
233 const ir_strtab_bucket *b = &((ir_strtab_bucket*)strtab->data)[i];
234 func(b->str, b->len, b->val);
235 }
236}
size_t len
Definition apprentice.c:174
count(Countable|array $value, int $mode=COUNT_NORMAL)
new_type size
Definition ffi.c:4365
memcpy(ptr1, ptr2, size)
memset(ptr, 0, type->size)
zval * val
Definition ffi.c:4262
zend_long offset
#define NULL
Definition gdcache.h:45
int32_t ir_ref
Definition ir.h:390
#define ir_mem_malloc
Definition ir.h:1006
#define ir_mem_realloc
Definition ir.h:1012
struct _ir_strtab ir_strtab
#define ir_mem_free
Definition ir.h:1015
void(* ir_strtab_apply_t)(const char *str, uint32_t len, ir_ref val)
Definition ir.h:498
#define IR_ASSERT(x)
Definition ir_private.h:17
#define IR_INVALID_IDX
Definition ir_private.h:842
ir_ref ir_strtab_find(const ir_strtab *strtab, const char *str, uint32_t len)
Definition ir_strtab.c:115
const char * ir_strtab_strl(const ir_strtab *strtab, ir_ref idx, size_t *len)
Definition ir_strtab.c:208
void ir_strtab_apply(const ir_strtab *strtab, ir_strtab_apply_t func)
Definition ir_strtab.c:228
ir_ref ir_strtab_update(ir_strtab *strtab, const char *str, uint32_t len, ir_ref val)
Definition ir_strtab.c:183
struct _ir_strtab_bucket ir_strtab_bucket
void ir_strtab_init(ir_strtab *strtab, uint32_t size, uint32_t buf_size)
Definition ir_strtab.c:93
const char * ir_strtab_str(const ir_strtab *strtab, ir_ref idx)
Definition ir_strtab.c:202
ir_ref ir_strtab_lookup(ir_strtab *strtab, const char *str, uint32_t len, ir_ref val)
Definition ir_strtab.c:134
void ir_strtab_free(ir_strtab *strtab)
Definition ir_strtab.c:216
unsigned const char * pos
Definition php_ffi.h:52
zend_constant * data
p
Definition session.c:1105
const char * str
Definition ir_strtab.c:14
execute_data func
#define UNEXPECTED(condition)