Home | History | Annotate | 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 int
     38 u_vector_init(struct u_vector *vector, uint32_t element_size, uint32_t size)
     39 {
     40    assert(util_is_power_of_two(size));
     41    assert(element_size < size && util_is_power_of_two(element_size));
     42 
     43    vector->head = 0;
     44    vector->tail = 0;
     45    vector->element_size = element_size;
     46    vector->size = size;
     47    vector->data = malloc(size);
     48 
     49    return vector->data != NULL;
     50 }
     51 
     52 void *
     53 u_vector_add(struct u_vector *vector)
     54 {
     55    uint32_t offset, size, split, src_tail, dst_tail;
     56    void *data;
     57 
     58    if (vector->head - vector->tail == vector->size) {
     59       size = vector->size * 2;
     60       data = malloc(size);
     61       if (data == NULL)
     62          return NULL;
     63       src_tail = vector->tail & (vector->size - 1);
     64       dst_tail = vector->tail & (size - 1);
     65       if (src_tail == 0) {
     66          /* Since we know that the vector is full, this means that it's
     67           * linear from start to end so we can do one copy.
     68           */
     69          memcpy((char *)data + dst_tail, vector->data, vector->size);
     70       } else {
     71          /* In this case, the vector is split into two pieces and we have
     72           * to do two copies.  We have to be careful to make sure each
     73           * piece goes to the right locations.  Thanks to the change in
     74           * size, it may or may not still wrap around.
     75           */
     76          split = u_align_u32(vector->tail, vector->size);
     77          assert(vector->tail <= split && split < vector->head);
     78          memcpy((char *)data + dst_tail, (char *)vector->data + src_tail,
     79                 split - vector->tail);
     80          memcpy((char *)data + (split & (size - 1)), vector->data,
     81                 vector->head - split);
     82       }
     83       free(vector->data);
     84       vector->data = data;
     85       vector->size = size;
     86    }
     87 
     88    assert(vector->head - vector->tail < vector->size);
     89 
     90    offset = vector->head & (vector->size - 1);
     91    vector->head += vector->element_size;
     92 
     93    return (char *)vector->data + offset;
     94 }
     95 
     96 void *
     97 u_vector_remove(struct u_vector *vector)
     98 {
     99    uint32_t offset;
    100 
    101    if (vector->head == vector->tail)
    102       return NULL;
    103 
    104    assert(vector->head - vector->tail <= vector->size);
    105 
    106    offset = vector->tail & (vector->size - 1);
    107    vector->tail += vector->element_size;
    108 
    109    return (char *)vector->data + offset;
    110 }
    111