Dave Airlie | 008f54f | 2016-10-14 12:55:03 +1000 | [diff] [blame] | 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 | */ |
Daniel Stone | 2b89547 | 2017-06-09 14:57:20 +0100 | [diff] [blame] | 23 | |
| 24 | #include <string.h> |
| 25 | #include "util/u_math.h" |
Dave Airlie | 008f54f | 2016-10-14 12:55:03 +1000 | [diff] [blame] | 26 | #include "util/u_vector.h" |
| 27 | |
Eric Anholt | 9caba0f | 2017-01-21 16:22:15 +1100 | [diff] [blame] | 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 | |
Dave Airlie | 008f54f | 2016-10-14 12:55:03 +1000 | [diff] [blame] | 37 | int |
| 38 | u_vector_init(struct u_vector *vector, uint32_t element_size, uint32_t size) |
| 39 | { |
Ian Romanick | cd18aa1 | 2018-03-26 10:52:43 -0700 | [diff] [blame] | 40 | assert(util_is_power_of_two_nonzero(size)); |
| 41 | assert(element_size < size && util_is_power_of_two_nonzero(element_size)); |
Dave Airlie | 008f54f | 2016-10-14 12:55:03 +1000 | [diff] [blame] | 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 | } |