From bf4630076762d9c20c16c80c1c791f352b046dd1 Mon Sep 17 00:00:00 2001 From: Brad Bishop Date: Mon, 30 Jun 2014 22:10:16 -0500 Subject: Port FFS tools over from Building Block repository. --- clib/src/array.c | 490 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 490 insertions(+) create mode 100644 clib/src/array.c (limited to 'clib/src/array.c') diff --git a/clib/src/array.c b/clib/src/array.c new file mode 100644 index 0000000..55e261c --- /dev/null +++ b/clib/src/array.c @@ -0,0 +1,490 @@ +/* + * Copyright (c) International Business Machines Corp., 2014 + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +/* + * File: array.c + * Author: Shaun Wetzstein + * Descr: Sparse Array + * Note: + * Date: 08/29/10 + */ + +#include +#include +#include +#include +#include +#include +#include +#include +#include + +#include "assert.h" +#include "misc.h" +#include "hash.h" +#include "array.h" +#include "slab.h" +#include "mqueue.h" +#include "tree.h" +#include "tree_iter.h" +#include "bb_trace.h" +#include "memory_leak_detection.h" + +/*! @cond */ +#define ARRAY_ELEM_SIZE_MIN 1 +#define ARRAY_ELEM_NUM_MIN 64 + +#define ARRAY_MAGIC 0x48444152 +#define ARRAY_NODE_MAGIC 0x4E444152 +/*! @endcond */ + +/* ======================================================================= */ + +/*! @cond */ +typedef struct array_node array_node_t; + +struct array_node { + uint32_t magic; + uint32_t address; + + tree_node_t node; +}; + +const char *__array_msg[] = { + "array: unexpected NULL pointer", + "array: unexpected cache and/or alloc size", + "array: out-of-memory", + "array: uninitialized array element", + "array: unexpected magic number", + "array: unexpected NULL message channel", +}; + +#define ARRAY_NULL (__array_msg[0]) +#define ARRAY_SIZE (__array_msg[1]) +#define ARRAY_OOM (__array_msg[2]) +#define ARRAY_UNINIT_ELEM (__array_msg[3]) +#define ARRAY_MAGIC_CHECK (__array_msg[4]) +#define ARRAY_MQ_NULL (__array_msg[5]) +/*! @endcond */ + +/* ======================================================================= */ + +#define __index_to_page(i,s) \ +({ \ + typeof(i) _p = ((i) / (s)); \ + (i) >= 0 ? _p :_p - 1; \ +}) + +#define __index_to_page_hashed(i,s) \ +({ \ + typeof(i) _h = int32_hash1(__index_to_page((i),(s))); \ + _h; \ +}) + +#define __page_to_low(p,s) \ +({ \ + typeof(p) _l = (p) * (s); \ + (p) >= 0 ? _l : _l - 1; \ +}) + +#define __page_to_high(p,s) \ +({ \ + typeof(p) _h = (p) * (s) + (s) - (typeof(p))1; \ + _h; \ +}) + +/* ======================================================================= */ + +static array_node_t *__array_grow(array_t * self, size_t idx) +{ + if (unlikely(self == NULL)) + throw_unexpected(ARRAY_NULL); + + array_node_t *node = NULL; + switch (POSIX_MEMALIGN + ((void **)&node, self->page_size, self->page_size)) { + case EINVAL: + throw_unexpected(ARRAY_SIZE); + case ENOMEM: + throw_unexpected(ARRAY_OOM); + } + assert(node != NULL); + + node->magic = ARRAY_NODE_MAGIC; + node->address = (uint32_t) node; + + const void *key = + (const void *)__index_to_page_hashed(idx, self->elem_num); + tree_node_init(&node->node, key); + + splay_insert(&self->tree, &node->node); + self->pages++; + + size_t page = __index_to_page(idx, self->elem_num); + + self->low = min(self->low, __page_to_low(page, self->elem_num)); + self->high = max(self->high, __page_to_high(page, self->elem_num)); + + return node; +} + +static int __array_compare(const int i1, const int i2) +{ + return i1 - i2; +} + +void array_init(array_t * self, size_t elem_size, size_t elem_num) +{ + if (unlikely(self == NULL)) + throw_unexpected(ARRAY_NULL); + + self->magic = ARRAY_MAGIC; + self->high = 0; + self->low = UINT32_MAX; + self->size = 0; + self->pages = 0; + + self->elem_size = max(elem_size, ARRAY_ELEM_SIZE_MIN); + self->elem_num = max(elem_num, ARRAY_ELEM_NUM_MIN); + + self->page_size = __round_pow2(elem_size * elem_num); + + self->map_size = align(elem_num / CHAR_BIT, sizeof(uint32_t)); + + self->elem_num = + (self->page_size - sizeof(array_node_t) - + self->map_size) / self->elem_size; + + tree_init(&self->tree, (compare_f) __array_compare); +} + +static void __array_delete(array_t * self) +{ + if (self != NULL) { + while (self->tree.root != NULL) { + array_node_t *node; + node = + container_of(tree_root(&self->tree), array_node_t, + node); + splay_remove(&self->tree, &node->node); + FREE(node); + } + tree_init(&self->tree, (compare_f) __array_compare); + } +} + +void array_delete(array_t * self) +{ + __array_delete(self); +} + +static void *__array_find_page(array_t * self, size_t idx) +{ + const void *hash = + (const void *)__index_to_page_hashed(idx, self->elem_num); + tree_node_t *node = tree_find(&self->tree, hash); + + if (node == NULL) + return (void *)__array_grow(self, idx); + else + return (void *)container_of(node, array_node_t, node); + + return NULL; +} + +static uint8_t *__array_find_map(array_t * self, size_t idx) +{ + if (unlikely(self == NULL)) + throw_unexpected(ARRAY_NULL); + + const void *hash = + (const void *)__index_to_page_hashed(idx, self->elem_num); + uint8_t *map = (uint8_t *) tree_find(&self->tree, hash); + if (map != NULL) + map += sizeof(tree_node_t); + + return map; +} + +const void *array_at(array_t * self, size_t idx) +{ + if (unlikely(self == NULL)) + throw_unexpected(ARRAY_NULL); + + uint32_t offset = idx % self->elem_num; + + uint8_t *map = __array_find_page(self, idx); + map += sizeof(array_node_t); + + uint8_t byte = offset / CHAR_BIT; + uint8_t mask = 0x80 >> (offset % CHAR_BIT); + + if ((map[byte] & mask) == 0) + throw_unexpected(ARRAY_UNINIT_ELEM); + + return map + self->map_size + (self->elem_size * offset); +} + +void array_get3(array_t * self, size_t elem_off, void *ptr) +{ + return array_get4(self, elem_off, ptr, 1); +} + +void array_get4(array_t * self, size_t elem_off, void *ptr, size_t elem_num) +{ + if (unlikely(self == NULL)) + throw_unexpected(ARRAY_NULL); + + while (0 < elem_num) { + memcpy(ptr, array_at(self, elem_off), self->elem_size); + + elem_off++; + elem_num--; + + ptr += self->elem_size; + } +} + +void __array_put(array_t * self, size_t elem_off, const void *ptr) +{ + if (unlikely(self == NULL)) + throw_unexpected(ARRAY_NULL); + + uint32_t offset = elem_off % self->elem_num; + + uint8_t *map = __array_find_page(self, elem_off); + map += sizeof(array_node_t); + + uint8_t byte = offset / CHAR_BIT; + uint8_t mask = 0x80 >> (offset % CHAR_BIT); + + if ((map[byte] & mask) == 0) + self->size++; + + map[byte] |= mask; + + memcpy(map + self->map_size + (self->elem_size * offset), + ptr, self->elem_size); +} + +void array_put3(array_t * self, size_t elem_off, const void *ptr) +{ + return array_put4(self, elem_off, ptr, 1); +} + +void array_put4(array_t * self, size_t elem_off, const void *ptr, + size_t elem_num) +{ + if (unlikely(self == NULL)) + throw_unexpected(ARRAY_NULL); + + while (0 < elem_num) { + __array_put(self, elem_off, ptr); + + elem_off++; + elem_num--; + + ptr += self->elem_size; + } +} + +bool array_status2(array_t * self, size_t idx) +{ + uint8_t *map = __array_find_map(self, idx); + + uint32_t offset = idx % self->elem_num; + uint8_t byte = offset / CHAR_BIT; + uint8_t mask = 0x80 >> (offset % CHAR_BIT); + + return ! !(map[byte] & mask); +} + +bool array_status3(array_t * self, size_t idx, bool status) +{ + uint8_t *map = __array_find_map(self, idx); + + if (map == NULL) { + map = (uint8_t *) __array_grow(self, idx); + map += sizeof(array_node_t); + } + + uint32_t offset = idx % self->elem_num; + uint8_t byte = offset / CHAR_BIT; + uint8_t mask = 0x80 >> (offset % CHAR_BIT); + + bool ret = ! !(map[byte] & mask); + + map[byte] &= ~mask; + if (status) + map[byte] |= mask; + + return ret; +} + +void array_resize(array_t * self, size_t size) +{ + if (unlikely(self == NULL)) + throw_unexpected(ARRAY_NULL); + while (0 < size) { + (void)__array_grow(self, self->high + 1); + size /= self->elem_num; + } +} + +size_t array_size(array_t * self) +{ + if (unlikely(self == NULL)) + throw_unexpected(ARRAY_NULL); + return self->size; +} + +size_t array_pages(array_t * self) +{ + if (unlikely(self == NULL)) + throw_unexpected(ARRAY_NULL); + return self->pages; +} + +size_t array_capacity(array_t * self) +{ + if (unlikely(self == NULL)) + throw_unexpected(ARRAY_NULL); + return self->high - self->low + 1; +} + +size_t array_low(array_t * self) +{ + if (unlikely(self == NULL)) + throw_unexpected(ARRAY_NULL); + return self->low; +} + +size_t array_high(array_t * self) +{ + if (unlikely(self == NULL)) + throw_unexpected(ARRAY_NULL); + return self->high; +} + +void array_send(array_t * self, mqueue_t * mq) +{ + if (unlikely(self == NULL)) + throw_unexpected(ARRAY_NULL); + if (unlikely(mq == NULL)) + throw_unexpected(ARRAY_MQ_NULL); + + mqueue_send(mq, (char *)self, sizeof(*self)); + + tree_iter_t it; + tree_iter_init(&it, &self->tree, TI_FLAG_FWD); + + array_node_t *node; + tree_for_each(&it, node, node) { + if (node->magic != ARRAY_NODE_MAGIC) + throw_unexpected(ARRAY_MAGIC_CHECK); + + mqueue_send(mq, (char *)node, self->page_size); + } +} + +void array_receive(array_t * self, mqueue_t * mq) +{ + if (unlikely(self == NULL)) + throw_unexpected(ARRAY_NULL); + if (unlikely(mq == NULL)) + throw_unexpected(ARRAY_MQ_NULL); + + __array_delete(self); + + mqueue_attr_t attr = mqueue_getattr(mq); + + array_node_t *node = NULL; + switch (POSIX_MEMALIGN + ((void **)&node, attr.mq_msgsize, attr.mq_msgsize)) { + case EINVAL: + throw_unexpected(ARRAY_SIZE); + case ENOMEM: + throw_unexpected(ARRAY_OOM); + } + assert(node != NULL); + + ssize_t len = mqueue_receive(mq, (void *)node, attr.mq_msgsize); + assert(0 < len); + + memcpy(self, (void *)node, sizeof(*self)); + tree_init(&self->tree, (compare_f) __array_compare); + + for (int i = 0; i < array_pages(self); i++) { + if (node == NULL) { + switch (POSIX_MEMALIGN + ((void **)&node, attr.mq_msgsize, + attr.mq_msgsize)) { + case EINVAL: + throw_unexpected(ARRAY_SIZE); + case ENOMEM: + throw_unexpected(ARRAY_OOM); + } + } + + len = mqueue_receive(mq, (void *)node, attr.mq_msgsize); + assert(0 < len); + + node->address = (uint32_t) node; + tree_node_init(&node->node, node->node.key); + splay_insert(&self->tree, &node->node); + + node = NULL; + } +} + +void array_dump(array_t * self, FILE * out) +{ + if (self != NULL) { + fprintf(out, + "array: [ page_size: %5u pages: %5u map_size: %5u capacity: %10u ]\n", + self->page_size, self->pages, self->map_size, + array_capacity(self)); + fprintf(out, + " [ elem_size: %5u elem_num: %5u size: %10u range: (%u....%u) ]\n", + self->elem_size, self->elem_num, array_size(self), + array_low(self), array_high(self)); + + dump_memory(out, (unsigned long)self, self, sizeof(*self)); + + tree_iter_t it; + for (tree_iter_init(&it, &self->tree, TI_FLAG_FWD); + tree_iter_elem(&it); tree_iter_inc(&it)) { + array_node_t *node; + node = + container_of(tree_iter_elem(&it), array_node_t, + node); + + fprintf(out, "magic[%x] address[%x]\n", + node->magic, node->address); + fprintf(out, + "n[%p] left[%p] right[%p] parent[%p] key[%p] \n", + &node->node, node->node.left, node->node.right, + node->node.parent, node->node.key); + + dump_memory(out, (unsigned long)node, node, + self->page_size); + } + } +} + +/* ======================================================================= */ -- cgit v1.2.1