/src/php-src/ext/opcache/jit/ir/ir_strtab.c

Source
/*
 * IR - Lightweight JIT Compilation Framework
 * (String table)
 * This file is part of the IR Project distributed under the MIT-style LICENSE.
 * Authors: Dmitry Stogov <dmitry@php.net>
 */

#include "ir.h"
#include "ir_private.h"

typedef struct _ir_strtab_bucket {
  uint32_t    h;
  uint32_t    len;
  const char *str;
  uint32_t    next;
  ir_str      val;
} ir_strtab_bucket;

static uint32_t ir_str_hash(const char *str, size_t len)
{
  size_t i;
  uint32_t h = 5381;

    for (i = 0; i < len; i++) {
        h = ((h << 5) + h) + *str;
        str++;
    }
    return h | 0x10000000;
}

static uint32_t ir_strtab_hash_size(uint32_t size)
{
  /* Use big enough power of 2 */
  size -= 1;
  size |= (size >> 1);
  size |= (size >> 2);
  size |= (size >> 4);
  size |= (size >> 8);
  size |= (size >> 16);
  return size + 1;
}

static void ir_strtab_resize(ir_strtab *strtab)
{
  uint32_t old_hash_size = (uint32_t)(-(int32_t)strtab->mask);
  char *old_data = strtab->data;
  uint32_t size = strtab->size * 2;
  uint32_t hash_size = ir_strtab_hash_size(size);
  char *data = ir_mem_malloc(hash_size * sizeof(uint32_t) + size * sizeof(ir_strtab_bucket));
  ir_strtab_bucket *p;
  uint32_t pos, i;

  memset(data, IR_INVALID_IDX, hash_size * sizeof(uint32_t));
  strtab->data = data + (hash_size * sizeof(uint32_t));
  strtab->mask = (uint32_t)(-(int32_t)hash_size);
  strtab->size = size;

  memcpy(strtab->data, old_data, strtab->count * sizeof(ir_strtab_bucket));
  ir_mem_free(old_data - (old_hash_size * sizeof(uint32_t)));

  i = strtab->count;
  pos = 0;
  p = (ir_strtab_bucket*)strtab->data;
  do {
    uint32_t h = p->h | strtab->mask;
    p->next = ((uint32_t*)strtab->data)[(int32_t)h];
    ((uint32_t*)strtab->data)[(int32_t)h] = pos;
    pos += sizeof(ir_strtab_bucket);
    p++;
  } while (--i);
}

static void ir_strtab_grow_buf(ir_strtab *strtab, uint32_t len)
{
  intptr_t old = (intptr_t)strtab->buf;

  do {
    strtab->buf_size *= 2;
  } while (UNEXPECTED(strtab->buf_size - strtab->buf_top < len + 1));

  strtab->buf = ir_mem_realloc(strtab->buf, strtab->buf_size);
  if ((intptr_t)strtab->buf != old) {
    intptr_t offset = (intptr_t)strtab->buf - old;
    ir_strtab_bucket *p = (ir_strtab_bucket*)strtab->data;
    uint32_t i;
    for (i = strtab->count; i > 0; i--) {
      p->str += offset;
      p++;
    }
  }
}

void ir_strtab_init(ir_strtab *strtab, uint32_t size, uint32_t buf_size)
{
  IR_ASSERT(size > 0);
  uint32_t hash_size = ir_strtab_hash_size(size);
  char *data = ir_mem_malloc(hash_size * sizeof(uint32_t) + size * sizeof(ir_strtab_bucket));
  memset(data, IR_INVALID_IDX, hash_size * sizeof(uint32_t));
  strtab->data = (data + (hash_size * sizeof(uint32_t)));
  strtab->mask = (uint32_t)(-(int32_t)hash_size);
  strtab->size = size;
  strtab->count = 0;
  strtab->pos = 0;
  if (buf_size) {
    strtab->buf = ir_mem_malloc(buf_size);
    strtab->buf_size = buf_size;
    strtab->buf_top = 0;
  } else {
    strtab->buf = NULL;
    strtab->buf_size = 0;
    strtab->buf_top = 0;
  }
}

