diff options
author | Nils Durner <durner@gnunet.org> | 2009-08-08 13:48:41 +0000 |
---|---|---|
committer | Nils Durner <durner@gnunet.org> | 2009-08-08 13:48:41 +0000 |
commit | 3bb8ad6dc201a7fce2241d2b3e8acc46b0364035 (patch) | |
tree | 5ed1605f133becc2f891a7fa44ce8b8d60a61bba /src/util | |
parent | 645767a8803ddfee212fc77bc80dd35fe2be1b0a (diff) | |
download | gnunet-3bb8ad6dc201a7fce2241d2b3e8acc46b0364035.tar.gz gnunet-3bb8ad6dc201a7fce2241d2b3e8acc46b0364035.zip |
revive vector container
Diffstat (limited to 'src/util')
-rw-r--r-- | src/util/Makefile.am | 7 | ||||
-rw-r--r-- | src/util/container_vector.c | 639 | ||||
-rw-r--r-- | src/util/test_container_vector.c | 145 |
3 files changed, 791 insertions, 0 deletions
diff --git a/src/util/Makefile.am b/src/util/Makefile.am index 64178e538..089e92018 100644 --- a/src/util/Makefile.am +++ b/src/util/Makefile.am | |||
@@ -24,6 +24,7 @@ libgnunetutil_la_SOURCES = \ | |||
24 | container_bloomfilter.c \ | 24 | container_bloomfilter.c \ |
25 | container_meta_data.c \ | 25 | container_meta_data.c \ |
26 | container_multihashmap.c \ | 26 | container_multihashmap.c \ |
27 | container_vector.c \ | ||
27 | crypto_aes.c \ | 28 | crypto_aes.c \ |
28 | crypto_crc.c \ | 29 | crypto_crc.c \ |
29 | crypto_hash.c \ | 30 | crypto_hash.c \ |
@@ -79,6 +80,7 @@ check_PROGRAMS = \ | |||
79 | test_container_bloomfilter \ | 80 | test_container_bloomfilter \ |
80 | test_container_meta_data \ | 81 | test_container_meta_data \ |
81 | test_container_multihashmap \ | 82 | test_container_multihashmap \ |
83 | test_container_vector \ | ||
82 | test_crypto_aes \ | 84 | test_crypto_aes \ |
83 | test_crypto_aes_weak \ | 85 | test_crypto_aes_weak \ |
84 | test_crypto_crc \ | 86 | test_crypto_crc \ |
@@ -152,6 +154,11 @@ test_container_multihashmap_SOURCES = \ | |||
152 | test_container_multihashmap_LDADD = \ | 154 | test_container_multihashmap_LDADD = \ |
153 | $(top_builddir)/src/util/libgnunetutil.la | 155 | $(top_builddir)/src/util/libgnunetutil.la |
154 | 156 | ||
157 | test_container_vector_SOURCES = \ | ||
158 | test_container_vector.c | ||
159 | test_container_vector_LDADD = \ | ||
160 | $(top_builddir)/src/util/libgnunetutil.la | ||
161 | |||
155 | test_crypto_aes_SOURCES = \ | 162 | test_crypto_aes_SOURCES = \ |
156 | test_crypto_aes.c | 163 | test_crypto_aes.c |
157 | test_crypto_aes_LDADD = \ | 164 | test_crypto_aes_LDADD = \ |
diff --git a/src/util/container_vector.c b/src/util/container_vector.c new file mode 100644 index 000000000..d9e4fab47 --- /dev/null +++ b/src/util/container_vector.c | |||
@@ -0,0 +1,639 @@ | |||
1 | /* | ||
2 | This file is part of GNUnet | ||
3 | |||
4 | GNUnet is free software; you can redistribute it and/or modify | ||
5 | it under the terms of the GNU General Public License as published | ||
6 | by the Free Software Foundation; either version 2, or (at your | ||
7 | option) any later version. | ||
8 | |||
9 | GNUnet is distributed in the hope that it will be useful, but | ||
10 | WITHOUT ANY WARRANTY; without even the implied warranty of | ||
11 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | ||
12 | General Public License for more details. | ||
13 | |||
14 | You should have received a copy of the GNU General Public License | ||
15 | along with GNUnet; see the file COPYING. If not, write to the | ||
16 | Free Software Foundation, Inc., 59 Temple Place - Suite 330, | ||
17 | Boston, MA 02111-1307, USA. | ||
18 | */ | ||
19 | |||
20 | /** | ||
21 | * @file util/container_vector.c | ||
22 | * @brief Implementation of a dynamic array | ||
23 | * @author Antti Salonen, Christian Grothoff | ||
24 | * @version vector.c,v 1.3 2004/05/02 20:22:52 aksalone Exp | ||
25 | * | ||
26 | * An implementation of a dynamic array of objects. Like an array, the | ||
27 | * vector's elements are indexed, but it is also possible to | ||
28 | * dynamically resize the vector by inserting and removing elements at | ||
29 | * any location. The vector is implemented as a double-linked list of | ||
30 | * arrays, each with a static maximum length. When one array fills up, | ||
31 | * it's splitted into two half-full arrays, and so forth. With | ||
32 | * functions {insert,get,remove}_last the vector can also be used as a | ||
33 | * fairly efficient stack. The functions | ||
34 | * get_{at,first,last,next,previous} allow traversing the vector in an | ||
35 | * efficient manner, each function call taking more or less constant | ||
36 | * time. Vector_get_next and Vector_get_first may only be called after | ||
37 | * a call to one of vector_get_{first,last,at}, which set the vector's | ||
38 | * iterator. All functions that modify the vector's contents unset the | ||
39 | * iterator. | ||
40 | */ | ||
41 | |||
42 | #include "platform.h" | ||
43 | #include "gnunet_common.h" | ||
44 | |||
45 | typedef struct GNUNET_CONTAINER_Vector { | ||
46 | unsigned int VECTOR_SEGMENT_SIZE; | ||
47 | struct vector_segment_t * segmentsHead; | ||
48 | struct vector_segment_t * segmentsTail; | ||
49 | struct vector_segment_t * iteratorSegment; | ||
50 | unsigned int iteratorIndex; | ||
51 | size_t size; | ||
52 | } GNUNET_CONTAINER_Vector; | ||
53 | |||
54 | |||
55 | typedef struct vector_segment_t { | ||
56 | void ** data; /* always of size VECTOR_SEGMENT_SIZE */ | ||
57 | struct vector_segment_t *next; | ||
58 | struct vector_segment_t *previous; | ||
59 | size_t size; | ||
60 | } VectorSegment; | ||
61 | |||
62 | /** | ||
63 | * A debug function that traverses the linked list and prints the | ||
64 | * sizes of the segments. This currently isn't used. | ||
65 | */ | ||
66 | void GNUNET_CONTAINER_vector_dump(struct GNUNET_CONTAINER_Vector *v) { | ||
67 | VectorSegment *vs; | ||
68 | int n; | ||
69 | unsigned int sum = 0; | ||
70 | |||
71 | for (vs = v->segmentsHead; vs; vs = vs->next) { | ||
72 | fprintf(stderr, | ||
73 | "Segment-size: %3llu / %llu [%llu...%llu]: ", | ||
74 | (unsigned long long) vs->size, | ||
75 | (unsigned long long) v->VECTOR_SEGMENT_SIZE, | ||
76 | (unsigned long long) sum, | ||
77 | (unsigned long long) (sum + vs->size - 1)); | ||
78 | for (n=0;n<vs->size;n++) { | ||
79 | fprintf(stderr, | ||
80 | "%p, ", | ||
81 | vs->data[n]); | ||
82 | } | ||
83 | fprintf(stderr, "\n"); | ||
84 | sum += vs->size; | ||
85 | } | ||
86 | fprintf(stderr, | ||
87 | "Vector size: %u\n", | ||
88 | sum); | ||
89 | } | ||
90 | |||
91 | /** | ||
92 | * Remove and return the element at given index in the segment's array. The | ||
93 | * trailing pointers in the array, if any, are moved backwards to fill the gap. | ||
94 | */ | ||
95 | static void *vectorSegmentRemoveAtIndex(VectorSegment *vs, | ||
96 | int index) { | ||
97 | void *rvalue = vs->data[index]; | ||
98 | |||
99 | while (index < vs->size) { | ||
100 | vs->data[index] = vs->data[index + 1]; | ||
101 | index++; | ||
102 | } | ||
103 | return rvalue; | ||
104 | } | ||
105 | |||
106 | |||
107 | /** | ||
108 | * Split the full segment vs into two half-full segments. | ||
109 | */ | ||
110 | static void vectorSegmentSplit(struct GNUNET_CONTAINER_Vector *v, | ||
111 | VectorSegment *vs) { | ||
112 | VectorSegment *oldNext; | ||
113 | int moveCount; | ||
114 | |||
115 | oldNext = vs->next; | ||
116 | vs->next = GNUNET_malloc(sizeof(VectorSegment)); | ||
117 | vs->next->data = GNUNET_malloc(v->VECTOR_SEGMENT_SIZE * sizeof(void*)); | ||
118 | vs->next->previous = vs; | ||
119 | vs->next->next = oldNext; | ||
120 | if (NULL != oldNext) | ||
121 | oldNext->previous = vs->next; | ||
122 | else | ||
123 | v->segmentsTail = vs->next; | ||
124 | moveCount = vs->size / 2; | ||
125 | memcpy(vs->next->data, | ||
126 | vs->data + (vs->size - moveCount), | ||
127 | moveCount * sizeof (void *)); | ||
128 | vs->next->size = moveCount; | ||
129 | vs->size -= moveCount; | ||
130 | } | ||
131 | |||
132 | /** | ||
133 | * Joins the given segment with the following segment. The first segment _must_ | ||
134 | * be empty enough to store the data of both segments. | ||
135 | */ | ||
136 | static void vectorSegmentJoin(struct GNUNET_CONTAINER_Vector *v, | ||
137 | VectorSegment *vs) { | ||
138 | VectorSegment *oldNext = vs->next->next; | ||
139 | |||
140 | memcpy(vs->data + vs->size, | ||
141 | vs->next->data, | ||
142 | vs->next->size * sizeof (void *)); | ||
143 | vs->size += vs->next->size; | ||
144 | GNUNET_free(vs->next->data); | ||
145 | GNUNET_free(vs->next); | ||
146 | vs->next = oldNext; | ||
147 | if (oldNext != NULL) | ||
148 | vs->next->previous = vs; | ||
149 | else | ||
150 | v->segmentsTail = vs; | ||
151 | } | ||
152 | |||
153 | /** | ||
154 | * Free an empty segment, _unless_ it is the only segment. | ||
155 | */ | ||
156 | static void vectorSegmentRemove(struct GNUNET_CONTAINER_Vector *v, | ||
157 | VectorSegment *vs) { | ||
158 | if ( (vs->previous == NULL) && | ||
159 | (vs->next == NULL) ) | ||
160 | return; | ||
161 | if (vs->previous != NULL) | ||
162 | vs->previous->next = vs->next; | ||
163 | else | ||
164 | v->segmentsHead = vs->next; | ||
165 | if (vs->next != NULL) | ||
166 | vs->next->previous = vs->previous; | ||
167 | else | ||
168 | v->segmentsTail = vs->previous; | ||
169 | GNUNET_free(vs->data); | ||
170 | GNUNET_free(vs); | ||
171 | } | ||
172 | |||
173 | |||
174 | /** | ||
175 | * Search for given index in the vector v. When the index is found, its | ||
176 | * segment and relative index are written to parameters vs and segment_index. | ||
177 | * If possible, an unused index at the end of a segment is returned, as this | ||
178 | * is also a requirement for adding data in an empty vector. | ||
179 | */ | ||
180 | static int vectorFindNewIndex(struct GNUNET_CONTAINER_Vector * v, | ||
181 | unsigned int index, | ||
182 | VectorSegment **vs) { | ||
183 | VectorSegment *segment; | ||
184 | int segmentStartIndex; | ||
185 | |||
186 | if (index > v->size) { | ||
187 | *vs = NULL; | ||
188 | return -1; | ||
189 | } | ||
190 | if (index <= v->size / 2) { /* empty vector included */ | ||
191 | segment = v->segmentsHead; | ||
192 | segmentStartIndex = 0; | ||
193 | while (index > segmentStartIndex + segment->size) { | ||
194 | segmentStartIndex += segment->size; | ||
195 | segment = segment->next; | ||
196 | } | ||
197 | } else { /* reverse */ | ||
198 | segment = v->segmentsTail; | ||
199 | segmentStartIndex = v->size - segment->size; | ||
200 | while (index <= segmentStartIndex) { | ||
201 | segment = segment->previous; | ||
202 | segmentStartIndex -= segment->size; | ||
203 | } | ||
204 | } | ||
205 | *vs = segment; | ||
206 | return index - segmentStartIndex; | ||
207 | } | ||
208 | |||
209 | |||
210 | /** | ||
211 | * Find the segment and segmentIndex of the element | ||
212 | * with the given index. | ||
213 | */ | ||
214 | static int vectorFindIndex(struct GNUNET_CONTAINER_Vector *v, | ||
215 | unsigned int index, | ||
216 | VectorSegment **vs) { | ||
217 | VectorSegment *segment; | ||
218 | int segmentStartIndex; | ||
219 | |||
220 | if (index >= v->size) { | ||
221 | *vs = NULL; | ||
222 | return -1; | ||
223 | } | ||
224 | if (index < v->size / 2) { | ||
225 | segment = v->segmentsHead; | ||
226 | segmentStartIndex = 0; | ||
227 | while (index >= segmentStartIndex + segment->size) { | ||
228 | segmentStartIndex += segment->size; | ||
229 | segment = segment->next; | ||
230 | } | ||
231 | } else { | ||
232 | segment = v->segmentsTail; | ||
233 | segmentStartIndex = v->size - segment->size; | ||
234 | while (index < segmentStartIndex) { | ||
235 | segment = segment->previous; | ||
236 | segmentStartIndex -= segment->size; | ||
237 | } | ||
238 | } | ||
239 | *vs = segment; | ||
240 | return index - segmentStartIndex; | ||
241 | } | ||
242 | |||
243 | |||
244 | /* | ||
245 | * Traverse the vector looking for a given object. When found, set the pointer | ||
246 | * pointed to by vs to point to the object's segment and the integer pointed | ||
247 | * to by segmentIndex to the object's index in the segment. If the object is | ||
248 | * not found, *vs is set to NULL. | ||
249 | */ | ||
250 | static void vectorFindObject(struct GNUNET_CONTAINER_Vector *v, | ||
251 | void *object, | ||
252 | VectorSegment **vs, | ||
253 | int *segmentIndex) { | ||
254 | VectorSegment *segment; | ||
255 | int i; | ||
256 | |||
257 | segment = v->segmentsHead; | ||
258 | while (NULL != segment) { | ||
259 | for (i=0;i<segment->size;i++) { | ||
260 | if (segment->data[i] == object) { | ||
261 | *vs = segment; | ||
262 | *segmentIndex = i; | ||
263 | return; | ||
264 | } | ||
265 | } | ||
266 | segment = segment->next; | ||
267 | } | ||
268 | *vs = NULL; | ||
269 | } | ||
270 | |||
271 | |||
272 | /** | ||
273 | * Allocate a new vector structure with a single empty data segment. | ||
274 | */ | ||
275 | struct GNUNET_CONTAINER_Vector * GNUNET_CONTAINER_vector_new(unsigned int vss) { | ||
276 | struct GNUNET_CONTAINER_Vector *rvalue; | ||
277 | |||
278 | if (vss < 2) | ||
279 | return NULL; /* invalid! */ | ||
280 | rvalue = GNUNET_malloc(sizeof (GNUNET_CONTAINER_Vector)); | ||
281 | rvalue->VECTOR_SEGMENT_SIZE = vss; | ||
282 | rvalue->size = 0; | ||
283 | rvalue->segmentsHead = GNUNET_malloc(sizeof(VectorSegment)); | ||
284 | rvalue->segmentsHead->data = GNUNET_malloc(sizeof(void*)*vss); | ||
285 | rvalue->segmentsTail = rvalue->segmentsHead; | ||
286 | rvalue->segmentsHead->next = NULL; | ||
287 | rvalue->segmentsHead->previous = NULL; | ||
288 | rvalue->segmentsHead->size = 0; | ||
289 | rvalue->iteratorSegment = NULL; | ||
290 | rvalue->iteratorIndex = 0; | ||
291 | return rvalue; | ||
292 | } | ||
293 | |||
294 | /** | ||
295 | * Free vector structure including its data segments, but _not_ including the | ||
296 | * stored void pointers. It is the user's responsibility to empty the vector | ||
297 | * when necessary to avoid memory leakage. | ||
298 | */ | ||
299 | void GNUNET_CONTAINER_vector_free(struct GNUNET_CONTAINER_Vector *v) { | ||
300 | VectorSegment * vs; | ||
301 | VectorSegment * vsNext; | ||
302 | |||
303 | vs = v->segmentsHead; | ||
304 | while (vs != NULL) { | ||
305 | vsNext = vs->next; | ||
306 | GNUNET_free(vs->data); | ||
307 | GNUNET_free(vs); | ||
308 | vs = vsNext; | ||
309 | } | ||
310 | GNUNET_free(v); | ||
311 | } | ||
312 | |||
313 | /** | ||
314 | * Return the size of the vector. | ||
315 | */ | ||
316 | size_t GNUNET_CONTAINER_vector_size(struct GNUNET_CONTAINER_Vector *v) { | ||
317 | return v->size; | ||
318 | } | ||
319 | |||
320 | /** | ||
321 | * Insert a new element in the vector at given index. The return value is | ||
322 | * GNUNET_OK on success, GNUNET_SYSERR if the index is out of bounds. | ||
323 | */ | ||
324 | int GNUNET_CONTAINER_vector_insert_at(struct GNUNET_CONTAINER_Vector *v, | ||
325 | void *object, | ||
326 | unsigned int index) { | ||
327 | VectorSegment *segment; | ||
328 | int segmentIndex; | ||
329 | int i; | ||
330 | |||
331 | if (index > v->size) | ||
332 | return GNUNET_SYSERR; | ||
333 | v->iteratorSegment = NULL; | ||
334 | segmentIndex = vectorFindNewIndex(v, index, &segment); | ||
335 | if (segmentIndex == -1) | ||
336 | return GNUNET_SYSERR; | ||
337 | for (i = segment->size; i > segmentIndex; i--) | ||
338 | segment->data[i] = segment->data[i - 1]; | ||
339 | segment->data[segmentIndex] = object; | ||
340 | v->size++; | ||
341 | segment->size++; | ||
342 | if (segment->size == v->VECTOR_SEGMENT_SIZE) | ||
343 | vectorSegmentSplit(v, segment); | ||
344 | return GNUNET_OK; | ||
345 | } | ||
346 | |||
347 | /** | ||
348 | * Insert a new element at the end of the vector. | ||
349 | */ | ||
350 | void GNUNET_CONTAINER_vector_insert_last(struct GNUNET_CONTAINER_Vector *v, void *object) { | ||
351 | v->iteratorSegment = NULL; | ||
352 | v->segmentsTail->data[v->segmentsTail->size++] = object; | ||
353 | if (v->segmentsTail->size == v->VECTOR_SEGMENT_SIZE) | ||
354 | vectorSegmentSplit(v, v->segmentsTail); | ||
355 | v->size++; | ||
356 | } | ||
357 | |||
358 | /** | ||
359 | * Return the element at given index in the vector or NULL if the index is out | ||
360 | * of bounds. The iterator is set to point to the returned element. | ||
361 | */ | ||
362 | void * GNUNET_CONTAINER_vector_get_at(struct GNUNET_CONTAINER_Vector *v, | ||
363 | unsigned int index) { | ||
364 | int ret; | ||
365 | if ( (index < 0) || (index >= v->size) ) | ||
366 | return NULL; | ||
367 | ret = vectorFindIndex(v, | ||
368 | index, | ||
369 | &v->iteratorSegment); | ||
370 | if (ret == -1) | ||
371 | return NULL; | ||
372 | v->iteratorIndex = ret; | ||
373 | return v->iteratorSegment->data[ret]; | ||
374 | } | ||
375 | |||
376 | /** | ||
377 | * Return the first element in the vector, whose index is 0, or NULL if the | ||
378 | * vector is empty. The iterator of the vector is set to point to the first | ||
379 | * element. | ||
380 | */ | ||
381 | void * GNUNET_CONTAINER_vector_get_first(struct GNUNET_CONTAINER_Vector *v) { | ||
382 | if (v->size == 0) | ||
383 | return NULL; | ||
384 | v->iteratorSegment = v->segmentsHead; | ||
385 | v->iteratorIndex = 0; | ||
386 | return v->iteratorSegment->data[0]; | ||
387 | } | ||
388 | |||
389 | /** | ||
390 | * Return the last element in the vector or NULL if the vector is | ||
391 | * empty. The iterator of the vector is set to the last element. | ||
392 | */ | ||
393 | void * GNUNET_CONTAINER_vector_get_last(struct GNUNET_CONTAINER_Vector *v) { | ||
394 | if (v->size == 0) | ||
395 | return NULL; | ||
396 | v->iteratorSegment = v->segmentsTail; | ||
397 | v->iteratorIndex = v->segmentsTail->size-1; | ||
398 | return v->segmentsTail->data[v->iteratorIndex]; | ||
399 | } | ||
400 | |||
401 | /** | ||
402 | * Return the next element in the vector, as called after vector_get_at() or | ||
403 | * vector_get_first(). The return value is NULL if there are no more elements | ||
404 | * in the vector or if the iterator has not been set. | ||
405 | */ | ||
406 | void * GNUNET_CONTAINER_vector_get_next(struct GNUNET_CONTAINER_Vector *v) { | ||
407 | if (v->iteratorSegment == NULL) | ||
408 | return NULL; | ||
409 | if (++v->iteratorIndex >= v->iteratorSegment->size) { | ||
410 | if (v->iteratorSegment == v->segmentsTail) { | ||
411 | v->iteratorSegment = NULL; | ||
412 | return NULL; | ||
413 | } else { | ||
414 | v->iteratorSegment = v->iteratorSegment->next; | ||
415 | v->iteratorIndex = 0; | ||
416 | } | ||
417 | } | ||
418 | return v->iteratorSegment->data[v->iteratorIndex]; | ||
419 | } | ||
420 | |||
421 | /** | ||
422 | * Return the previous element in the vector, as called after vector_get_at() | ||
423 | * or vector_get_last(). The return value is NULL if there are no more | ||
424 | * elements in the vector or if the iterator has not been set. | ||
425 | */ | ||
426 | void * GNUNET_CONTAINER_vector_get_previous(struct GNUNET_CONTAINER_Vector * v) { | ||
427 | if (v->iteratorSegment == NULL) | ||
428 | return NULL; | ||
429 | if (--v->iteratorIndex == -1) { | ||
430 | if (v->iteratorSegment == v->segmentsHead) { | ||
431 | v->iteratorSegment = 0; | ||
432 | return NULL; | ||
433 | } else { | ||
434 | v->iteratorSegment = v->iteratorSegment->previous; | ||
435 | v->iteratorIndex = v->iteratorSegment->size - 1; | ||
436 | } | ||
437 | } | ||
438 | return v->iteratorSegment->data[v->iteratorIndex]; | ||
439 | } | ||
440 | |||
441 | /** | ||
442 | * Delete and return the element at given index. NULL is returned if index is | ||
443 | * out of bounds. | ||
444 | */ | ||
445 | void * GNUNET_CONTAINER_vector_remove_at(struct GNUNET_CONTAINER_Vector *v, | ||
446 | unsigned int index) { | ||
447 | VectorSegment * segment; | ||
448 | int segmentIndex; | ||
449 | void *rvalue; | ||
450 | |||
451 | if (index >= v->size) | ||
452 | return NULL; | ||
453 | v->iteratorSegment = NULL; | ||
454 | segmentIndex = vectorFindIndex(v, index, &segment); | ||
455 | if (segmentIndex == -1) | ||
456 | return NULL; | ||
457 | rvalue = vectorSegmentRemoveAtIndex(segment, | ||
458 | segmentIndex); | ||
459 | /* If the segment ends empty remove it, otherwise | ||
460 | try to join it with its neighbors. */ | ||
461 | if (--segment->size == 0) | ||
462 | vectorSegmentRemove(v, segment); | ||
463 | else if (segment->next && | ||
464 | segment->size + segment->next->size < v->VECTOR_SEGMENT_SIZE) | ||
465 | vectorSegmentJoin(v, segment); | ||
466 | else if (segment->previous && | ||
467 | segment->size + segment->previous->size < v->VECTOR_SEGMENT_SIZE) | ||
468 | vectorSegmentJoin(v, segment->previous); | ||
469 | v->size--; | ||
470 | return rvalue; | ||
471 | } | ||
472 | |||
473 | /** | ||
474 | * Delete and return the last element in the vector, or NULL if the vector | ||
475 | * is empty. | ||
476 | */ | ||
477 | void *GNUNET_CONTAINER_vector_remove_last (struct GNUNET_CONTAINER_Vector *v) { | ||
478 | void *rvalue; | ||
479 | |||
480 | if (v->size == 0) | ||
481 | return NULL; | ||
482 | v->iteratorSegment = NULL; | ||
483 | rvalue = v->segmentsTail->data[v->segmentsTail->size - 1]; | ||
484 | /* If the segment ends empty remove it, otherwise join it if necessary. */ | ||
485 | if (--v->segmentsTail->size == 0) | ||
486 | vectorSegmentRemove(v, v->segmentsTail); | ||
487 | else if ( (v->segmentsTail->previous != NULL) && | ||
488 | (v->segmentsTail->size + v->segmentsTail->previous->size | ||
489 | < v->VECTOR_SEGMENT_SIZE) ) | ||
490 | vectorSegmentJoin (v, v->segmentsTail->previous); | ||
491 | v->size--; | ||
492 | return rvalue; | ||
493 | } | ||
494 | |||
495 | /** | ||
496 | * Delete and return given object from the vector, or return NULL if the object | ||
497 | * is not found. | ||
498 | */ | ||
499 | void * GNUNET_CONTAINER_vector_remove_object(struct GNUNET_CONTAINER_Vector *v, void *object) { | ||
500 | VectorSegment *segment; | ||
501 | int segmentIndex; | ||
502 | void * rvalue; | ||
503 | |||
504 | v->iteratorSegment = NULL; | ||
505 | vectorFindObject(v, object, &segment, &segmentIndex); | ||
506 | if (segment == NULL) | ||
507 | return NULL; | ||
508 | rvalue = vectorSegmentRemoveAtIndex(segment, segmentIndex); | ||
509 | /* If the segment ends empty remove it, otherwise join it if necessary. */ | ||
510 | if (--segment->size == 0) | ||
511 | vectorSegmentRemove (v, segment); | ||
512 | else if ( (segment->next != NULL) && | ||
513 | (segment->size + segment->next->size < v->VECTOR_SEGMENT_SIZE) ) | ||
514 | vectorSegmentJoin (v, segment); | ||
515 | else if ( (segment->previous != NULL) && | ||
516 | (segment->size + segment->previous->size < v->VECTOR_SEGMENT_SIZE) ) | ||
517 | vectorSegmentJoin (v, segment->previous); | ||
518 | v->size--; | ||
519 | return rvalue; | ||
520 | } | ||
521 | |||
522 | /** | ||
523 | * Set the given index in the vector. The old value of the index is | ||
524 | * returned, or NULL if the index is out of bounds. | ||
525 | */ | ||
526 | void *GNUNET_CONTAINER_vector_set_at (struct GNUNET_CONTAINER_Vector *v, | ||
527 | void *object, | ||
528 | unsigned int index) { | ||
529 | VectorSegment *segment; | ||
530 | int segmentIndex; | ||
531 | void *rvalue; | ||
532 | |||
533 | if (index >= v->size) | ||
534 | return NULL; | ||
535 | v->iteratorSegment = NULL; | ||
536 | segmentIndex = vectorFindIndex(v, index, &segment); | ||
537 | if (segmentIndex == -1) | ||
538 | return NULL; | ||
539 | rvalue = segment->data[segmentIndex]; | ||
540 | segment->data[segmentIndex] = object; | ||
541 | return rvalue; | ||
542 | } | ||
543 | |||
544 | |||
545 | /** | ||
546 | * Set the index occupied by the given object to point to the new object. | ||
547 | * The old object is returned, or NULL if it's not found. | ||
548 | */ | ||
549 | void *GNUNET_CONTAINER_vector_set_object(struct GNUNET_CONTAINER_Vector *v, | ||
550 | void *object, | ||
551 | void *oldObject) { | ||
552 | VectorSegment *segment; | ||
553 | int segmentIndex; | ||
554 | void *rvalue; | ||
555 | |||
556 | v->iteratorSegment = NULL; | ||
557 | vectorFindObject (v, oldObject, &segment, &segmentIndex); | ||
558 | if (segment == NULL) | ||
559 | return NULL; | ||
560 | rvalue = segment->data[segmentIndex]; | ||
561 | segment->data[segmentIndex] = object; | ||
562 | return rvalue; | ||
563 | } | ||
564 | |||
565 | |||
566 | /** | ||
567 | * Swaps the contents of index1 and index2. Return value is GNUNET_OK | ||
568 | * on success, GNUNET_SYSERR if either index is out of bounds. | ||
569 | */ | ||
570 | int GNUNET_CONTAINER_vector_swap(struct GNUNET_CONTAINER_Vector *v, | ||
571 | unsigned int index1, | ||
572 | unsigned int index2) { | ||
573 | VectorSegment * segment1; | ||
574 | VectorSegment * segment2; | ||
575 | int segmentIndex1; | ||
576 | int segmentIndex2; | ||
577 | void *temp; | ||
578 | |||
579 | if ( (index1 >= v->size) || | ||
580 | (index2 >= v->size) ) | ||
581 | return GNUNET_SYSERR; | ||
582 | v->iteratorSegment= NULL; | ||
583 | segmentIndex1 = vectorFindIndex(v, index1, &segment1); | ||
584 | segmentIndex2 = vectorFindIndex(v, index2, &segment2); | ||
585 | if( (segmentIndex1 == -1) || | ||
586 | (segmentIndex2 == -1) ) | ||
587 | return GNUNET_SYSERR; | ||
588 | temp = segment1->data[segmentIndex1]; | ||
589 | segment1->data[segmentIndex1] = segment2->data[segmentIndex2]; | ||
590 | segment2->data[segmentIndex2] = temp; | ||
591 | return GNUNET_OK; | ||
592 | } | ||
593 | |||
594 | /** | ||
595 | * Return the index of given element or -1 if the element is not found. | ||
596 | */ | ||
597 | unsigned int GNUNET_CONTAINER_vector_index_of(struct GNUNET_CONTAINER_Vector *v, | ||
598 | void *object) { | ||
599 | VectorSegment * segment; | ||
600 | unsigned int i; | ||
601 | unsigned int segmentStartIndex; | ||
602 | |||
603 | segmentStartIndex = 0; | ||
604 | segment = v->segmentsHead; | ||
605 | while (NULL != segment) { | ||
606 | for (i = 0; i < segment->size; i++) | ||
607 | if (segment->data[i] == object) | ||
608 | return segmentStartIndex + i; | ||
609 | segmentStartIndex += segment->size; | ||
610 | segment = segment->next; | ||
611 | } | ||
612 | return (unsigned int) -1; | ||
613 | } | ||
614 | |||
615 | |||
616 | /* | ||
617 | * Return the data stored in the vector as a single dynamically allocated | ||
618 | * array of (void *), which must be free(3)d by the user. Use the functions | ||
619 | * get_{at,first,last,next,previous} instead, unless you really need to access | ||
620 | * everything in the vector as fast as possible. | ||
621 | */ | ||
622 | void ** GNUNET_CONTAINER_vector_elements (struct GNUNET_CONTAINER_Vector *v) { | ||
623 | void **rvalue; | ||
624 | VectorSegment *vs; | ||
625 | size_t i = 0; | ||
626 | |||
627 | rvalue = GNUNET_malloc_large(v->size * sizeof (void *)); | ||
628 | for (vs = v->segmentsHead; vs; vs = vs->next) { | ||
629 | memcpy (rvalue + i, | ||
630 | vs->data, | ||
631 | vs->size * sizeof (void *)); | ||
632 | i += vs->size; | ||
633 | } | ||
634 | return rvalue; | ||
635 | } | ||
636 | |||
637 | |||
638 | |||
639 | /* end of vector.c */ | ||
diff --git a/src/util/test_container_vector.c b/src/util/test_container_vector.c new file mode 100644 index 000000000..ddd6cdd3e --- /dev/null +++ b/src/util/test_container_vector.c | |||
@@ -0,0 +1,145 @@ | |||
1 | /* | ||
2 | This file is part of GNUnet | ||
3 | (C) 2005, 2006, 2009 Christian Grothoff (and other contributing authors) | ||
4 | |||
5 | GNUnet is free software; you can redistribute it and/or modify | ||
6 | it under the terms of the GNU General Public License as published | ||
7 | by the Free Software Foundation; either version 2, or (at your | ||
8 | option) any later version. | ||
9 | |||
10 | GNUnet is distributed in the hope that it will be useful, but | ||
11 | WITHOUT ANY WARRANTY; without even the implied warranty of | ||
12 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | ||
13 | General Public License for more details. | ||
14 | |||
15 | You should have received a copy of the GNU General Public License | ||
16 | along with GNUnet; see the file COPYING. If not, write to the | ||
17 | Free Software Foundation, Inc., 59 Temple Place - Suite 330, | ||
18 | Boston, MA 02111-1307, USA. | ||
19 | */ | ||
20 | |||
21 | /** | ||
22 | * This is a testcase for the vector, waiting to be extended. | ||
23 | */ | ||
24 | |||
25 | #include "platform.h" | ||
26 | #include "gnunet_container_lib.h" | ||
27 | |||
28 | #define DUMP(v) fprintf(stderr, "At %d: \n", __LINE__); GNUNET_CONTAINER_vector_dump(v); | ||
29 | |||
30 | static int test(int size) { | ||
31 | struct GNUNET_CONTAINER_Vector * v; | ||
32 | |||
33 | v = GNUNET_CONTAINER_vector_new(size); | ||
34 | if (0 != GNUNET_CONTAINER_vector_size(v)) | ||
35 | { DUMP(v); return 1; } | ||
36 | if (GNUNET_OK != GNUNET_CONTAINER_vector_insert_at(v, "first", 0)) | ||
37 | { DUMP(v); return 1; } | ||
38 | if (GNUNET_OK == GNUNET_CONTAINER_vector_insert_at(v, "not", 2)) | ||
39 | { DUMP(v); return 1; } | ||
40 | if (GNUNET_OK != GNUNET_CONTAINER_vector_insert_at(v, "zero", 0)) | ||
41 | { DUMP(v); return 1; } | ||
42 | if (GNUNET_OK != GNUNET_CONTAINER_vector_insert_at(v, "second", 2)) | ||
43 | { DUMP(v); return 1; } | ||
44 | GNUNET_CONTAINER_vector_insert_last(v, "third"); | ||
45 | if (4 != GNUNET_CONTAINER_vector_size(v)) | ||
46 | { DUMP(v); return 1; } | ||
47 | if (0 != strcmp(GNUNET_CONTAINER_vector_get_at(v, 1), "first")) | ||
48 | { DUMP(v); return 1; } | ||
49 | if (0 != strcmp(GNUNET_CONTAINER_vector_get_at(v, 3), "third")) | ||
50 | { DUMP(v); return 1; } | ||
51 | if (0 != strcmp(GNUNET_CONTAINER_vector_get_at(v, 0), "zero")) | ||
52 | { DUMP(v); return 1; } | ||
53 | if (0 != strcmp(GNUNET_CONTAINER_vector_get_first(v), "zero")) | ||
54 | { DUMP(v); return 1; } | ||
55 | if (0 != strcmp(GNUNET_CONTAINER_vector_get_last(v), "third")) | ||
56 | { DUMP(v); return 1; } | ||
57 | if (0 != strcmp(GNUNET_CONTAINER_vector_remove_at(v, 1), "first")) | ||
58 | { DUMP(v); return 1; } | ||
59 | if (0 != strcmp(GNUNET_CONTAINER_vector_get_at(v, 1), "second")) | ||
60 | { DUMP(v); return 1; } | ||
61 | if (NULL != GNUNET_CONTAINER_vector_remove_at(v, 3)) | ||
62 | { DUMP(v); return 1; } | ||
63 | if (3 != GNUNET_CONTAINER_vector_size(v)) | ||
64 | { DUMP(v); return 1; } | ||
65 | if (0 != strcmp(GNUNET_CONTAINER_vector_remove_at(v, 1), "second")) | ||
66 | { DUMP(v); return 1; } | ||
67 | if (0 != strcmp(GNUNET_CONTAINER_vector_remove_object(v, "third"), "third")) | ||
68 | { DUMP(v); return 1; } | ||
69 | if (NULL != GNUNET_CONTAINER_vector_remove_object(v, "third")) | ||
70 | { DUMP(v); return 1; } | ||
71 | if (0 != strcmp(GNUNET_CONTAINER_vector_remove_last(v), "zero")) | ||
72 | { DUMP(v); return 1; } | ||
73 | if (0 != GNUNET_CONTAINER_vector_size(v)) | ||
74 | { DUMP(v); return 1; } | ||
75 | if (NULL != GNUNET_CONTAINER_vector_remove_last(v)) | ||
76 | { DUMP(v); return 1; } | ||
77 | if (0 != GNUNET_CONTAINER_vector_size(v)) | ||
78 | { DUMP(v); return 1; } | ||
79 | GNUNET_CONTAINER_vector_free(v); | ||
80 | return 0; | ||
81 | } | ||
82 | |||
83 | static int test2(int size) { | ||
84 | long i; | ||
85 | struct GNUNET_CONTAINER_Vector * v; | ||
86 | |||
87 | v = GNUNET_CONTAINER_vector_new(size); | ||
88 | |||
89 | for (i=0;i<500;i++) | ||
90 | if (GNUNET_OK != GNUNET_CONTAINER_vector_insert_at(v, (void*)i, 0)) | ||
91 | { DUMP(v); return 1; } | ||
92 | if (500 != GNUNET_CONTAINER_vector_size(v)) | ||
93 | { DUMP(v); return 1; } | ||
94 | for (i=0;i<500;i++) | ||
95 | if (499 - i != (long) GNUNET_CONTAINER_vector_get_at(v, i)) | ||
96 | { DUMP(v); return 1; } | ||
97 | if (499 != (long) GNUNET_CONTAINER_vector_get_first(v)) | ||
98 | { DUMP(v); return 1; } | ||
99 | for (i=498;i>=0;i--) | ||
100 | if (i != (long) GNUNET_CONTAINER_vector_get_next(v)) | ||
101 | { DUMP(v); return 1; } | ||
102 | |||
103 | if (499 != (long) GNUNET_CONTAINER_vector_get_first(v)) | ||
104 | { DUMP(v); return 1; } | ||
105 | for (i=498;i>=250;i--) | ||
106 | if (i != (long) GNUNET_CONTAINER_vector_get_next(v)) | ||
107 | { DUMP(v); return 1; } | ||
108 | for (i=251;i<499;i++) | ||
109 | if (i != (long) GNUNET_CONTAINER_vector_get_previous(v)) | ||
110 | { DUMP(v); return 1; } | ||
111 | |||
112 | GNUNET_CONTAINER_vector_free(v); | ||
113 | return 0; | ||
114 | } | ||
115 | |||
116 | |||
117 | int main(int argc, | ||
118 | char * argv[]) { | ||
119 | if (NULL != GNUNET_CONTAINER_vector_new(0)) | ||
120 | { printf("At %d\n", __LINE__); return 1; } | ||
121 | if (NULL != GNUNET_CONTAINER_vector_new(1)) | ||
122 | { printf("At %d\n", __LINE__); return 1; } | ||
123 | if (test(2) != 0) | ||
124 | { printf("At %d\n", __LINE__); return 1; } | ||
125 | if (test(3) != 0) | ||
126 | { printf("At %d\n", __LINE__); return 1; } | ||
127 | if (test(4) != 0) | ||
128 | { printf("At %d\n", __LINE__); return 1; } | ||
129 | if (test(128) != 0) | ||
130 | { printf("At %d\n", __LINE__); return 1; } | ||
131 | if (test(65536) != 0) | ||
132 | { printf("At %d\n", __LINE__); return 1; } | ||
133 | if (test(2*65536) != 0) | ||
134 | { printf("At %d\n", __LINE__); return 1; } | ||
135 | |||
136 | if (test2(2) != 0) | ||
137 | { printf("At %d\n", __LINE__); return 1; } | ||
138 | if (test2(3) != 0) | ||
139 | { printf("At %d\n", __LINE__); return 1; } | ||
140 | if (test2(4) != 0) | ||
141 | { printf("At %d\n", __LINE__); return 1; } | ||
142 | if (test2(128) != 0) | ||
143 | { printf("At %d\n", __LINE__); return 1; } | ||
144 | return 0; | ||
145 | } | ||