diff options
Diffstat (limited to 'lib/port-array.c')
| -rw-r--r-- | lib/port-array.c | 183 |
1 files changed, 183 insertions, 0 deletions
diff --git a/lib/port-array.c b/lib/port-array.c new file mode 100644 index 000000000..87bb21687 --- /dev/null +++ b/lib/port-array.c @@ -0,0 +1,183 @@ +/* + * Copyright (c) 2008 Nicira Networks. + * + * 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 <config.h> +#include "port-array.h" +#include <stdlib.h> + +static struct port_array_l2 l2_sentinel; +static struct port_array_l3 l3_sentinel; +static bool inited; + +/* Initializes 'pa' as an empty port_array. */ +void +port_array_init(struct port_array *pa) +{ + size_t i; + if (!inited) { + inited = true; + for (i = 0; i < PORT_ARRAY_L2_SIZE; i++) { + l2_sentinel.l2[i] = &l3_sentinel; + } + } + for (i = 0; i < PORT_ARRAY_L1_SIZE; i++) { + pa->l1[i] = &l2_sentinel; + } +} + +/* Frees all the memory allocated for 'pa'. It is the client's responsibility + * to free memory that 'pa' elements point to. */ +void +port_array_destroy(struct port_array *pa) +{ + unsigned int l1_idx; + + for (l1_idx = 0; l1_idx < PORT_ARRAY_L1_SIZE; l1_idx++) { + struct port_array_l2 *l2 = pa->l1[l1_idx]; + + if (l2 != &l2_sentinel) { + unsigned int l2_idx; + + for (l2_idx = 0; l2_idx < PORT_ARRAY_L2_SIZE; l2_idx++) { + struct port_array_l3 *l3 = l2->l2[l2_idx]; + if (l3 != &l3_sentinel) { + free(l3); + } + } + free(l2); + } + } +} + +/* Clears all elements of 'pa' to null pointers. */ +void +port_array_clear(struct port_array *pa) +{ + port_array_destroy(pa); + port_array_init(pa); +} + +/* Sets 'pa' element numbered 'idx' to 'p'. */ +void +port_array_set(struct port_array *pa, uint16_t idx, void *p) +{ + struct port_array_l2 **l2p, *l2; + struct port_array_l3 **l3p, *l3; + + /* Traverse level 1. */ + l2p = &pa->l1[PORT_ARRAY_L1(idx)]; + if (*l2p == &l2_sentinel) { + *l2p = xmemdup(&l2_sentinel, sizeof l2_sentinel); + } + l2 = *l2p; + + /* Traverse level 2. */ + l3p = &l2->l2[PORT_ARRAY_L2(idx)]; + if (*l3p == &l3_sentinel) { + *l3p = xmemdup(&l3_sentinel, sizeof l3_sentinel); + } + l3 = *l3p; + + /* Set level 3. */ + l3->l3[PORT_ARRAY_L3(idx)] = p; +} + +static void * +next(const struct port_array *pa, unsigned int *idxp) +{ + unsigned int idx = *idxp; + + /* Using shift-right directly here, instead of PORT_ARRAY_L1(idx), ensures + * that with an initially too-big value of '*idxp' we will skip the outer + * loop and return NULL. */ + unsigned int l1_idx = idx >> PORT_ARRAY_L1_SHIFT; + unsigned int l2_idx = PORT_ARRAY_L2(idx); + unsigned int l3_idx = PORT_ARRAY_L3(idx); + while (l1_idx < PORT_ARRAY_L1_SIZE) { + struct port_array_l2 *l2 = pa->l1[l1_idx]; + if (l2 != &l2_sentinel) { + while (l2_idx < PORT_ARRAY_L2_SIZE) { + struct port_array_l3 *l3 = l2->l2[l2_idx]; + if (l3 != &l3_sentinel) { + while (l3_idx < PORT_ARRAY_L3_SIZE) { + void *p = l3->l3[l3_idx]; + if (p) { + *idxp = ((l1_idx << PORT_ARRAY_L1_SHIFT) + | (l2_idx << PORT_ARRAY_L2_SHIFT) + | (l3_idx << PORT_ARRAY_L3_SHIFT)); + return p; + } + l3_idx++; + } + } + l2_idx++; + l3_idx = 0; + } + } + l1_idx++; + l2_idx = 0; + l3_idx = 0; + } + *idxp = PORT_ARRAY_SIZE; + return NULL; +} + +/* Returns the value of the lowest-numbered non-empty element of 'pa', and sets + * '*idxp' to that element's index. If 'pa' is entirely empty, returns a null + * pointer and sets '*idxp' to 65536. */ +void * +port_array_first(const struct port_array *pa, unsigned int *idxp) +{ + *idxp = 0; + return next(pa, idxp); +} + +/* Returns the value of the lowest-numbered non-empty element of 'pa' greater + * than the initial value of '*idxp', and sets '*idxp' to that element's index. + * If 'pa' contains no non-empty elements with indexes greater than the initial + * value of '*idxp', returns a null pointer and sets '*idxp' to 65536. */ +void * +port_array_next(const struct port_array *pa, unsigned int *idxp) +{ + ++*idxp; + return next(pa, idxp); +} + +/* Returns the number of non-null elements of 'pa'. */ +unsigned int +port_array_count(const struct port_array *pa) +{ + unsigned int l1_idx, l2_idx, l3_idx; + unsigned int count; + + count = 0; + for (l1_idx = 0; l1_idx < PORT_ARRAY_L1_SIZE; l1_idx++) { + struct port_array_l2 *l2 = pa->l1[l1_idx]; + if (l2 != &l2_sentinel) { + for (l2_idx = 0; l2_idx < PORT_ARRAY_L2_SIZE; l2_idx++) { + struct port_array_l3 *l3 = l2->l2[l2_idx]; + if (l3 != &l3_sentinel) { + for (l3_idx = 0; l3_idx < PORT_ARRAY_L3_SIZE; l3_idx++) { + if (l3->l3[l3_idx]) { + count++; + } + } + } + } + } + } + return count; +} |