/src/libhtp/htp/htp_list.c

Source (jump to first uncovered line)
/***************************************************************************
 * Copyright (c) 2009-2010 Open Information Security Foundation
 * Copyright (c) 2010-2013 Qualys, Inc.
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are
 * met:
 *
 * - Redistributions of source code must retain the above copyright
 *   notice, this list of conditions and the following disclaimer.

 * - Redistributions in binary form must reproduce the above copyright
 *   notice, this list of conditions and the following disclaimer in the
 *   documentation and/or other materials provided with the distribution.

 * - Neither the name of the Qualys, Inc. nor the names of its
 *   contributors may be used to endorse or promote products derived from
 *   this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 ***************************************************************************/

/**
 * @file
 * @author Ivan Ristic <ivanr@webkreator.com>
 */

#include "htp_config_auto.h"

#include "htp_private.h"

// Array-backed list

htp_status_t htp_list_array_init(htp_list_t *l, size_t size) {
    // Allocate the initial batch of elements.
    l->elements = malloc(size * sizeof (void *));
    if (l->elements == NULL) {
        return HTP_ERROR;
    }

    // Initialize the structure.
    l->first = 0;
    l->last = 0;
    l->current_size = 0;
    l->max_size = size;

    return HTP_OK;
}

htp_list_t *htp_list_array_create(size_t size) {
    // It makes no sense to create a zero-size list.
    if (size == 0) return NULL;

    // Allocate the list structure.
    htp_list_array_t *l = calloc(1, sizeof (htp_list_array_t));
    if (l == NULL) return NULL;

    if (htp_list_array_init(l, size) == HTP_ERROR) {
        free(l);
        return NULL;
    }

    return (htp_list_t *) l;
}

void htp_list_array_clear(htp_list_array_t *l) {
    if (l == NULL) return;

    // Continue using already allocated memory; just reset the fields.
    l->first = 0;
    l->last = 0;
    l->current_size = 0;
}

void htp_list_array_destroy(htp_list_array_t *l) {
    if (l == NULL) return;

    free(l->elements);
    free(l);
}

void htp_list_array_release(htp_list_array_t *l) {
    if (l == NULL) return;

    free(l->elements);
}

void *htp_list_array_get(const htp_list_array_t *l, size_t idx) {
    if (l == NULL) return NULL;    
    if (idx >= l->current_size) return NULL;
    
    if (l->first + idx < l->max_size) {
        return (void *) l->elements[l->first + idx];
    } else {        
        return (void *) l->elements[idx - (l->max_size - l->first)];
    }
}

void *htp_list_array_pop(htp_list_array_t *l) {
    if (l == NULL) return NULL;

    const void *r = NULL;

    if (l->current_size == 0) {
        return NULL;
    }

    size_t pos = l->first + l->current_size - 1;
    if (pos > l->max_size - 1) pos -= l->max_size;

    r = l->elements[pos];
    l->last = pos;

    l->current_size--;

    return (void *) r;
}

htp_status_t htp_list_array_push(htp_list_array_t *l, void *e) {
    if (l == NULL) return HTP_ERROR;

    // Check whether we're full
    if (l->current_size >= l->max_size) {
        size_t new_size = l->max_size * 2;
        void *newblock = NULL;

        if (l->first == 0) {
            // The simple case of expansion is when the first
            // element in the list resides in the first slot. In
            // that case we just add some new space to the end,
            // adjust the max_size and that's that.
            newblock = realloc(l->elements, new_size * sizeof (void *));
            if (newblock == NULL) return HTP_ERROR;
        } else {
            // When the first element is not in the first
            // memory slot, we need to rearrange the order
            // of the elements in order to expand the storage area.
            /* coverity[suspicious_sizeof] */
            newblock = malloc((size_t) (new_size * sizeof (void *)));
            if (newblock == NULL) return HTP_ERROR;

            // Copy the beginning of the list to the beginning of the new memory block
            /* coverity[suspicious_sizeof] */
            memcpy(newblock,
                    (void *) ((char *) l->elements + l->first * sizeof (void *)),
                    (size_t) ((l->max_size - l->first) * sizeof (void *)));

            // Append the second part of the list to the end
            memcpy((void *) ((char *) newblock + (l->max_size - l->first) * sizeof (void *)),
                    (void *) l->elements,
                    (size_t) (l->first * sizeof (void *)));

            free(l->elements);
        }

        l->first = 0;
        l->last = l->current_size;
        l->max_size = new_size;
        l->elements = newblock;
    }

    l->elements[l->last] = e;
    l->current_size++;

    l->last++;
    if (l->last == l->max_size) {
        l->last = 0;
    }

    return HTP_OK;
}

