src/util/u_vector.c

   1 /*
   2  * Copyright © 2015 Intel Corporation
   3  *
   4  * Permission is hereby granted, free of charge, to any person obtaining a
   5  * copy of this software and associated documentation files (the "Software"),
   6  * to deal in the Software without restriction, including without limitation
   7  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
   8  * and/or sell copies of the Software, and to permit persons to whom the
   9  * Software is furnished to do so, subject to the following conditions:
  10  *
  11  * The above copyright notice and this permission notice (including the next
  12  * paragraph) shall be included in all copies or substantial portions of the
  13  * Software.
  14  *
  15  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  16  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  17  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
  18  * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  19  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
  20  * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
  21  * IN THE SOFTWARE.
  22  */
  23
  24 #include <string.h>
  25 #include "util/u_math.h"
  26 #include "util/u_vector.h"
  27
  28 int
  29 u_vector_init(struct u_vector *vector, uint32_t element_size, uint32_t size)
  30 {
  31    assert(util_is_power_of_two(size));
  32    assert(element_size < size && util_is_power_of_two(element_size));
  33
  34    vector->head = 0;
  35    vector->tail = 0;
  36    vector->element_size = element_size;
  37    vector->size = size;
  38    vector->data = malloc(size);
  39
  40    return vector->data != NULL;
  41 }
  42
  43 void *
  44 u_vector_add(struct u_vector *vector)
  45 {
  46    uint32_t offset, size, split, src_tail, dst_tail;
  47    void *data;
  48
  49    if (vector->head - vector->tail == vector->size) {
  50       size = vector->size * 2;
  51       data = malloc(size);
  52       if (data == NULL)
  53          return NULL;
  54       src_tail = vector->tail & (vector->size - 1);
  55       dst_tail = vector->tail & (size - 1);
  56       if (src_tail == 0) {
  57          /* Since we know that the vector is full, this means that it's
  58           * linear from start to end so we can do one copy.
  59           */
  60          memcpy((char *)data + dst_tail, vector->data, vector->size);
  61       } else {
  62          /* In this case, the vector is split into two pieces and we have
  63           * to do two copies.  We have to be careful to make sure each
  64           * piece goes to the right locations.  Thanks to the change in
  65           * size, it may or may not still wrap around.
  66           */
  67          split = u_align_u32(vector->tail, vector->size);
  68          assert(vector->tail <= split && split < vector->head);
  69          memcpy((char *)data + dst_tail, (char *)vector->data + src_tail,
  70                 split - vector->tail);
  71          memcpy((char *)data + (split & (size - 1)), vector->data,
  72                 vector->head - split);
  73       }
  74       free(vector->data);
  75       vector->data = data;
  76       vector->size = size;
  77    }
  78
  79    assert(vector->head - vector->tail < vector->size);
  80
  81    offset = vector->head & (vector->size - 1);
  82    vector->head += vector->element_size;
  83
  84    return (char *)vector->data + offset;
  85 }
  86
  87 void *
  88 u_vector_remove(struct u_vector *vector)
  89 {
  90    uint32_t offset;
  91
  92    if (vector->head == vector->tail)
  93       return NULL;
  94
  95    assert(vector->head - vector->tail <= vector->size);
  96
  97    offset = vector->tail & (vector->size - 1);
  98    vector->tail += vector->element_size;
  99
 100    return (char *)vector->data + offset;
 101 }