ir_str ir_strtab_find(const ir_strtab *strtab, const char *str, uint32_t len)
{
  uint32_t h = ir_str_hash(str, len);
  const char *data = (const char*)strtab->data;
  uint32_t pos = ((uint32_t*)data)[(int32_t)(h | strtab->mask)];
  ir_strtab_bucket *p;

  while (pos != IR_INVALID_IDX) {
    p = (ir_strtab_bucket*)(data + pos);
    if (p->h == h
     && p->len == len
     && memcmp(p->str, str, len) == 0) {
      return p->val;
    }
    pos = p->next;
  }
  return 0;
}

ir_str ir_strtab_lookup(ir_strtab *strtab, const char *str, uint32_t len, ir_str val)
{
  uint32_t h = ir_str_hash(str, len);
  char *data = (char*)strtab->data;
  uint32_t pos = ((uint32_t*)data)[(int32_t)(h | strtab->mask)];
  ir_strtab_bucket *p;

  while (pos != IR_INVALID_IDX) {
    p = (ir_strtab_bucket*)(data + pos);
    if (p->h == h
     && p->len == len
     && memcmp(p->str, str, len) == 0) {
      return p->val;
    }
    pos = p->next;
  }

  IR_ASSERT(val != 0);

  if (UNEXPECTED(strtab->count >= strtab->size)) {
    ir_strtab_resize(strtab);
    data = strtab->data;
  }

  if (strtab->buf) {
    if (UNEXPECTED(strtab->buf_size - strtab->buf_top < len + 1)) {
      ir_strtab_grow_buf(strtab, len + 1);
    }

    memcpy(strtab->buf + strtab->buf_top, str, len);
    strtab->buf[strtab->buf_top + len] = 0;
    str = (const char*)strtab->buf + strtab->buf_top;
    strtab->buf_top += len + 1;
  }

  pos = strtab->pos;
  strtab->pos += sizeof(ir_strtab_bucket);
  strtab->count++;
  p = (ir_strtab_bucket*)(data + pos);
  p->h = h;
  p->len = len;
  p->str = str;
  h |= strtab->mask;
  p->next = ((uint32_t*)data)[(int32_t)h];
  ((uint32_t*)data)[(int32_t)h] = pos;
  p->val = val;
  return val;
}

void ir_strtab_set(ir_strtab *strtab, const char *str, uint32_t len, ir_str val)
{
  uint32_t h = ir_str_hash(str, len);
  char *data = (char*)strtab->data;
  uint32_t pos = ((uint32_t*)data)[(int32_t)(h | strtab->mask)];
  ir_strtab_bucket *p;

  while (pos != IR_INVALID_IDX) {
    p = (ir_strtab_bucket*)(data + pos);
    if (p->h == h
     && p->len == len
     && memcmp(p->str, str, len) == 0) {
      p->val = val;
      return;
    }
    pos = p->next;
  }

  IR_ASSERT(val != 0);

  if (UNEXPECTED(strtab->count >= strtab->size)) {
    ir_strtab_resize(strtab);
    data = strtab->data;
  }

  if (strtab->buf) {
    if (UNEXPECTED(strtab->buf_size - strtab->buf_top < len + 1)) {
      ir_strtab_grow_buf(strtab, len + 1);
    }

    memcpy(strtab->buf + strtab->buf_top, str, len);
    strtab->buf[strtab->buf_top + len] = 0;
    str = (const char*)strtab->buf + strtab->buf_top;
    strtab->buf_top += len + 1;
  }

  pos = strtab->pos;
  strtab->pos += sizeof(ir_strtab_bucket);
  strtab->count++;
  p = (ir_strtab_bucket*)(data + pos);
  p->h = h;
  p->len = len;
  p->str = str;
  h |= strtab->mask;
  p->next = ((uint32_t*)data)[(int32_t)h];
  ((uint32_t*)data)[(int32_t)h] = pos;
  p->val = val;
}

ir_str ir_strtab_update(ir_strtab *strtab, const char *str, uint32_t len, ir_str val)
{
  uint32_t h = ir_str_hash(str, len);
  char *data = (char*)strtab->data;
  uint32_t pos = ((uint32_t*)data)[(int32_t)(h | strtab->mask)];
  ir_strtab_bucket *p;

  while (pos != IR_INVALID_IDX) {
    p = (ir_strtab_bucket*)(data + pos);
    if (p->h == h
     && p->len == len
     && memcmp(p->str, str, len) == 0) {
      return p->val = val;
    }
    pos = p->next;
  }
  return 0;
}