htp_status_t htp_list_array_replace(htp_list_array_t *l, size_t idx, void *e) {
    if (l == NULL) return HTP_ERROR;

    if (idx + 1 > l->current_size) return HTP_DECLINED;

    l->elements[(l->first + idx) % l->max_size] = e;

    return HTP_OK;
}

size_t htp_list_array_size(const htp_list_array_t *l) {
    if (l == NULL) return HTP_ERROR;

    return l->current_size;
}

void *htp_list_array_shift(htp_list_array_t *l) {
    if (l == NULL) return NULL;

    void *r = NULL;

    if (l->current_size == 0) {
        return NULL;
    }

    r = l->elements[l->first];
    l->first++;
    if (l->first == l->max_size) {
        l->first = 0;
    }

    l->current_size--;

    return r;
}

#if 0
// Linked list

htp_list_linked_t *htp_list_linked_create(void) {
    htp_list_linked_t *l = calloc(1, sizeof (htp_list_linked_t));
    if (l == NULL) return NULL;

    return l;
}

void htp_list_linked_destroy(htp_list_linked_t *l) {
    if (l == NULL) return;

    // Free the list structures
    htp_list_linked_element_t *temp = l->first;
    htp_list_linked_element_t *prev = NULL;
    while (temp != NULL) {
        free(temp->data);
        prev = temp;
        temp = temp->next;
        free(prev);
    }

    // Free the list itself
    free(l);
}

int htp_list_linked_empty(const htp_list_linked_t *l) {
    if (!l->first) {
        return 1;
    } else {
        return 0;
    }
}

void *htp_list_linked_pop(htp_list_linked_t *l) {
    void *r = NULL;

    if (!l->first) {
        return NULL;
    }

    // Find the last element
    htp_list_linked_element_t *qprev = NULL;
    htp_list_linked_element_t *qe = l->first;
    while (qe->next != NULL) {
        qprev = qe;
        qe = qe->next;
    }

    r = qe->data;
    free(qe);

    if (qprev != NULL) {
        qprev->next = NULL;
        l->last = qprev;
    } else {
        l->first = NULL;
        l->last = NULL;
    }

    return r;
}

int htp_list_linked_push(htp_list_linked_t *l, void *e) {
    htp_list_linked_element_t *le = calloc(1, sizeof (htp_list_linked_element_t));
    if (le == NULL) return -1;

    // Remember the element
    le->data = e;

    // If the queue is empty, make this element first
    if (!l->first) {
        l->first = le;
    }

    if (l->last) {
        l->last->next = le;
    }

    l->last = le;

    return 1;
}

void *htp_list_linked_shift(htp_list_linked_t *l) {
    void *r = NULL;

    if (!l->first) {
        return NULL;
    }

    htp_list_linked_element_t *le = l->first;
    l->first = le->next;
    r = le->data;

    if (!l->first) {
        l->last = NULL;
    }

    free(le);

    return r;
}
#endif

#if 0

int main(int argc, char **argv) {
    htp_list_t *q = htp_list_array_create(4);

    htp_list_push(q, "1");
    htp_list_push(q, "2");
    htp_list_push(q, "3");
    htp_list_push(q, "4");

    htp_list_shift(q);
    htp_list_push(q, "5");
    htp_list_push(q, "6");

    char *s = NULL;
    while ((s = (char *) htp_list_pop(q)) != NULL) {
        printf("Got: %s\n", s);
    }

    printf("---\n");

    htp_list_push(q, "1");
    htp_list_push(q, "2");
    htp_list_push(q, "3");
    htp_list_push(q, "4");

    while ((s = (char *) htp_list_shift(q)) != NULL) {
        printf("Got: %s\n", s);
    }

    free(q);

    return 0;
}
#endif

Coverage Report

Created: 2025-07-11 06:42

