src/util/u_vector.h

   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 /*
  25  * u_vector is a vector based queue for storing arbitrary
  26  * sized arrays of objects without using a linked list.
  27  */
  28
  29 #ifndef U_VECTOR_H
  30 #define U_VECTOR_H
  31
  32 #include <stdint.h>
  33 #include <stdlib.h>
  34 #include "util/u_math.h"
  35 #include "util/macros.h"
  36
  37 /* TODO - move to u_math.h - name it better etc */
  38 static inline uint32_t
  39 u_align_u32(uint32_t v, uint32_t a)
  40 {
  41    assert(a != 0 && a == (a & -a));
  42    return (v + a - 1) & ~(a - 1);
  43 }
  44
  45 struct u_vector {
  46    uint32_t head;
  47    uint32_t tail;
  48    uint32_t element_size;
  49    uint32_t size;
  50    void *data;
  51 };
  52
  53 int u_vector_init(struct u_vector *queue, uint32_t element_size, uint32_t size);
  54 void *u_vector_add(struct u_vector *queue);
  55 void *u_vector_remove(struct u_vector *queue);
  56
  57 static inline int
  58 u_vector_length(struct u_vector *queue)
  59 {
  60    return (queue->head - queue->tail) / queue->element_size;
  61 }
  62
  63 static inline void *
  64 u_vector_head(struct u_vector *vector)
  65 {
  66    assert(vector->tail < vector->head);
  67    return (void *)((char *)vector->data +
  68                    ((vector->head - vector->element_size) &
  69                     (vector->size - 1)));
  70 }
  71
  72 static inline void *
  73 u_vector_tail(struct u_vector *vector)
  74 {
  75    return (void *)((char *)vector->data + (vector->tail & (vector->size - 1)));
  76 }
  77
  78 static inline void
  79 u_vector_finish(struct u_vector *queue)
  80 {
  81    free(queue->data);
  82 }
  83
  84 #define u_vector_foreach(elem, queue)                                  \
  85    STATIC_ASSERT(__builtin_types_compatible_p(__typeof__(queue), struct u_vector *)); \
  86    for (uint32_t __u_vector_offset = (queue)->tail;                                \
  87         elem = (queue)->data + (__u_vector_offset & ((queue)->size - 1)), __u_vector_offset < (queue)->head; \
  88         __u_vector_offset += (queue)->element_size)
  89
  90
  91 #endif
  92