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