Line	Count	Source (jump to first uncovered line)
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
45	438k	htp_status_t htp_list_array_init(htp_list_t *l, size_t size) {
46		// Allocate the initial batch of elements.
47	438k	l->elements = malloc(size * sizeof (void *));
48	438k	if (l->elements == NULL) {
49	0	return HTP_ERROR;
50	0	}
51
52		// Initialize the structure.
53	438k	l->first = 0;
54	438k	l->last = 0;
55	438k	l->current_size = 0;
56	438k	l->max_size = size;
57
58	438k	return HTP_OK;
59	438k	}
60
61	158k	htp_list_t *htp_list_array_create(size_t size) {
62		// It makes no sense to create a zero-size list.
63	158k	if (size == 0) return NULL;
64
65		// Allocate the list structure.
66	158k	htp_list_array_t *l = calloc(1, sizeof (htp_list_array_t));
67	158k	if (l == NULL) return NULL;
68
69	158k	if (htp_list_array_init(l, size) == HTP_ERROR) {
70	0	free(l);
71	0	return NULL;
72	0	}
73
74	158k	return (htp_list_t *) l;
75	158k	}
76
77	300k	void htp_list_array_clear(htp_list_array_t *l) {
78	300k	if (l == NULL) return;
79
80		// Continue using already allocated memory; just reset the fields.
81	300k	l->first = 0;
82	300k	l->last = 0;
83	300k	l->current_size = 0;
84	300k	}
85
86	158k	void htp_list_array_destroy(htp_list_array_t *l) {
87	158k	if (l == NULL) return;
88
89	158k	free(l->elements);
90	158k	free(l);
91	158k	}
92
93	279k	void htp_list_array_release(htp_list_array_t *l) {
94	279k	if (l == NULL) return;
95
96	279k	free(l->elements);
97	279k	}
98
99	18.2M	void htp_list_array_get(const htp_list_array_t l, size_t idx) {
100	18.2M	if (l == NULL) return NULL;
101	18.2M	if (idx >= l->current_size) return NULL;
102
103	18.2M	if (l->first + idx < l->max_size) {
104	18.2M	return (void *) l->elements[l->first + idx];
105	18.2M	} else {
106	0	return (void *) l->elements[idx - (l->max_size - l->first)];
107	0	}
108	18.2M	}
109
110	0	void htp_list_array_pop(htp_list_array_t l) {
111	0	if (l == NULL) return NULL;
112
113	0	const void *r = NULL;
114
115	0	if (l->current_size == 0) {
116	0	return NULL;
117	0	}
118
119	0	size_t pos = l->first + l->current_size - 1;
120	0	if (pos > l->max_size - 1) pos -= l->max_size;
121
122	0	r = l->elements[pos];
123	0	l->last = pos;
124
125	0	l->current_size--;
126
127	0	return (void *) r;
128	0	}
129
130	3.63M	htp_status_t htp_list_array_push(htp_list_array_t l, void e) {
131	3.63M	if (l == NULL) return HTP_ERROR;
132
133		// Check whether we're full
134	3.63M	if (l->current_size >= l->max_size) {
135	11.3k	size_t new_size = l->max_size * 2;
136	11.3k	void *newblock = NULL;
137
138	11.3k	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	11.3k	newblock = realloc(l->elements, new_size * sizeof (void *));
144	11.3k	if (newblock == NULL) return HTP_ERROR;
145	11.3k	} 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	0	newblock = malloc((size_t) (new_size * sizeof (void *)));
151	0	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	0	memcpy(newblock,
156	0	(void ) ((char ) l->elements + l->first * sizeof (void *)),
157	0	(size_t) ((l->max_size - l->first) * sizeof (void *)));
158
159		// Append the second part of the list to the end
160	0	memcpy((void ) ((char ) newblock + (l->max_size - l->first) * sizeof (void *)),
161	0	(void *) l->elements,
162	0	(size_t) (l->first * sizeof (void *)));
163
164	0	free(l->elements);
165	0	}
166
167	11.3k	l->first = 0;
168	11.3k	l->last = l->current_size;
169	11.3k	l->max_size = new_size;
170	11.3k	l->elements = newblock;
171	11.3k	}
172
173	3.63M	l->elements[l->last] = e;
174	3.63M	l->current_size++;
175
176	3.63M	l->last++;
177	3.63M	if (l->last == l->max_size) {
178	11.8k	l->last = 0;
179	11.8k	}
180
181	3.63M	return HTP_OK;
182	3.63M	}
183
184	93.1k	htp_status_t htp_list_array_replace(htp_list_array_t l, size_t idx, void e) {
185	93.1k	if (l == NULL) return HTP_ERROR;
186
187	93.1k	if (idx + 1 > l->current_size) return HTP_DECLINED;
188
189	93.1k	l->elements[(l->first + idx) % l->max_size] = e;
190
191	93.1k	return HTP_OK;
192	93.1k	}
193
194	7.95M	size_t htp_list_array_size(const htp_list_array_t *l) {
195	7.95M	if (l == NULL) return HTP_ERROR;
196
197	7.95M	return l->current_size;
198	7.95M	}
199
200	0	void htp_list_array_shift(htp_list_array_t l) {
201	0	if (l == NULL) return NULL;
202
203	0	void *r = NULL;
204
205	0	if (l->current_size == 0) {
206	0	return NULL;
207	0	}
208
209	0	r = l->elements[l->first];
210	0	l->first++;
211	0	if (l->first == l->max_size) {
212	0	l->first = 0;
213	0	}
214
215	0	l->current_size--;
216
217	0	return r;
218	0	}
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