]>
Commit | Line | Data |
---|---|---|
718e3744 | 1 | /* Generic vector interface routine |
2 | * Copyright (C) 1997 Kunihiro Ishiguro | |
3 | * | |
4 | * This file is part of GNU Zebra. | |
5 | * | |
6 | * GNU Zebra is free software; you can redistribute it and/or modify it | |
7 | * under the terms of the GNU General Public License as published by the | |
8 | * Free Software Foundation; either version 2, or (at your option) any | |
9 | * later version. | |
10 | * | |
11 | * GNU Zebra is distributed in the hope that it will be useful, but | |
12 | * WITHOUT ANY WARRANTY; without even the implied warranty of | |
13 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
14 | * General Public License for more details. | |
15 | * | |
896014f4 DL |
16 | * You should have received a copy of the GNU General Public License along |
17 | * with this program; see the file COPYING; if not, write to the Free Software | |
18 | * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA | |
718e3744 | 19 | */ |
20 | ||
21 | #include <zebra.h> | |
22 | ||
23 | #include "vector.h" | |
24 | #include "memory.h" | |
25 | ||
bf8d3d6a DL |
26 | DEFINE_MTYPE_STATIC(LIB, VECTOR, "Vector"); |
27 | DEFINE_MTYPE_STATIC(LIB, VECTOR_INDEX, "Vector index"); | |
4a1ab8e4 | 28 | |
718e3744 | 29 | /* Initialize vector : allocate memory and return vector. */ |
d62a17ae | 30 | vector vector_init(unsigned int size) |
718e3744 | 31 | { |
d62a17ae | 32 | vector v = XCALLOC(MTYPE_VECTOR, sizeof(struct _vector)); |
718e3744 | 33 | |
d62a17ae | 34 | /* allocate at least one slot */ |
35 | if (size == 0) | |
36 | size = 1; | |
718e3744 | 37 | |
d62a17ae | 38 | v->alloced = size; |
39 | v->active = 0; | |
14c39974 | 40 | v->count = 0; |
d62a17ae | 41 | v->index = XCALLOC(MTYPE_VECTOR_INDEX, sizeof(void *) * size); |
42 | return v; | |
718e3744 | 43 | } |
44 | ||
d62a17ae | 45 | void vector_free(vector v) |
718e3744 | 46 | { |
d62a17ae | 47 | XFREE(MTYPE_VECTOR_INDEX, v->index); |
48 | XFREE(MTYPE_VECTOR, v); | |
718e3744 | 49 | } |
50 | ||
d62a17ae | 51 | vector vector_copy(vector v) |
718e3744 | 52 | { |
d62a17ae | 53 | unsigned int size; |
54 | vector new = XCALLOC(MTYPE_VECTOR, sizeof(struct _vector)); | |
718e3744 | 55 | |
d62a17ae | 56 | new->active = v->active; |
57 | new->alloced = v->alloced; | |
14c39974 | 58 | new->count = v->count; |
718e3744 | 59 | |
d62a17ae | 60 | size = sizeof(void *) * (v->alloced); |
61 | new->index = XCALLOC(MTYPE_VECTOR_INDEX, size); | |
62 | memcpy(new->index, v->index, size); | |
718e3744 | 63 | |
d62a17ae | 64 | return new; |
718e3744 | 65 | } |
66 | ||
67 | /* Check assigned index, and if it runs short double index pointer */ | |
d62a17ae | 68 | void vector_ensure(vector v, unsigned int num) |
718e3744 | 69 | { |
d62a17ae | 70 | if (v->alloced > num) |
71 | return; | |
72 | ||
73 | v->index = XREALLOC(MTYPE_VECTOR_INDEX, v->index, | |
74 | sizeof(void *) * (v->alloced * 2)); | |
75 | memset(&v->index[v->alloced], 0, sizeof(void *) * v->alloced); | |
76 | v->alloced *= 2; | |
77 | ||
78 | if (v->alloced <= num) | |
79 | vector_ensure(v, num); | |
718e3744 | 80 | } |
81 | ||
82 | /* This function only returns next empty slot index. It dose not mean | |
83 | the slot's index memory is assigned, please call vector_ensure() | |
84 | after calling this function. */ | |
d62a17ae | 85 | int vector_empty_slot(vector v) |
718e3744 | 86 | { |
d62a17ae | 87 | unsigned int i; |
718e3744 | 88 | |
14c39974 DL |
89 | if (v->active == v->count) |
90 | return v->active; | |
91 | ||
d62a17ae | 92 | if (v->active == 0) |
93 | return 0; | |
718e3744 | 94 | |
d62a17ae | 95 | for (i = 0; i < v->active; i++) |
96 | if (v->index[i] == 0) | |
97 | return i; | |
718e3744 | 98 | |
d62a17ae | 99 | return i; |
718e3744 | 100 | } |
101 | ||
102 | /* Set value to the smallest empty slot. */ | |
d62a17ae | 103 | int vector_set(vector v, void *val) |
718e3744 | 104 | { |
d62a17ae | 105 | unsigned int i; |
718e3744 | 106 | |
d62a17ae | 107 | i = vector_empty_slot(v); |
108 | vector_ensure(v, i); | |
718e3744 | 109 | |
14c39974 DL |
110 | if (v->index[i]) |
111 | v->count--; | |
112 | if (val) | |
113 | v->count++; | |
d62a17ae | 114 | v->index[i] = val; |
718e3744 | 115 | |
d62a17ae | 116 | if (v->active <= i) |
117 | v->active = i + 1; | |
718e3744 | 118 | |
d62a17ae | 119 | return i; |
718e3744 | 120 | } |
121 | ||
122 | /* Set value to specified index slot. */ | |
d62a17ae | 123 | int vector_set_index(vector v, unsigned int i, void *val) |
718e3744 | 124 | { |
d62a17ae | 125 | vector_ensure(v, i); |
718e3744 | 126 | |
14c39974 DL |
127 | if (v->index[i]) |
128 | v->count--; | |
129 | if (val) | |
130 | v->count++; | |
d62a17ae | 131 | v->index[i] = val; |
718e3744 | 132 | |
d62a17ae | 133 | if (v->active <= i) |
134 | v->active = i + 1; | |
718e3744 | 135 | |
d62a17ae | 136 | return i; |
718e3744 | 137 | } |
138 | ||
139 | /* Look up vector. */ | |
d62a17ae | 140 | void *vector_lookup(vector v, unsigned int i) |
718e3744 | 141 | { |
d62a17ae | 142 | if (i >= v->active) |
143 | return NULL; | |
144 | return v->index[i]; | |
718e3744 | 145 | } |
146 | ||
147 | /* Lookup vector, ensure it. */ | |
d62a17ae | 148 | void *vector_lookup_ensure(vector v, unsigned int i) |
718e3744 | 149 | { |
d62a17ae | 150 | vector_ensure(v, i); |
151 | return v->index[i]; | |
718e3744 | 152 | } |
153 | ||
154 | /* Unset value at specified index slot. */ | |
d62a17ae | 155 | void vector_unset(vector v, unsigned int i) |
718e3744 | 156 | { |
d62a17ae | 157 | if (i >= v->alloced) |
158 | return; | |
718e3744 | 159 | |
14c39974 DL |
160 | if (v->index[i]) |
161 | v->count--; | |
162 | ||
d62a17ae | 163 | v->index[i] = NULL; |
718e3744 | 164 | |
d62a17ae | 165 | if (i + 1 == v->active) { |
166 | v->active--; | |
167 | while (i && v->index[--i] == NULL && v->active--) | |
168 | ; /* Is this ugly ? */ | |
169 | } | |
718e3744 | 170 | } |
171 | ||
62bece44 QY |
172 | void vector_remove(vector v, unsigned int ix) |
173 | { | |
174 | if (ix >= v->active) | |
175 | return; | |
176 | ||
14c39974 DL |
177 | if (v->index[ix]) |
178 | v->count--; | |
179 | ||
62bece44 QY |
180 | int n = (--v->active) - ix; |
181 | ||
182 | memmove(&v->index[ix], &v->index[ix + 1], n * sizeof(void *)); | |
183 | v->index[v->active] = NULL; | |
184 | } | |
185 | ||
f428cb8a QY |
186 | void vector_compact(vector v) |
187 | { | |
188 | for (unsigned int i = 0; i < vector_active(v); ++i) { | |
189 | if (vector_slot(v, i) == NULL) { | |
190 | vector_remove(v, i); | |
191 | --i; | |
192 | } | |
193 | } | |
194 | } | |
195 | ||
d62a17ae | 196 | void vector_unset_value(vector v, void *val) |
0d9e2046 | 197 | { |
d62a17ae | 198 | size_t i; |
199 | ||
200 | for (i = 0; i < v->active; i++) | |
201 | if (v->index[i] == val) { | |
202 | v->index[i] = NULL; | |
14c39974 | 203 | v->count--; |
d62a17ae | 204 | break; |
205 | } | |
206 | ||
207 | if (i + 1 == v->active) | |
208 | do | |
209 | v->active--; | |
210 | while (i && v->index[--i] == NULL); | |
0d9e2046 DL |
211 | } |
212 | ||
fe011935 QY |
213 | void vector_to_array(vector v, void ***dest, int *argc) |
214 | { | |
215 | *dest = XCALLOC(MTYPE_TMP, sizeof(void *) * v->active); | |
216 | memcpy(*dest, v->index, sizeof(void *) * v->active); | |
217 | *argc = v->active; | |
218 | } | |
219 | ||
220 | vector array_to_vector(void **src, int argc) | |
221 | { | |
222 | vector v = vector_init(VECTOR_MIN_SIZE); | |
0a334343 | 223 | |
fe011935 QY |
224 | for (int i = 0; i < argc; i++) |
225 | vector_set_index(v, i, src[i]); | |
226 | return v; | |
227 | } |