Coverage Report

Created: 2025-06-13 06:43

/src/php-src/Zend/zend_llist.c
Line
Count
Source (jump to first uncovered line)
1
/*
2
   +----------------------------------------------------------------------+
3
   | Zend Engine                                                          |
4
   +----------------------------------------------------------------------+
5
   | Copyright (c) Zend Technologies Ltd. (http://www.zend.com)           |
6
   +----------------------------------------------------------------------+
7
   | This source file is subject to version 2.00 of the Zend license,     |
8
   | that is bundled with this package in the file LICENSE, and is        |
9
   | available through the world-wide-web at the following url:           |
10
   | http://www.zend.com/license/2_00.txt.                                |
11
   | If you did not receive a copy of the Zend license and are unable to  |
12
   | obtain it through the world-wide-web, please send a note to          |
13
   | license@zend.com so we can mail you a copy immediately.              |
14
   +----------------------------------------------------------------------+
15
   | Authors: Andi Gutmans <andi@php.net>                                 |
16
   |          Zeev Suraski <zeev@php.net>                                 |
17
   +----------------------------------------------------------------------+
18
*/
19
20
#include "zend.h"
21
#include "zend_llist.h"
22
#include "zend_sort.h"
23
24
ZEND_API void zend_llist_init(zend_llist *l, size_t size, llist_dtor_func_t dtor, unsigned char persistent)
25
600k
{
26
600k
  l->head  = NULL;
27
600k
  l->tail  = NULL;
28
600k
  l->count = 0;
29
600k
  l->size  = size;
30
600k
  l->dtor  = dtor;
31
600k
  l->persistent = persistent;
32
600k
}
33
34
ZEND_API void zend_llist_add_element(zend_llist *l, const void *element)
35
444k
{
36
444k
  zend_llist_element *tmp = pemalloc(sizeof(zend_llist_element)+l->size-1, l->persistent);
37
38
444k
  tmp->prev = l->tail;
39
444k
  tmp->next = NULL;
40
444k
  if (l->tail) {
41
69
    l->tail->next = tmp;
42
444k
  } else {
43
444k
    l->head = tmp;
44
444k
  }
45
444k
  l->tail = tmp;
46
444k
  memcpy(tmp->data, element, l->size);
47
48
444k
  ++l->count;
49
444k
}
50
51
52
ZEND_API void zend_llist_prepend_element(zend_llist *l, const void *element)
53
0
{
54
0
  zend_llist_element *tmp = pemalloc(sizeof(zend_llist_element)+l->size-1, l->persistent);
55
56
0
  tmp->next = l->head;
57
0
  tmp->prev = NULL;
58
0
  if (l->head) {
59
0
    l->head->prev = tmp;
60
0
  } else {
61
0
    l->tail = tmp;
62
0
  }
63
0
  l->head = tmp;
64
0
  memcpy(tmp->data, element, l->size);
65
66
0
  ++l->count;
67
0
}
68
69
70
#define DEL_LLIST_ELEMENT(current, l) \
71
138k
      if ((current)->prev) {\
72
0
        (current)->prev->next = (current)->next;\
73
138k
      } else {\
74
138k
        (l)->head = (current)->next;\
75
138k
      }\
76
138k
      if ((current)->next) {\
77
0
        (current)->next->prev = (current)->prev;\
78
138k
      } else {\
79
138k
        (l)->tail = (current)->prev;\
80
138k
      }\
81
138k
      if ((l)->dtor) {\
82
138k
        (l)->dtor((current)->data);\
83
138k
      }\
84
138k
      pefree((current), (l)->persistent);\
85
138k
      --l->count;
