src/util/container_vector.c

   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_create(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_destroy(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 */