Home | History | Annotate | Line # | Download | only in util 
      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 /** @file u_vector.c
     29  *
     30  * A dynamically growable, circular buffer.  Elements are added at head and
     31  * removed from tail. head and tail are free-running uint32_t indices and we
     32  * only compute the modulo with size when accessing the array.  This way,
     33  * number of bytes in the queue is always head - tail, even in case of
     34  * wraparound.
     35  */
     36 
     37 /**
     38  * initial_element_count and element_size must be power-of-two.
     39  */
     40 int
     41 u_vector_init_pow2(struct u_vector *vector,
     42                    uint32_t initial_element_count,
     43                    uint32_t element_size)
     44 {
     45    assert(util_is_power_of_two_nonzero(initial_element_count));
     46    assert(util_is_power_of_two_nonzero(element_size));
     47 
     48    vector->head = 0;
     49    vector->tail = 0;
     50    vector->element_size = element_size;
     51    vector->size = element_size * initial_element_count;
     52    vector->data = malloc(vector->size);
     53 
     54    return vector->data != NULL;
     55 }
     56 
     57 void *
     58 u_vector_add(struct u_vector *vector)
     59 {
     60    uint32_t offset, size, split, src_tail, dst_tail;
     61    void *data;
     62 
     63    if (vector->head - vector->tail == vector->size) {
     64       size = vector->size * 2;
     65       data = malloc(size);
     66       if (data == NULL)
     67          return NULL;
     68       src_tail = vector->tail & (vector->size - 1);
     69       dst_tail = vector->tail & (size - 1);
     70       if (src_tail == 0) {
     71          /* Since we know that the vector is full, this means that it's
     72           * linear from start to end so we can do one copy.
     73           */
     74          memcpy((char *)data + dst_tail, vector->data, vector->size);
     75       } else {
     76          /* In this case, the vector is split into two pieces and we have
     77           * to do two copies.  We have to be careful to make sure each
     78           * piece goes to the right locations.  Thanks to the change in
     79           * size, it may or may not still wrap around.
     80           */
     81          split = u_align_u32(vector->tail, vector->size);
     82          assert(vector->tail <= split && split < vector->head);
     83          memcpy((char *)data + dst_tail, (char *)vector->data + src_tail,
     84                 split - vector->tail);
     85          memcpy((char *)data + (split & (size - 1)), vector->data,
     86                 vector->head - split);
     87       }
     88       free(vector->data);
     89       vector->data = data;
     90       vector->size = size;
     91    }
     92 
     93    assert(vector->head - vector->tail < vector->size);
     94 
     95    offset = vector->head & (vector->size - 1);
     96    vector->head += vector->element_size;
     97 
     98    return (char *)vector->data + offset;
     99 }
    100 
    101 void *
    102 u_vector_remove(struct u_vector *vector)
    103 {
    104    uint32_t offset;
    105 
    106    if (vector->head == vector->tail)
    107       return NULL;
    108 
    109    assert(vector->head - vector->tail <= vector->size);
    110 
    111    offset = vector->tail & (vector->size - 1);
    112    vector->tail += vector->element_size;
    113 
    114    return (char *)vector->data + offset;
    115 }
    116