2 This file is part of GNUnet
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.
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.
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.
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
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
43 #include "gnunet_common.h"
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;
52 } GNUNET_CONTAINER_Vector;
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;
63 * A debug function that traverses the linked list and prints the
64 * sizes of the segments. This currently isn't used.
66 void GNUNET_CONTAINER_vector_dump(struct GNUNET_CONTAINER_Vector *v) {
71 for (vs = v->segmentsHead; vs; vs = vs->next) {
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++) {
83 fprintf(stderr, "\n");
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.
95 static void *vectorSegmentRemoveAtIndex(VectorSegment *vs,
97 void *rvalue = vs->data[index];
99 while (index < vs->size) {
100 vs->data[index] = vs->data[index + 1];
108 * Split the full segment vs into two half-full segments.
110 static void vectorSegmentSplit(struct GNUNET_CONTAINER_Vector *v,
112 VectorSegment *oldNext;
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;
121 oldNext->previous = vs->next;
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;
133 * Joins the given segment with the following segment. The first segment _must_
134 * be empty enough to store the data of both segments.
136 static void vectorSegmentJoin(struct GNUNET_CONTAINER_Vector *v,
138 VectorSegment *oldNext = vs->next->next;
140 memcpy(vs->data + vs->size,
142 vs->next->size * sizeof (void *));
143 vs->size += vs->next->size;
144 GNUNET_free(vs->next->data);
145 GNUNET_free(vs->next);
148 vs->next->previous = vs;
150 v->segmentsTail = vs;
154 * Free an empty segment, _unless_ it is the only segment.
156 static void vectorSegmentRemove(struct GNUNET_CONTAINER_Vector *v,
158 if ( (vs->previous == NULL) &&
161 if (vs->previous != NULL)
162 vs->previous->next = vs->next;
164 v->segmentsHead = vs->next;
165 if (vs->next != NULL)
166 vs->next->previous = vs->previous;
168 v->segmentsTail = vs->previous;
169 GNUNET_free(vs->data);
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.
180 static int vectorFindNewIndex(struct GNUNET_CONTAINER_Vector * v,
182 VectorSegment **vs) {
183 VectorSegment *segment;
184 int segmentStartIndex;
186 if (index > v->size) {
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;
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;
206 return index - segmentStartIndex;
211 * Find the segment and segmentIndex of the element
212 * with the given index.
214 static int vectorFindIndex(struct GNUNET_CONTAINER_Vector *v,
216 VectorSegment **vs) {
217 VectorSegment *segment;
218 int segmentStartIndex;
220 if (index >= v->size) {
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;
232 segment = v->segmentsTail;
233 segmentStartIndex = v->size - segment->size;
234 while (index < segmentStartIndex) {
235 segment = segment->previous;
236 segmentStartIndex -= segment->size;
240 return index - segmentStartIndex;
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.
250 static void vectorFindObject(struct GNUNET_CONTAINER_Vector *v,
254 VectorSegment *segment;
257 segment = v->segmentsHead;
258 while (NULL != segment) {
259 for (i=0;i<segment->size;i++) {
260 if (segment->data[i] == object) {
266 segment = segment->next;
273 * Allocate a new vector structure with a single empty data segment.
275 struct GNUNET_CONTAINER_Vector * GNUNET_CONTAINER_vector_new(unsigned int vss) {
276 struct GNUNET_CONTAINER_Vector *rvalue;
279 return NULL; /* invalid! */
280 rvalue = GNUNET_malloc(sizeof (GNUNET_CONTAINER_Vector));
281 rvalue->VECTOR_SEGMENT_SIZE = vss;
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;
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.
299 void GNUNET_CONTAINER_vector_free(struct GNUNET_CONTAINER_Vector *v) {
301 VectorSegment * vsNext;
303 vs = v->segmentsHead;
306 GNUNET_free(vs->data);
314 * Return the size of the vector.
316 size_t GNUNET_CONTAINER_vector_size(struct GNUNET_CONTAINER_Vector *v) {
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.
324 int GNUNET_CONTAINER_vector_insert_at(struct GNUNET_CONTAINER_Vector *v,
326 unsigned int index) {
327 VectorSegment *segment;
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;
342 if (segment->size == v->VECTOR_SEGMENT_SIZE)
343 vectorSegmentSplit(v, segment);
348 * Insert a new element at the end of the vector.
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);
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.
362 void * GNUNET_CONTAINER_vector_get_at(struct GNUNET_CONTAINER_Vector *v,
363 unsigned int index) {
365 if ( (index < 0) || (index >= v->size) )
367 ret = vectorFindIndex(v,
369 &v->iteratorSegment);
372 v->iteratorIndex = ret;
373 return v->iteratorSegment->data[ret];
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
381 void * GNUNET_CONTAINER_vector_get_first(struct GNUNET_CONTAINER_Vector *v) {
384 v->iteratorSegment = v->segmentsHead;
385 v->iteratorIndex = 0;
386 return v->iteratorSegment->data[0];
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.
393 void * GNUNET_CONTAINER_vector_get_last(struct GNUNET_CONTAINER_Vector *v) {
396 v->iteratorSegment = v->segmentsTail;
397 v->iteratorIndex = v->segmentsTail->size-1;
398 return v->segmentsTail->data[v->iteratorIndex];
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.
406 void * GNUNET_CONTAINER_vector_get_next(struct GNUNET_CONTAINER_Vector *v) {
407 if (v->iteratorSegment == NULL)
409 if (++v->iteratorIndex >= v->iteratorSegment->size) {
410 if (v->iteratorSegment == v->segmentsTail) {
411 v->iteratorSegment = NULL;
414 v->iteratorSegment = v->iteratorSegment->next;
415 v->iteratorIndex = 0;
418 return v->iteratorSegment->data[v->iteratorIndex];
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.
426 void * GNUNET_CONTAINER_vector_get_previous(struct GNUNET_CONTAINER_Vector * v) {
427 if (v->iteratorSegment == NULL)
429 if (--v->iteratorIndex == -1) {
430 if (v->iteratorSegment == v->segmentsHead) {
431 v->iteratorSegment = 0;
434 v->iteratorSegment = v->iteratorSegment->previous;
435 v->iteratorIndex = v->iteratorSegment->size - 1;
438 return v->iteratorSegment->data[v->iteratorIndex];
442 * Delete and return the element at given index. NULL is returned if index is
445 void * GNUNET_CONTAINER_vector_remove_at(struct GNUNET_CONTAINER_Vector *v,
446 unsigned int index) {
447 VectorSegment * segment;
451 if (index >= v->size)
453 v->iteratorSegment = NULL;
454 segmentIndex = vectorFindIndex(v, index, &segment);
455 if (segmentIndex == -1)
457 rvalue = vectorSegmentRemoveAtIndex(segment,
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);
474 * Delete and return the last element in the vector, or NULL if the vector
477 void *GNUNET_CONTAINER_vector_remove_last (struct GNUNET_CONTAINER_Vector *v) {
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);
496 * Delete and return given object from the vector, or return NULL if the object
499 void * GNUNET_CONTAINER_vector_remove_object(struct GNUNET_CONTAINER_Vector *v, void *object) {
500 VectorSegment *segment;
504 v->iteratorSegment = NULL;
505 vectorFindObject(v, object, &segment, &segmentIndex);
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);
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.
526 void *GNUNET_CONTAINER_vector_set_at (struct GNUNET_CONTAINER_Vector *v,
528 unsigned int index) {
529 VectorSegment *segment;
533 if (index >= v->size)
535 v->iteratorSegment = NULL;
536 segmentIndex = vectorFindIndex(v, index, &segment);
537 if (segmentIndex == -1)
539 rvalue = segment->data[segmentIndex];
540 segment->data[segmentIndex] = object;
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.
549 void *GNUNET_CONTAINER_vector_set_object(struct GNUNET_CONTAINER_Vector *v,
552 VectorSegment *segment;
556 v->iteratorSegment = NULL;
557 vectorFindObject (v, oldObject, &segment, &segmentIndex);
560 rvalue = segment->data[segmentIndex];
561 segment->data[segmentIndex] = object;
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.
570 int GNUNET_CONTAINER_vector_swap(struct GNUNET_CONTAINER_Vector *v,
572 unsigned int index2) {
573 VectorSegment * segment1;
574 VectorSegment * segment2;
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;
595 * Return the index of given element or -1 if the element is not found.
597 unsigned int GNUNET_CONTAINER_vector_index_of(struct GNUNET_CONTAINER_Vector *v,
599 VectorSegment * segment;
601 unsigned int segmentStartIndex;
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;
612 return (unsigned int) -1;
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.
622 void ** GNUNET_CONTAINER_vector_elements (struct GNUNET_CONTAINER_Vector *v) {
627 rvalue = GNUNET_malloc_large(v->size * sizeof (void *));
628 for (vs = v->segmentsHead; vs; vs = vs->next) {
631 vs->size * sizeof (void *));
639 /* end of vector.c */