Coverage Report

Created: 2025-02-15 06:25

/src/wireshark/wsutil/wmem/wmem_list.c
Line
Count
Source (jump to first uncovered line)
1
/* wmem_list.c
2
 * Wireshark Memory Manager Doubly-Linked List
3
 * Copyright 2012, Evan Huus <eapache@gmail.com>
4
 *
5
 * Wireshark - Network traffic analyzer
6
 * By Gerald Combs <gerald@wireshark.org>
7
 * Copyright 1998 Gerald Combs
8
 *
9
 * SPDX-License-Identifier: GPL-2.0-or-later
10
 */
11
12
#include <string.h>
13
#include <glib.h>
14
15
#include "wmem_core.h"
16
#include "wmem_list.h"
17
18
struct _wmem_list_frame_t {
19
    struct _wmem_list_frame_t *next, *prev;
20
    void *data;
21
};
22
23
struct _wmem_list_t {
24
    unsigned count;
25
    wmem_list_frame_t  *head, *tail;
26
    wmem_allocator_t   *allocator;
27
};
28
29
unsigned
30
wmem_list_count(const wmem_list_t *list)
31
1.86M
{
32
1.86M
    return list->count;
33
1.86M
}
34
35
wmem_list_frame_t *
36
wmem_list_head(const wmem_list_t *list)
37
312k
{
38
312k
    return list->head;
39
312k
}
40
41
wmem_list_frame_t *
42
wmem_list_tail(const wmem_list_t *list)
43
700k
{
44
700k
    return list->tail;
45
700k
}
46
47
wmem_list_frame_t *
48
wmem_list_frame_next(const wmem_list_frame_t *frame)
49
271k
{
50
271k
    return frame->next;
51
271k
}
52
53
wmem_list_frame_t *
54
wmem_list_frame_prev(const wmem_list_frame_t *frame)
55
157k
{
56
157k
    return frame->prev;
57
157k
}
58
59
void *
60
wmem_list_frame_data(const wmem_list_frame_t *frame)
61
1.11M
{
62
1.11M
    return frame->data;
63
1.11M
}
64
65
void
66
wmem_list_remove(wmem_list_t *list, void *data)
67
130k
{
68
130k
    wmem_list_frame_t *frame;
69
70
130k
    frame = list->head;
71
72
130k
    while (frame && frame->data != data) {
73
0
        frame = frame->next;
74
0
    }
75
76
130k
    if (frame == NULL) {
77
0
        return;
78
0
    }
79
80
130k
    wmem_list_remove_frame(list, frame);
81
130k
}
82
83
void
84
wmem_list_remove_frame(wmem_list_t *list, wmem_list_frame_t *frame)
85
444k
{
86
444k
    if (frame->prev) {
87
313k
        frame->prev->next = frame->next;
88
313k
    }
89
130k
    else {
90
130k
        list->head = frame->next;
91
130k
    }
92
93
444k
    if (frame->next) {
94
97.0k
        frame->next->prev = frame->prev;
95
97.0k
    }
96
347k
    else {
97
347k
        list->tail = frame->prev;
98
347k
    }
99
100
444k
    list->count--;
101
444k
    wmem_free(list->allocator, frame);
102
444k
}
103
104
wmem_list_frame_t *
105
wmem_list_find(wmem_list_t *list, const void *data)
106
5.25k
{
107
5.25k
    wmem_list_frame_t *cur;
108
109
33.9k
    for (cur = list->head; cur; cur = cur->next) {
110
28.6k
        if(cur->data == data)
111
0
            return cur;
112
28.6k
    }
113
114
5.25k
    return NULL;
115
5.25k
}
116
117
wmem_list_frame_t *
118
wmem_list_find_custom(wmem_list_t *list, const void *data, GCompareFunc compare_func)
119
9.20k
{
120
9.20k
    wmem_list_frame_t *cur;
121
122
159k
    for (cur = list->head; cur != NULL; cur = cur->next) {
123
153k
        if (compare_func(cur->data, data) == 0) {
124
3.71k
            return cur;
125
3.71k
        }
126
153k
    }
127
128
5.48k
    return NULL;
129
9.20k
}
130
131
void
132
wmem_list_prepend(wmem_list_t *list, void *data)
133
218k
{
134
218k
    wmem_list_frame_t *new_frame;
135
136
218k
    new_frame = wmem_new(list->allocator, wmem_list_frame_t);
137
138
218k
    new_frame->data = data;
139
218k
    new_frame->next = list->head;
140
218k
    new_frame->prev = NULL;
141
142
218k
    if (list->head) {
143
107k
        list->head->prev = new_frame;
144
107k
    }
145
111k
    else {
146
111k
        list->tail = new_frame;
147
111k
    }
148
149
218k
    list->head = new_frame;
150
218k
    list->count++;
151
218k
}
152
153
void
154
wmem_list_append(wmem_list_t *list, void *data)
155
1.17M
{
156
1.17M
    wmem_list_frame_t *new_frame;
157
158
1.17M
    new_frame = wmem_new(list->allocator, wmem_list_frame_t);
159
1.17M
    new_frame->data = data;
160
1.17M
    new_frame->next = NULL;
161
1.17M
    new_frame->prev = list->tail;
162
163
1.17M
    if (list->tail) {
164
1.02M
        list->tail->next = new_frame;
165
1.02M
    }
166
152k
    else {
167
152k
        list->head = new_frame;
168
152k
    }
169
170
1.17M
    list->tail = new_frame;
171
1.17M
    list->count++;
172
1.17M
}
173
174
void
175
wmem_list_insert_sorted(wmem_list_t *list, void* data, GCompareFunc func)
176
7.51k
{
177
7.51k
    wmem_list_frame_t *new_frame;
178
7.51k
    wmem_list_frame_t *cur;
179
7.51k
    wmem_list_frame_t *prev;
180
181
7.51k
    new_frame = wmem_new(list->allocator, wmem_list_frame_t);
182
7.51k
    new_frame->data = data;
183
7.51k
    new_frame->next = NULL;
184
7.51k
    new_frame->prev = NULL;
185
186
7.51k
    list->count++;
187
188
7.51k
    if (!list->head) {
189
1.53k
        list->head = new_frame;
190
1.53k
        list->tail = new_frame;
191
1.53k
        return;
192
1.53k
    }
193
194
5.97k
    cur = list->head;
195
196
5.97k
    if (func(cur->data, data) >= 0) {
197
1.10k
        cur->prev = new_frame;
198
1.10k
        new_frame->next = cur;
199
1.10k
        list->head = new_frame;
200
1.10k
        return;
201
1.10k
    }
202
203
266k
    do {
204
266k
        prev = cur;
205
266k
        cur = cur->next;
206
266k
    } while (cur && func(cur->data, data) <= 0);
207
208
4.86k
    if (!cur) {
209
869
        prev->next = new_frame;
210
869
        new_frame->prev = prev;
211
869
        list->tail = new_frame;
212
869
        return;
213
869
    }
214
215
3.99k
    new_frame->prev = prev;
216
3.99k
    new_frame->next = cur;
217
3.99k
    new_frame->prev->next = new_frame;
218
3.99k
    new_frame->next->prev = new_frame;
219
3.99k
}
220
221
void
222
wmem_list_append_sorted(wmem_list_t *list, void* data, GCompareFunc func)
223
0
{
224
0
    wmem_list_frame_t *new_frame;
225
0
    wmem_list_frame_t *cur;
226
0
    wmem_list_frame_t *next;
227
228
0
    new_frame = wmem_new(list->allocator, wmem_list_frame_t);
229
0
    new_frame->data = data;
230
0
    new_frame->next = NULL;
231
0
    new_frame->prev = NULL;
232
233
0
    list->count++;
234
235
0
    if (!list->head) {
236
0
        list->head = new_frame;
237
0
        list->tail = new_frame;
238
0
        return;
239
0
    }
240
241
0
    cur = list->tail;
242
243
    /* best case scenario: append */
244
0
    if (func(cur->data, data) <= 0) {
245
0
        cur->next = new_frame;
246
0
        new_frame->prev = cur;
247
0
        list->tail = new_frame;
248
0
        return;
249
0
    }
250
251
0
    do {
252
0
        next = cur;
253
0
        cur = cur->prev;
254
0
    } while (cur && func(cur->data, data) >= 0);
255
256
    /* worst case scenario: prepend */
257
0
    if (!cur) {
258
0
        next->prev = new_frame;
259
0
        new_frame->next = next;
260
0
        list->head = new_frame;
261
0
        return;
262
0
    }
263
264
    /* ordinary case: insert */
265
0
    new_frame->next = next;
266
0
    new_frame->prev = cur;
267
0
    new_frame->prev->next = new_frame;
268
0
    new_frame->next->prev = new_frame;
269
0
}
270
271
wmem_list_t *
272
wmem_list_new(wmem_allocator_t *allocator)
273
823k
{
274
823k
    wmem_list_t *list;
275
276
823k
    list =  wmem_new(allocator, wmem_list_t);
277
278
823k
    list->count     = 0;
279
823k
    list->head      = NULL;
280
823k
    list->tail      = NULL;
281
823k
    list->allocator = allocator;
282
283
823k
    return list;
284
823k
}
285
286
void
287
wmem_destroy_list(wmem_list_t *list)
288
206k
{
289
206k
    wmem_list_frame_t *cur, *next;
290
291
206k
    cur = list->head;
292
293
225k
    while (cur) {
294
18.4k
        next = cur->next;
295
18.4k
        wmem_free(list->allocator, cur);
296
18.4k
        cur = next;
297
18.4k
    }
298
299
206k
    wmem_free(list->allocator, list);
300
206k
}
301
302
void
303
wmem_list_foreach(wmem_list_t *list, GFunc foreach_func, void * user_data)
304
287k
{
305
287k
    wmem_list_frame_t *cur;
306
307
287k
    cur = list->head;
308
309
341k
    while (cur) {
310
53.8k
        foreach_func(cur->data, user_data);
311
53.8k
        cur = cur->next;
312
53.8k
    }
313
287k
}
314
315
/*
316
 * Editor modelines  -  https://www.wireshark.org/tools/modelines.html
317
 *
318
 * Local variables:
319
 * c-basic-offset: 4
320
 * tab-width: 8
321
 * indent-tabs-mode: nil
322
 * End:
323
 *
324
 * vi: set shiftwidth=4 tabstop=8 expandtab:
325
 * :indentSize=4:tabSize=8:noTabs=true:
326
 */