1 /* ptrv.c - A vector of address pointers
2 *
3 * Copyright (C) 2004, 2005 Oskar Liljeblad
4 *
5 * This program is free software; you can redistribute it and/or modify
6 * it under the terms of the GNU General Public License as published by
7 * the Free Software Foundation; either version 2 of the License, or
8 * (at your option) any later version.
9 *
10 * This program is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU Library General Public License for more details.
14 *
15 * You should have received a copy of the GNU General Public License along
16 * with this program; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
18 */
19
20 #include <config.h>
21 #include <string.h>
22 #include <sys/param.h>
23 #include <stdlib.h>
24 #include "xalloc.h"
25 #include "ptrv.h"
26
27 /* Create a new ptrv with specified size.
28 */
29 static PtrV *
ptrv_new_with_size(uint32_t initial_size)30 ptrv_new_with_size(uint32_t initial_size)
31 {
32 PtrV *pv;
33
34 pv = xmalloc(sizeof(PtrV));
35 pv->cur = 0;
36 pv->max = MAX(1, initial_size);
37 pv->buf = xmalloc(pv->max * sizeof(void *));
38
39 return pv;
40 }
41
42 /* Create a new ptrv that initially is as small as possible.
43 */
44 PtrV *
ptrv_new(void)45 ptrv_new(void)
46 {
47 return ptrv_new_with_size(1);
48 }
49
50 /* Free the ptrv.
51 */
52 void
ptrv_free(PtrV * pv)53 ptrv_free(PtrV *pv)
54 {
55 if (pv != NULL) {
56 free(pv->buf);
57 free(pv);
58 }
59 }
60
61 /* Append a pointer to the ptrv.
62 */
63 void
ptrv_append(PtrV * pv,void * value)64 ptrv_append(PtrV *pv, void *value)
65 {
66 if (pv->cur >= pv->max) {
67 pv->max = MAX(1, pv->max*2);
68 pv->buf = xrealloc(pv->buf, pv->max * sizeof(void *));
69 }
70 pv->buf[pv->cur] = value;
71 pv->cur++;
72 }
73
74 /* Prepend a few values to the ptrv.
75 */
76 void
ptrv_prepend_n(PtrV * pv,uint32_t count,void * value)77 ptrv_prepend_n(PtrV *pv, uint32_t count, void *value)
78 {
79 uint32_t c;
80
81 if (pv->cur+count > pv->max) {
82 pv->max = MAX(pv->cur+count, pv->max*2);
83 pv->buf = xrealloc(pv->buf, pv->max*sizeof(void *));
84 }
85 memmove(pv->buf+count, pv->buf, pv->cur*sizeof(void *));
86
87 for (c = 0; c < count; c++)
88 pv->buf[c] = value;
89 pv->cur += count;
90 }
91
92 /* Remove a range of pointers from the ptrv.
93 */
94 void
ptrv_remove_range(PtrV * pv,uint32_t start,uint32_t end)95 ptrv_remove_range(PtrV *pv, uint32_t start, uint32_t end)
96 {
97 if (end < pv->cur)
98 memmove(pv->buf+start, pv->buf+end, (pv->cur - end) * sizeof(void *));
99
100 pv->cur -= end - start;
101 }
102
103 /* Remove the pointer from the ptrv.
104 */
105 void *
ptrv_remove(PtrV * pv,uint32_t pos)106 ptrv_remove(PtrV *pv, uint32_t pos)
107 {
108 void *value = NULL;
109 if (pos >= 0 && pos < pv->cur) {
110 value = pv->buf[pos];
111 pv->cur--;
112 if ((pv->cur-pos) > 0)
113 memmove(pv->buf+pos, pv->buf+pos+1, (pv->cur-pos) * sizeof(void *));
114 }
115
116 return value;
117 }
118
119 /* Call some function (callback) for each pointer in the ptrv.
120 */
121 void
ptrv_foreach(PtrV * pv,PtrVForeachCallback callback)122 ptrv_foreach(PtrV *pv, PtrVForeachCallback callback)
123 {
124 unsigned c;
125
126 for (c = 0; c < pv->cur; c++)
127 callback(pv->buf[c]);
128 }
129
130 /* Remove all pointers from the ptrv.
131 */
132 void
ptrv_clear(PtrV * pv)133 ptrv_clear(PtrV *pv)
134 {
135 pv->cur = 0;
136 }
137
138 int32_t
ptrv_find(PtrV * pv,void * element,comparison_fn_t comparator)139 ptrv_find(PtrV *pv, void *element, comparison_fn_t comparator)
140 {
141 uint32_t c;
142
143 for (c = 0; c < pv->cur; c++) {
144 if (comparator(element, pv->buf[c]) == 0)
145 return c;
146 }
147
148 return -1;
149 }
150
151 void
ptrv_sort(PtrV * pv,comparison_fn_t comparator)152 ptrv_sort(PtrV *pv, comparison_fn_t comparator)
153 {
154 qsort(pv->buf, pv->cur, sizeof(void *), comparator);
155 }
156
157 void
ptrv_insort(PtrV * pv,void * element,comparison_fn_t comparator)158 ptrv_insort(PtrV *pv, void *element, comparison_fn_t comparator)
159 {
160 uint32_t c;
161
162 /* XXX: this is slow but stable... */
163 for (c = 0; c < pv->cur; c++) {
164 int cmp;
165
166 cmp = comparator(element, pv->buf[c]);
167 if (cmp <= 0) {
168 if (pv->cur >= pv->max) {
169 pv->max = MAX(1, pv->max * 2);
170 pv->buf = xrealloc(pv->buf, pv->max * sizeof(void *));
171 }
172 memmove(pv->buf+c+1, pv->buf+c, sizeof(void *)*(pv->cur-c));
173 pv->buf[c] = element;
174 pv->cur++;
175 return;
176 }
177 }
178
179 ptrv_append(pv, element);
180 }
181