86
87
88
ZEND_API void zend_llist_del_element(zend_llist *l, void *element, int (*compare)(void *element1, void *element2))
89
138k
{
90
138k
  zend_llist_element *current=l->head;
91
92
138k
  while (current) {
93
138k
    if (compare(current->data, element)) {
94
138k
      DEL_LLIST_ELEMENT(current, l);
95
138k
      break;
96
138k
    }
97
0
    current = current->next;
98
0
  }
99
138k
}
100
101
102
ZEND_API void zend_llist_destroy(zend_llist *l)
103
900k
{
104
900k
  zend_llist_element *current=l->head, *next;
105
106
1.20M
  while (current) {
107
306k
    next = current->next;
108
306k
    if (l->dtor) {
109
306k
      l->dtor(current->data);
110
306k
    }
111
306k
    pefree(current, l->persistent);
112
306k
    current = next;
113
306k
  }
114
115
900k
  l->head  = NULL;
116
900k
  l->tail  = NULL;
117
900k
  l->count = 0;
118
900k
}
119
120
121
ZEND_API void zend_llist_clean(zend_llist *l)
122
300k
{
123
300k
  zend_llist_destroy(l);
124
300k
  l->head = l->tail = NULL;
125
300k
}
126
127
128
ZEND_API void zend_llist_remove_tail(zend_llist *l)
129
0
{
130
0
  zend_llist_element *old_tail = l->tail;
131
0
  if (!old_tail) {
132
0
    return;
133
0
  }
134
135
0
  if (old_tail->prev) {
136
0
    old_tail->prev->next = NULL;
137
0
  } else {
138
0
    l->head = NULL;
139
0
  }
140
141
0
  l->tail = old_tail->prev;
142
0
  --l->count;
143
144
0
  if (l->dtor) {
145
0
    l->dtor(old_tail->data);
146
0
  }
147
0
  pefree(old_tail, l->persistent);
148
0
}
149
150
151
ZEND_API void zend_llist_copy(zend_llist *dst, zend_llist *src)
152
0
{
153
0
  zend_llist_element *ptr;
154
155
0
  zend_llist_init(dst, src->size, src->dtor, src->persistent);
156
0
  ptr = src->head;
157
0
  while (ptr) {
158
0
    zend_llist_add_element(dst, ptr->data);
159
0
    ptr = ptr->next;
160
0
  }
161
0
}
162
163
164
ZEND_API void zend_llist_apply_with_del(zend_llist *l, int (*func)(void *data))
165
16
{
166
16
  zend_llist_element *element, *next;
167
168
16
  element=l->head;
169
20
  while (element) {
170
4
    next = element->next;
171
4
    if (func(element->data)) {
172
0
      DEL_LLIST_ELEMENT(element, l);
173
0
    }
174
4
    element = next;
175
4
  }
176
16
}
177
178
179
ZEND_API void zend_llist_apply(zend_llist *l, llist_apply_func_t func)
180
600k
{
181
600k
  zend_llist_element *element;
182
183
798k
  for (element=l->head; element; element=element->next) {
184
197k
    func(element->data);
185
197k
  }
186
600k
}
187
188
static void zend_llist_swap(zend_llist_element **p, zend_llist_element **q)
189
0
{
190
0
  zend_llist_element *t;
191
0
  t = *p;
192
0
  *p = *q;
193
0
  *q = t;
194
0
}
195
196
ZEND_API void zend_llist_sort(zend_llist *l, llist_compare_func_t comp_func)
197
0
{
198
0
  size_t i;
199
200
0
  zend_llist_element **elements;
201
0
  zend_llist_element *element, **ptr;
202
203
0
  if (l->count == 0) {
204
0
    return;
205
0
  }
206
207
0
  elements = (zend_llist_element **) emalloc(l->count * sizeof(zend_llist_element *));
208
209
0
  ptr = &elements[0];
210
211
0
  for (element=l->head; element; element=element->next) {
212
0
    *ptr++ = element;
213
0
  }
214
215
0
  zend_sort(elements, l->count, sizeof(zend_llist_element *),
216
0
      (compare_func_t) comp_func, (swap_func_t) zend_llist_swap);
217
218
0
  l->head = elements[0];
219
0
  elements[0]->prev = NULL;
220
221
0
  for (i = 1; i < l->count; i++) {
222
0
    elements[i]->prev = elements[i-1];
223
0
    elements[i-1]->next = elements[i];
224
0
  }
225
0
  elements[i-1]->next = NULL;
226
0
  l->tail = elements[i-1];
227
0
  efree(elements);
228
0
}
229
230
231
ZEND_API void zend_llist_apply_with_argument(zend_llist *l, llist_apply_with_arg_func_t func, void *arg)
232
300k
{
233
300k
  zend_llist_element *element;
234
235
600k
  for (element=l->head; element; element=element->next) {
236
300k
    func(element->data, arg);
237
300k
  }
238
300k
}
239
240
241
ZEND_API void zend_llist_apply_with_arguments(zend_llist *l, llist_apply_with_args_func_t func, int num_args, ...)
242
4
{
243
4
  zend_llist_element *element;
244
4
  va_list args;
245
246
4
  va_start(args, num_args);
247
4
  for (element=l->head; element; element=element->next) {
248
0
    func(element->data, num_args, args);
249
0
  }
250
4
  va_end(args);
251
4
}
252
253
254
ZEND_API size_t zend_llist_count(zend_llist *l)
255
12
{
256
12
  return l->count;
257
12
}
258
259
260
ZEND_API void *zend_llist_get_first_ex(zend_llist *l, zend_llist_position *pos)
261
24
{
262
24
  zend_llist_position *current = pos ? pos : &l->traverse_ptr;
263
264
24
  *current = l->head;
265
24
  if (*current) {
266
24
    return (*current)->data;
267
24
  } else {
268
0
    return NULL;
269
0
  }
270
24
}
271
272
273
ZEND_API void *zend_llist_get_last_ex(zend_llist *l, zend_llist_position *pos)
274
0
{
275
0
  zend_llist_position *current = pos ? pos : &l->traverse_ptr;
276
277
0
  *current = l->tail;
278
0
  if (*current) {
279
0
    return (*current)->data;
280
0
  } else {
281
0
    return NULL;
282
0
  }
283
0
}
284
285
286
ZEND_API void *zend_llist_get_next_ex(zend_llist *l, zend_llist_position *pos)
287
24
{
288
24
  zend_llist_position *current = pos ? pos : &l->traverse_ptr;
289
290
24
  if (*current) {
291
24
    *current = (*current)->next;
292
24
    if (*current) {
293
0
      return (*current)->data;
294
0
    }
295
24
  }
296
24
  return NULL;
297
24
}
298
299
300
ZEND_API void *zend_llist_get_prev_ex(zend_llist *l, zend_llist_position *pos)
301
0
{
302
0
  zend_llist_position *current = pos ? pos : &l->traverse_ptr;
303
304
0
  if (*current) {
305
0
    *current = (*current)->prev;
306
0
    if (*current) {
307
0
      return (*current)->data;
308
0
    }
309
0
  }
310
0
  return NULL;
311
0
}