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/macros.h"
  35
  36 #ifdef __cplusplus
  37 extern "C" {
  38 #endif
  39
  40 /* TODO - move to u_math.h - name it better etc */
  41 static inline uint32_t
  42 u_align_u32(uint32_t v, uint32_t a)
  43 {
  44    assert(a != 0 && a == (a & -((int32_t) a)));
  45    return (v + a - 1) & ~(a - 1);
  46 }
  47
  48 struct u_vector {
  49    uint32_t head;
  50    uint32_t tail;
  51    uint32_t element_size;
  52    uint32_t size;
  53    void *data;
  54 };
  55
  56 int u_vector_init(struct u_vector *queue, uint32_t element_size, uint32_t size);
  57 void *u_vector_add(struct u_vector *queue);
  58 void *u_vector_remove(struct u_vector *queue);
  59
  60 static inline int
  61 u_vector_length(struct u_vector *queue)
  62 {
  63    return (queue->head - queue->tail) / queue->element_size;
  64 }
  65
  66 static inline void *
  67 u_vector_head(struct u_vector *vector)
  68 {
  69    assert(vector->tail < vector->head);
  70    return (void *)((char *)vector->data +
  71                    ((vector->head - vector->element_size) &
  72                     (vector->size - 1)));
  73 }
  74
  75 static inline void *
  76 u_vector_tail(struct u_vector *vector)
  77 {
  78    return (void *)((char *)vector->data + (vector->tail & (vector->size - 1)));
  79 }
  80
  81 static inline void
  82 u_vector_finish(struct u_vector *queue)
  83 {
  84    free(queue->data);
  85 }
  86
  87 #if !defined(__GNUC__) || defined(__cplusplus)
  88 #define __builtin_types_compatible_p(t1, t2) 1
  89 #endif
  90
  91 #define u_vector_foreach(elem, queue)                                  \
  92    STATIC_ASSERT(__builtin_types_compatible_p(__typeof__(queue), struct u_vector *)); \
  93    for (uint32_t __u_vector_offset = (queue)->tail;                                \
  94         elem = (void *)((char *)(queue)->data + (__u_vector_offset & ((queue)->size - 1))), __u_vector_offset != (queue)->head; \
  95         __u_vector_offset += (queue)->element_size)
  96
  97 #ifdef __cplusplus
  98 }
  99 #endif
 100
 101 #endif
 102