/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 | | */ |