const char *ir_strtab_str(const ir_strtab *strtab, ir_str idx)
{
  IR_ASSERT(idx >= 0 && (uint32_t)idx < strtab->count);
  return ((const ir_strtab_bucket*)strtab->data)[idx].str;
}

const char *ir_strtab_strl(const ir_strtab *strtab, ir_str idx, size_t *len)
{
  const ir_strtab_bucket *b = ((const ir_strtab_bucket*)strtab->data) + idx;
  IR_ASSERT(idx >= 0 && (uint32_t)idx < strtab->count);
  *len = b->len;
  return b->str;
}

void ir_strtab_free(ir_strtab *strtab)
{
  uint32_t hash_size = (uint32_t)(-(int32_t)strtab->mask);
  char *data = (char*)strtab->data - (hash_size * sizeof(uint32_t));
  ir_mem_free(data);
  strtab->data = NULL;
  if (strtab->buf) {
    ir_mem_free(strtab->buf);
    strtab->buf = NULL;
  }
}

void ir_strtab_apply(const ir_strtab *strtab, ir_strtab_apply_t func)
{
  uint32_t i;

  for (i = 0; i < strtab->count; i++) {
    const ir_strtab_bucket *b = &((ir_strtab_bucket*)strtab->data)[i];
    func(b->str, b->len, b->val);
  }
}

Coverage Report

Created: 2026-10-28 06:20

