1 /***************************************************************************
2 * Copyright (c) 2009-2010 Open Information Security Foundation
3 * Copyright (c) 2010-2013 Qualys, Inc.
4 * All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions are
8 * met:
9 *
10 * - Redistributions of source code must retain the above copyright
11 * notice, this list of conditions and the following disclaimer.
12
13 * - Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in the
15 * documentation and/or other materials provided with the distribution.
16
17 * - Neither the name of the Qualys, Inc. nor the names of its
18 * contributors may be used to endorse or promote products derived from
19 * this software without specific prior written permission.
20 *
21 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
24 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
25 * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
26 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
27 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
28 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
29 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
30 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
31 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
32 ***************************************************************************/
33
34 /**
35 * @file
36 * @author Ivan Ristic <ivanr@webkreator.com>
37 */
38
39 #include "htp_config_auto.h"
40
41 #include "htp_private.h"
42
43 // Array-backed list
44
htp_list_array_init(htp_list_t * l,size_t size)45 htp_status_t htp_list_array_init(htp_list_t *l, size_t size) {
46 // Allocate the initial batch of elements.
47 l->elements = malloc(size * sizeof (void *));
48 if (l->elements == NULL) {
49 return HTP_ERROR;
50 }
51
52 // Initialize the structure.
53 l->first = 0;
54 l->last = 0;
55 l->current_size = 0;
56 l->max_size = size;
57
58 return HTP_OK;
59 }
60
htp_list_array_create(size_t size)61 htp_list_t *htp_list_array_create(size_t size) {
62 // It makes no sense to create a zero-size list.
63 if (size == 0) return NULL;
64
65 // Allocate the list structure.
66 htp_list_array_t *l = calloc(1, sizeof (htp_list_array_t));
67 if (l == NULL) return NULL;
68
69 if (htp_list_array_init(l, size) == HTP_ERROR) {
70 free(l);
71 return NULL;
72 }
73
74 return (htp_list_t *) l;
75 }
76
htp_list_array_clear(htp_list_array_t * l)77 void htp_list_array_clear(htp_list_array_t *l) {
78 if (l == NULL) return;
79
80 // Continue using already allocated memory; just reset the fields.
81 l->first = 0;
82 l->last = 0;
83 l->current_size = 0;
84 }
85
htp_list_array_destroy(htp_list_array_t * l)86 void htp_list_array_destroy(htp_list_array_t *l) {
87 if (l == NULL) return;
88
89 free(l->elements);
90 free(l);
91 }
92
htp_list_array_release(htp_list_array_t * l)93 void htp_list_array_release(htp_list_array_t *l) {
94 if (l == NULL) return;
95
96 free(l->elements);
97 }
98
htp_list_array_get(const htp_list_array_t * l,size_t idx)99 void *htp_list_array_get(const htp_list_array_t *l, size_t idx) {
100 if (l == NULL) return NULL;
101 if (idx + 1 > l->current_size) return NULL;
102
103 if (l->first + idx < l->max_size) {
104 return (void *) l->elements[l->first + idx];
105 } else {
106 return (void *) l->elements[idx - (l->max_size - l->first)];
107 }
108 }
109
htp_list_array_pop(htp_list_array_t * l)110 void *htp_list_array_pop(htp_list_array_t *l) {
111 if (l == NULL) return NULL;
112
113 const void *r = NULL;
114
115 if (l->current_size == 0) {
116 return NULL;
117 }
118
119 size_t pos = l->first + l->current_size - 1;
120 if (pos > l->max_size - 1) pos -= l->max_size;
121
122 r = l->elements[pos];
123 l->last = pos;
124
125 l->current_size--;
126
127 return (void *) r;
128 }
129
htp_list_array_push(htp_list_array_t * l,void * e)130 htp_status_t htp_list_array_push(htp_list_array_t *l, void *e) {
131 if (l == NULL) return HTP_ERROR;
132
133 // Check whether we're full
134 if (l->current_size >= l->max_size) {
135 size_t new_size = l->max_size * 2;
136 void *newblock = NULL;
137
138 if (l->first == 0) {
139 // The simple case of expansion is when the first
140 // element in the list resides in the first slot. In
141 // that case we just add some new space to the end,
142 // adjust the max_size and that's that.
143 newblock = realloc(l->elements, new_size * sizeof (void *));
144 if (newblock == NULL) return HTP_ERROR;
145 } else {
146 // When the first element is not in the first
147 // memory slot, we need to rearrange the order
148 // of the elements in order to expand the storage area.
149 /* coverity[suspicious_sizeof] */
150 newblock = malloc((size_t) (new_size * sizeof (void *)));
151 if (newblock == NULL) return HTP_ERROR;
152
153 // Copy the beginning of the list to the beginning of the new memory block
154 /* coverity[suspicious_sizeof] */
155 memcpy(newblock,
156 (void *) ((char *) l->elements + l->first * sizeof (void *)),
157 (size_t) ((l->max_size - l->first) * sizeof (void *)));
158
159 // Append the second part of the list to the end
160 memcpy((void *) ((char *) newblock + (l->max_size - l->first) * sizeof (void *)),
161 (void *) l->elements,
162 (size_t) (l->first * sizeof (void *)));
163
164 free(l->elements);
165 }
166
167 l->first = 0;
168 l->last = l->current_size;
169 l->max_size = new_size;
170 l->elements = newblock;
171 }
172
173 l->elements[l->last] = e;
174 l->current_size++;
175
176 l->last++;
177 if (l->last == l->max_size) {
178 l->last = 0;
179 }
180
181 return HTP_OK;
182 }
183
htp_list_array_replace(htp_list_array_t * l,size_t idx,void * e)184 htp_status_t htp_list_array_replace(htp_list_array_t *l, size_t idx, void *e) {
185 if (l == NULL) return HTP_ERROR;
186
187 if (idx + 1 > l->current_size) return HTP_DECLINED;
188
189 l->elements[(l->first + idx) % l->max_size] = e;
190
191 return HTP_OK;
192 }
193
htp_list_array_size(const htp_list_array_t * l)194 size_t htp_list_array_size(const htp_list_array_t *l) {
195 if (l == NULL) return HTP_ERROR;
196
197 return l->current_size;
198 }
199
htp_list_array_shift(htp_list_array_t * l)200 void *htp_list_array_shift(htp_list_array_t *l) {
201 if (l == NULL) return NULL;
202
203 void *r = NULL;
204
205 if (l->current_size == 0) {
206 return NULL;
207 }
208
209 r = l->elements[l->first];
210 l->first++;
211 if (l->first == l->max_size) {
212 l->first = 0;
213 }
214
215 l->current_size--;
216
217 return r;
218 }
219
220 #if 0
221 // Linked list
222
223 htp_list_linked_t *htp_list_linked_create(void) {
224 htp_list_linked_t *l = calloc(1, sizeof (htp_list_linked_t));
225 if (l == NULL) return NULL;
226
227 return l;
228 }
229
230 void htp_list_linked_destroy(htp_list_linked_t *l) {
231 if (l == NULL) return;
232
233 // Free the list structures
234 htp_list_linked_element_t *temp = l->first;
235 htp_list_linked_element_t *prev = NULL;
236 while (temp != NULL) {
237 free(temp->data);
238 prev = temp;
239 temp = temp->next;
240 free(prev);
241 }
242
243 // Free the list itself
244 free(l);
245 }
246
247 int htp_list_linked_empty(const htp_list_linked_t *l) {
248 if (!l->first) {
249 return 1;
250 } else {
251 return 0;
252 }
253 }
254
255 void *htp_list_linked_pop(htp_list_linked_t *l) {
256 void *r = NULL;
257
258 if (!l->first) {
259 return NULL;
260 }
261
262 // Find the last element
263 htp_list_linked_element_t *qprev = NULL;
264 htp_list_linked_element_t *qe = l->first;
265 while (qe->next != NULL) {
266 qprev = qe;
267 qe = qe->next;
268 }
269
270 r = qe->data;
271 free(qe);
272
273 if (qprev != NULL) {
274 qprev->next = NULL;
275 l->last = qprev;
276 } else {
277 l->first = NULL;
278 l->last = NULL;
279 }
280
281 return r;
282 }
283
284 int htp_list_linked_push(htp_list_linked_t *l, void *e) {
285 htp_list_linked_element_t *le = calloc(1, sizeof (htp_list_linked_element_t));
286 if (le == NULL) return -1;
287
288 // Remember the element
289 le->data = e;
290
291 // If the queue is empty, make this element first
292 if (!l->first) {
293 l->first = le;
294 }
295
296 if (l->last) {
297 l->last->next = le;
298 }
299
300 l->last = le;
301
302 return 1;
303 }
304
305 void *htp_list_linked_shift(htp_list_linked_t *l) {
306 void *r = NULL;
307
308 if (!l->first) {
309 return NULL;
310 }
311
312 htp_list_linked_element_t *le = l->first;
313 l->first = le->next;
314 r = le->data;
315
316 if (!l->first) {
317 l->last = NULL;
318 }
319
320 free(le);
321
322 return r;
323 }
324 #endif
325
326 #if 0
327
328 int main(int argc, char **argv) {
329 htp_list_t *q = htp_list_array_create(4);
330
331 htp_list_push(q, "1");
332 htp_list_push(q, "2");
333 htp_list_push(q, "3");
334 htp_list_push(q, "4");
335
336 htp_list_shift(q);
337 htp_list_push(q, "5");
338 htp_list_push(q, "6");
339
340 char *s = NULL;
341 while ((s = (char *) htp_list_pop(q)) != NULL) {
342 printf("Got: %s\n", s);
343 }
344
345 printf("---\n");
346
347 htp_list_push(q, "1");
348 htp_list_push(q, "2");
349 htp_list_push(q, "3");
350 htp_list_push(q, "4");
351
352 while ((s = (char *) htp_list_shift(q)) != NULL) {
353 printf("Got: %s\n", s);
354 }
355
356 free(q);
357
358 return 0;
359 }
360 #endif
361