| /* |
| * Copyright (c) 2018 The Fuchsia Authors. |
| * |
| * Permission to use, copy, modify, and/or distribute this software for any |
| * purpose with or without fee is hereby granted, provided that the above |
| * copyright notice and this permission notice appear in all copies. |
| * |
| * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES |
| * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF |
| * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR |
| * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES |
| * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN |
| * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF |
| * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. |
| */ |
| |
| #include "sparse_array.h" |
| |
| #include <stdlib.h> |
| |
| #include <zircon/assert.h> |
| |
| // An individual element is either a part of the used list or the free list at |
| // any given time, each of which is a non-circular doubly-linked list terminated |
| // at the head and tail by an index value of -1. |
| struct sa_elem { |
| ssize_t prev_ndx; |
| ssize_t next_ndx; |
| void* ptr; |
| }; |
| |
| // We store a sparse array as a set of elements with two lists -- one for available |
| // elements and one for in use elements. "free" and "used" provide the index of the |
| // head of the list of unused and used indices, respectively. |
| struct sparse_array { |
| size_t size; |
| ssize_t free; |
| ssize_t used; |
| struct sa_elem elems[0]; |
| }; |
| |
| #define RANGE_CHECK(sa, ndx) ZX_DEBUG_ASSERT(((ndx) >= 0) && (((size_t)(ndx)) < sa->size)) |
| |
| void sa_init(sparse_array_t* psa, size_t size) { |
| ZX_DEBUG_ASSERT(size > 0); |
| size_t total_size = sizeof(struct sparse_array) + (sizeof(struct sa_elem) * size); |
| *psa = calloc(1, total_size); |
| if (*psa == NULL) { return; } |
| |
| sparse_array_t sa = *psa; |
| sa->size = size; |
| |
| // Initialize used list as empty |
| sa->used = -1; |
| |
| // Add all elements to the free list |
| sa->elems[0].prev_ndx = -1; |
| for (ssize_t ndx = 0; ndx < ((ssize_t)size - 1); ndx++) { |
| sa->elems[ndx + 1].prev_ndx = ndx; |
| sa->elems[ndx].next_ndx = ndx + 1; |
| } |
| sa->elems[size - 1].next_ndx = -1; |
| |
| // Initialize free list to point to a list of all elements |
| sa->free = 0; |
| } |
| |
| void sa_free(sparse_array_t sa) { |
| free(sa); |
| } |
| |
| ssize_t sa_add(sparse_array_t sa, void* payload) { |
| ssize_t elem_ndx = sa->free; |
| if (elem_ndx == -1) { return -1; } |
| RANGE_CHECK(sa, elem_ndx); |
| struct sa_elem* elem = &sa->elems[elem_ndx]; |
| |
| // Remove from free list |
| sa->free = elem->next_ndx; |
| if (sa->free != -1) { |
| RANGE_CHECK(sa, sa->free); |
| sa->elems[sa->free].prev_ndx = -1; |
| } |
| |
| // Add to used list |
| elem->next_ndx = sa->used; |
| if (sa->used != -1) { |
| RANGE_CHECK(sa, sa->used); |
| sa->elems[sa->used].prev_ndx = elem_ndx; |
| } |
| sa->used = elem_ndx; |
| |
| ZX_DEBUG_ASSERT(elem->ptr == NULL); |
| elem->ptr = payload; |
| |
| return elem_ndx; |
| } |
| |
| void* sa_get(sparse_array_t sa, ssize_t ndx) { |
| RANGE_CHECK(sa, ndx); |
| return sa->elems[ndx].ptr; |
| } |
| |
| void sa_remove(sparse_array_t sa, ssize_t ndx) { |
| RANGE_CHECK(sa, ndx); |
| struct sa_elem* elem = &sa->elems[ndx]; |
| ssize_t prev_ndx = elem->prev_ndx; |
| ssize_t next_ndx = elem->next_ndx; |
| |
| // Remove from used list |
| if (prev_ndx == -1) { |
| sa->used = next_ndx; |
| } else { |
| RANGE_CHECK(sa, prev_ndx); |
| struct sa_elem* prev_elem = &sa->elems[prev_ndx]; |
| prev_elem->next_ndx = next_ndx; |
| } |
| if (next_ndx != -1) { |
| RANGE_CHECK(sa, next_ndx); |
| struct sa_elem* next_elem = &sa->elems[next_ndx]; |
| next_elem->prev_ndx = prev_ndx; |
| } |
| |
| // Add to free list |
| next_ndx = sa->free; |
| elem->prev_ndx = -1; |
| elem->next_ndx = next_ndx; |
| elem->ptr = NULL; |
| sa->free = ndx; |
| if (next_ndx != -1) { |
| RANGE_CHECK(sa, next_ndx); |
| struct sa_elem* next_elem = &sa->elems[next_ndx]; |
| next_elem->prev_ndx = ndx; |
| } |
| } |
| |
| void sa_for_each(sparse_array_t sa, void (*fn)(ssize_t, void*, void*), void* ctx) { |
| ssize_t next_ndx = sa->used; |
| while (next_ndx != -1) { |
| RANGE_CHECK(sa, next_ndx); |
| struct sa_elem* elem = &sa->elems[next_ndx]; |
| fn(next_ndx, elem->ptr, ctx); |
| next_ndx = sa->elems[next_ndx].next_ndx; |
| } |
| } |