Line	Count	Source
1		/*
2		* IR - Lightweight JIT Compilation Framework
3		* (String table)
4		* This file is part of the IR Project distributed under the MIT-style LICENSE.
5		* Authors: Dmitry Stogov <dmitry@php.net>
6		*/
7
8		#include "ir.h"
9		#include "ir_private.h"
10
11		typedef struct _ir_strtab_bucket {
12		uint32_t h;
13		uint32_t len;
14		const char *str;
15		uint32_t next;
16		ir_str val;
17		} ir_strtab_bucket;
18
19		static uint32_t ir_str_hash(const char *str, size_t len)
20	64	{
21	64	size_t i;
22	64	uint32_t h = 5381;
23
24	296	for (i = 0; i < len; i++) {
25	232	h = ((h << 5) + h) + *str;
26	232	str++;
27	232	}
28	64	return h \| 0x10000000;
29	64	}
30
31		static uint32_t ir_strtab_hash_size(uint32_t size)
32	44	{
33		/* Use big enough power of 2 */
34	44	size -= 1;
35	44	size \|= (size >> 1);
36	44	size \|= (size >> 2);
37	44	size \|= (size >> 4);
38	44	size \|= (size >> 8);
39	44	size \|= (size >> 16);
40	44	return size + 1;
41	44	}
42
43		static void ir_strtab_resize(ir_strtab *strtab)
44	0	{
45	0	uint32_t old_hash_size = (uint32_t)(-(int32_t)strtab->mask);
46	0	char *old_data = strtab->data;
47	0	uint32_t size = strtab->size * 2;
48	0	uint32_t hash_size = ir_strtab_hash_size(size);
49	0	char data = ir_mem_malloc(hash_size sizeof(uint32_t) + size * sizeof(ir_strtab_bucket));
50	0	ir_strtab_bucket *p;
51	0	uint32_t pos, i;
52
53	0	memset(data, IR_INVALID_IDX, hash_size * sizeof(uint32_t));
54	0	strtab->data = data + (hash_size * sizeof(uint32_t));
55	0	strtab->mask = (uint32_t)(-(int32_t)hash_size);
56	0	strtab->size = size;
57
58	0	memcpy(strtab->data, old_data, strtab->count * sizeof(ir_strtab_bucket));
59	0	ir_mem_free(old_data - (old_hash_size * sizeof(uint32_t)));
60
61	0	i = strtab->count;
62	0	pos = 0;
63	0	p = (ir_strtab_bucket*)strtab->data;
64	0	do {
65	0	uint32_t h = p->h \| strtab->mask;
66	0	p->next = ((uint32_t*)strtab->data)[(int32_t)h];
67	0	((uint32_t*)strtab->data)[(int32_t)h] = pos;
68	0	pos += sizeof(ir_strtab_bucket);
69	0	p++;
70	0	} while (--i);
71	0	}
72
73		static void ir_strtab_grow_buf(ir_strtab *strtab, uint32_t len)
74	0	{
75	0	intptr_t old = (intptr_t)strtab->buf;
76
77	0	do {
78	0	strtab->buf_size *= 2;
79	0	} while (UNEXPECTED(strtab->buf_size - strtab->buf_top < len + 1));
80
81	0	strtab->buf = ir_mem_realloc(strtab->buf, strtab->buf_size);
82	0	if ((intptr_t)strtab->buf != old) {
83	0	intptr_t offset = (intptr_t)strtab->buf - old;
84	0	ir_strtab_bucket p = (ir_strtab_bucket)strtab->data;
85	0	uint32_t i;
86	0	for (i = strtab->count; i > 0; i--) {
87	0	p->str += offset;
88	0	p++;
89	0	}
90	0	}
91	0	}
92
93		void ir_strtab_init(ir_strtab *strtab, uint32_t size, uint32_t buf_size)
94	44	{
95	44	IR_ASSERT(size > 0);
96	44	uint32_t hash_size = ir_strtab_hash_size(size);
97	44	char data = ir_mem_malloc(hash_size sizeof(uint32_t) + size * sizeof(ir_strtab_bucket));
98	44	memset(data, IR_INVALID_IDX, hash_size * sizeof(uint32_t));
99	44	strtab->data = (data + (hash_size * sizeof(uint32_t)));
100	44	strtab->mask = (uint32_t)(-(int32_t)hash_size);
101	44	strtab->size = size;
102	44	strtab->count = 0;
103	44	strtab->pos = 0;
104	44	if (buf_size) {
105	44	strtab->buf = ir_mem_malloc(buf_size);
106	44	strtab->buf_size = buf_size;
107	44	strtab->buf_top = 0;
108	44	} else {
109	0	strtab->buf = NULL;
110	0	strtab->buf_size = 0;
111	0	strtab->buf_top = 0;
112	0	}
113	44	}
114
115		ir_str ir_strtab_find(const ir_strtab strtab, const char str, uint32_t len)
116	0	{
117	0	uint32_t h = ir_str_hash(str, len);
118	0	const char data = (const char)strtab->data;
119	0	uint32_t pos = ((uint32_t*)data)[(int32_t)(h \| strtab->mask)];
120	0	ir_strtab_bucket *p;
121
122	0	while (pos != IR_INVALID_IDX) {
123	0	p = (ir_strtab_bucket*)(data + pos);
124	0	if (p->h == h
125	0	&& p->len == len
126	0	&& memcmp(p->str, str, len) == 0) {
127	0	return p->val;
128	0	}
129	0	pos = p->next;
130	0	}
131	0	return 0;
132	0	}
133
134		ir_str ir_strtab_lookup(ir_strtab strtab, const char str, uint32_t len, ir_str val)
135	64	{
136	64	uint32_t h = ir_str_hash(str, len);
137	64	char data = (char)strtab->data;
138	64	uint32_t pos = ((uint32_t*)data)[(int32_t)(h \| strtab->mask)];
139	64	ir_strtab_bucket *p;
140
141	64	while (pos != IR_INVALID_IDX) {
142	0	p = (ir_strtab_bucket*)(data + pos);
143	0	if (p->h == h
144	0	&& p->len == len
145	0	&& memcmp(p->str, str, len) == 0) {
146	0	return p->val;
147	0	}
148	0	pos = p->next;
149	0	}
150
151	64	IR_ASSERT(val != 0);
152
153	64	if (UNEXPECTED(strtab->count >= strtab->size)) {
154	0	ir_strtab_resize(strtab);
155	0	data = strtab->data;
156	0	}
157
158	64	if (strtab->buf) {
159	64	if (UNEXPECTED(strtab->buf_size - strtab->buf_top < len + 1)) {
160	0	ir_strtab_grow_buf(strtab, len + 1);
161	0	}
162
163	64	memcpy(strtab->buf + strtab->buf_top, str, len);
164	64	strtab->buf[strtab->buf_top + len] = 0;
165	64	str = (const char*)strtab->buf + strtab->buf_top;
166	64	strtab->buf_top += len + 1;
167	64	}
168
169	64	pos = strtab->pos;
170	64	strtab->pos += sizeof(ir_strtab_bucket);
171	64	strtab->count++;
172	64	p = (ir_strtab_bucket*)(data + pos);
173	64	p->h = h;
174	64	p->len = len;
175	64	p->str = str;
176	64	h \|= strtab->mask;
177	64	p->next = ((uint32_t*)data)[(int32_t)h];
178	64	((uint32_t*)data)[(int32_t)h] = pos;
179	64	p->val = val;
180	64	return val;
181	64	}
182
183		void ir_strtab_set(ir_strtab strtab, const char str, uint32_t len, ir_str val)
184	0	{
185	0	uint32_t h = ir_str_hash(str, len);
186	0	char data = (char)strtab->data;
187	0	uint32_t pos = ((uint32_t*)data)[(int32_t)(h \| strtab->mask)];
188	0	ir_strtab_bucket *p;
189
190	0	while (pos != IR_INVALID_IDX) {
191	0	p = (ir_strtab_bucket*)(data + pos);
192	0	if (p->h == h
193	0	&& p->len == len
194	0	&& memcmp(p->str, str, len) == 0) {
195	0	p->val = val;
196	0	return;
197	0	}
198	0	pos = p->next;
199	0	}
200
201	0	IR_ASSERT(val != 0);
202
203	0	if (UNEXPECTED(strtab->count >= strtab->size)) {
204	0	ir_strtab_resize(strtab);
205	0	data = strtab->data;
206	0	}
207
208	0	if (strtab->buf) {
209	0	if (UNEXPECTED(strtab->buf_size - strtab->buf_top < len + 1)) {
210	0	ir_strtab_grow_buf(strtab, len + 1);
211	0	}
212
213	0	memcpy(strtab->buf + strtab->buf_top, str, len);
214	0	strtab->buf[strtab->buf_top + len] = 0;
215	0	str = (const char*)strtab->buf + strtab->buf_top;
216	0	strtab->buf_top += len + 1;
217	0	}
218
219	0	pos = strtab->pos;
220	0	strtab->pos += sizeof(ir_strtab_bucket);
221	0	strtab->count++;
222	0	p = (ir_strtab_bucket*)(data + pos);
223	0	p->h = h;
224	0	p->len = len;
225	0	p->str = str;
226	0	h \|= strtab->mask;
227	0	p->next = ((uint32_t*)data)[(int32_t)h];
228	0	((uint32_t*)data)[(int32_t)h] = pos;
229	0	p->val = val;
230	0	}
231
232		ir_str ir_strtab_update(ir_strtab strtab, const char str, uint32_t len, ir_str val)
233	0	{
234	0	uint32_t h = ir_str_hash(str, len);
235	0	char data = (char)strtab->data;
236	0	uint32_t pos = ((uint32_t*)data)[(int32_t)(h \| strtab->mask)];
237	0	ir_strtab_bucket *p;
238
239	0	while (pos != IR_INVALID_IDX) {
240	0	p = (ir_strtab_bucket*)(data + pos);
241	0	if (p->h == h
242	0	&& p->len == len
243	0	&& memcmp(p->str, str, len) == 0) {
244	0	return p->val = val;
245	0	}
246	0	pos = p->next;
247	0	}
248	0	return 0;
249	0	}
250
251		const char ir_strtab_str(const ir_strtab strtab, ir_str idx)
252	44	{
253	44	IR_ASSERT(idx >= 0 && (uint32_t)idx < strtab->count);
254	44	return ((const ir_strtab_bucket*)strtab->data)[idx].str;
255	44	}
256
257		const char ir_strtab_strl(const ir_strtab strtab, ir_str idx, size_t *len)
258	0	{
259	0	const ir_strtab_bucket b = ((const ir_strtab_bucket)strtab->data) + idx;
260	0	IR_ASSERT(idx >= 0 && (uint32_t)idx < strtab->count);
261	0	*len = b->len;
262	0	return b->str;
263	0	}
264
265		void ir_strtab_free(ir_strtab *strtab)
266	44	{
267	44	uint32_t hash_size = (uint32_t)(-(int32_t)strtab->mask);
268	44	char data = (char)strtab->data - (hash_size * sizeof(uint32_t));
269	44	ir_mem_free(data);
270	44	strtab->data = NULL;
271	44	if (strtab->buf) {
272	44	ir_mem_free(strtab->buf);
273	44	strtab->buf = NULL;
274	44	}
275	44	}
276
277		void ir_strtab_apply(const ir_strtab *strtab, ir_strtab_apply_t func)
278	0	{
279	0	uint32_t i;
280
281	0	for (i = 0; i < strtab->count; i++) {
282	0	const ir_strtab_bucket b = &((ir_strtab_bucket)strtab->data)[i];
283	0	func(b->str, b->len, b->val);
284	0	}
285	0	}