/*
* container_binary_array.c
*
* see comments in header file.
*
* Portions of this file are subject to the following copyright(s). See
* the Net-SNMP's COPYING file for more details and other copyrights
* that may apply:
*
* Portions of this file are copyrighted by:
* Copyright (c) 2016 VMware, Inc. All rights reserved.
* Use is subject to license terms specified in the COPYING file
* distributed with the Net-SNMP package.
*/
#include <net-snmp/net-snmp-config.h>
#if HAVE_IO_H
#include <io.h>
#endif
#include <stdio.h>
#if HAVE_STDLIB_H
#include <stdlib.h>
#endif
#if HAVE_MALLOC_H
#include <malloc.h>
#endif
#include <sys/types.h>
#if HAVE_STRING_H
#include <string.h>
#else
#include <strings.h>
#endif
#include <net-snmp/net-snmp-includes.h>
#include <net-snmp/types.h>
#include <net-snmp/library/snmp_api.h>
#include <net-snmp/library/container.h>
#include <net-snmp/library/container_binary_array.h>
#include <net-snmp/library/tools.h>
#include <net-snmp/library/snmp_assert.h>
typedef struct binary_array_table_s {
size_t max_size; /* Size of the current data table */
size_t count; /* Index of the next free entry */
int dirty;
void **data; /* The table itself */
} binary_array_table;
typedef struct binary_array_iterator_s {
netsnmp_iterator base;
size_t pos;
} binary_array_iterator;
static netsnmp_iterator *_ba_iterator_get(netsnmp_container *c);
/**********************************************************************
*
*
*
*/
static void
array_qsort(void **data, int first, int last, netsnmp_container_compare *f)
{
int i, j;
void *mid, *tmp;
i = first;
j = last;
mid = data[(first+last)/2];
do {
while (i < last && (*f)(data[i], mid) < 0)
++i;
while (j > first && (*f)(mid, data[j]) < 0)
--j;
if(i < j) {
tmp = data[i];
data[i] = data[j];
data[j] = tmp;
++i;
--j;
}
else if (i == j) {
++i;
--j;
break;
}
} while(i <= j);
if (j > first)
array_qsort(data, first, j, f);
if (i < last)
array_qsort(data, i, last, f);
}
static int
Sort_Array(netsnmp_container *c)
{
binary_array_table *t = (binary_array_table*)c->container_data;
netsnmp_assert(t!=NULL);
netsnmp_assert(c->compare!=NULL);
if (c->flags & CONTAINER_KEY_UNSORTED)
return 0;
if (t->dirty) {
/*
* Sort the table
*/
if (t->count > 1)
array_qsort(t->data, 0, t->count - 1, c->compare);
t->dirty = 0;
/*
* no way to know if it actually changed... just assume so.
*/
++c->sync;
}
return 1;
}
static int
linear_search(const void *val, netsnmp_container *c)
{
binary_array_table *t = (binary_array_table*)c->container_data;
size_t pos = 0;
if (!t->count)
return -1;
if (! (c->flags & CONTAINER_KEY_UNSORTED)) {
snmp_log(LOG_ERR, "linear search on sorted container %s?!?\n",
c->container_name);
return -1;
}
for (; pos < t->count; ++pos) {
if (c->compare(t->data[pos], val) == 0)
break;
}
if (pos >= t->count)
return -1;
return pos;
}
static int
binary_search(const void *val, netsnmp_container *c, int exact, size_t *next)
{
binary_array_table *t = (binary_array_table*)c->container_data;
size_t len = t->count;
size_t half;
size_t first = 0;
size_t middle = 0; /* init not needed; keeps compiler happy */
int result = 0; /* init not needed; keeps compiler happy */
if (!len) {
if (NULL != next)
*next = 0;
return -1;
}
if (c->flags & CONTAINER_KEY_UNSORTED) {
if (!exact) {
snmp_log(LOG_ERR, "non-exact search on unsorted container %s?!?\n",
c->container_name);
return -1;
}
return linear_search(val, c);
}
if (t->dirty)
Sort_Array(c);
while (len > 0) {
half = len >> 1;
middle = first + half;
if ((result = c->compare(t->data[middle], val)) < 0) {
first = middle + 1;
len = len - half - 1;
} else if (result == 0) {
first = middle;
break;
} else {
len = half;
}
}
if (first >= t->count) {
if (exact && NULL != next)
*next = t->count;
return -1;
}
if (first != middle) {
/* last compare wasn't against first, so get actual result */
result = c->compare(t->data[first], val);
}
if(result == 0) {
if (exact && NULL != next)
*next = first+1;
else if (!exact && ++first == t->count) {
if (NULL != next)
*next = first;
first = -1;
}
} else if(exact) {
if (NULL != next) {
if (result > 0)
*next = first;
else
*next = t->count;
}
first = -1;
}
return first;
}
NETSNMP_STATIC_INLINE binary_array_table *
netsnmp_binary_array_initialize(void)
{
binary_array_table *t;
t = SNMP_MALLOC_TYPEDEF(binary_array_table);
if (t == NULL)
return NULL;
t->max_size = 0;
t->count = 0;
t->dirty = 0;
t->data = NULL;
return t;
}
void
netsnmp_binary_array_release(netsnmp_container *c)
{
binary_array_table *t = (binary_array_table*)c->container_data;
SNMP_FREE(t->data);
SNMP_FREE(t);
SNMP_FREE(c);
}
int
netsnmp_binary_array_options_set(netsnmp_container *c, int set, u_int flags)
{
#define BA_FLAGS (CONTAINER_KEY_ALLOW_DUPLICATES|CONTAINER_KEY_UNSORTED)
if (set) {
if ((flags & BA_FLAGS) == flags) {
/** if turning off unsorted, do sort */
int sort = ((c->flags & CONTAINER_KEY_UNSORTED) &&
! (flags & CONTAINER_KEY_UNSORTED));
c->flags = flags;
if (sort) {
binary_array_table *t = (binary_array_table*)c->container_data;
t->dirty = 1; /* force sort */
Sort_Array(c);
}
} else
flags = (u_int)-1; /* unsupported flag */
}
else
return ((c->flags & flags) == flags);
return flags;
}
NETSNMP_STATIC_INLINE size_t
netsnmp_binary_array_count(netsnmp_container *c)
{
binary_array_table *t = (binary_array_table*)c->container_data;
/*
* return count
*/
return t ? t->count : 0;
}
NETSNMP_STATIC_INLINE void *
netsnmp_binary_array_get(netsnmp_container *c, const void *key, int exact)
{
binary_array_table *t = (binary_array_table*)c->container_data;
int index = 0;
/*
* if there is no data, return NULL;
*/
if (!t->count)
return NULL;
/*
* if the table is dirty, sort it.
*/
if (t->dirty)
Sort_Array(c);
/*
* if there is a key, search. Otherwise default is 0;
*/
if (key) {
if ((index = binary_search(key, c, exact, NULL)) == -1)
return NULL;
if (!exact &&
c->flags & CONTAINER_KEY_ALLOW_DUPLICATES) {
int result;
/*
* If duplicates are allowed, we have to be extra
* sure that we didn't just increment to a duplicate,
* thus causing a getnext loop.
*/
result = c->compare(t->data[index], key);
while (result == 0) {
DEBUGMSGTL(("container","skipping duplicate key in %s\n",
c->container_name));
if (++index == t->count)
return NULL;
result = c->compare(t->data[index], key);
}
}
}
return t->data[index];
}
static int
netsnmp_binary_array_get_at(netsnmp_container *c, size_t pos, void **entry)
{
binary_array_table *t = (binary_array_table*)c->container_data;
/*
* if there is no data, return NULL;
*/
if (!t->count || pos >= t->count || NULL == entry)
return -1;
*entry = t->data[pos];
return 0;
}
int
netsnmp_binary_array_remove_at(netsnmp_container *c, size_t index, void **save)
{
binary_array_table *t = (binary_array_table*)c->container_data;
if (save)
*save = NULL;
/*
* if there is no data, return NULL;
*/
if (!t->count)
return -1;
/*
* find old data and save it, if ptr provided
*/
if (save)
*save = t->data[index];
/*
* if entry was last item, just decrement count
*/
--t->count;
if (index != t->count) {
/*
* otherwise, shift array down
*/
memmove(&t->data[index], &t->data[index+1],
sizeof(void*) * (t->count - index));
++c->sync;
}
return 0;
}
int
netsnmp_binary_array_remove(netsnmp_container *c, const void *key, void **save)
{
binary_array_table *t = (binary_array_table*)c->container_data;
int index = 0;
if (save)
*save = NULL;
/*
* if there is no data, return NULL;
*/
if (!t->count)
return 0;
/*
* if the table is dirty, sort it.
*/
if (t->dirty)
Sort_Array(c);
/*
* search
*/
if ((index = binary_search(key, c, 1, NULL)) == -1)
return -1;
return netsnmp_binary_array_remove_at(c, (size_t)index, save);
}
NETSNMP_STATIC_INLINE void
netsnmp_binary_array_for_each(netsnmp_container *c,
netsnmp_container_obj_func *fe,
void *context, int sort)
{
binary_array_table *t = (binary_array_table*)c->container_data;
size_t i;
if (sort && t->dirty)
Sort_Array(c);
for (i = 0; i < t->count; ++i)
(*fe) (t->data[i], context);
}
NETSNMP_STATIC_INLINE void
netsnmp_binary_array_clear(netsnmp_container *c,
netsnmp_container_obj_func *fe,
void *context)
{
binary_array_table *t = (binary_array_table*)c->container_data;
if( NULL != fe ) {
size_t i;
for (i = 0; i < t->count; ++i)
(*fe) (t->data[i], context);
}
t->count = 0;
t->dirty = 0;
++c->sync;
}
static int
_ba_resize_check(binary_array_table *t)
{
size_t new_max;
void ** new_data;
if (t->max_size > t->count)
return 0; /* resize not needed */
/*
* Table is full, so extend it to double the size, or use 10 elements
* if it is empty.
*/
new_max = t->max_size > 0 ? 2 * t->max_size : 10;
new_data = (void**) realloc(t->data, new_max * sizeof(void*));
if (new_data == NULL) {
snmp_log(LOG_ERR, "malloc failed in _ba_resize_check\n");
return -1; /* error */
}
memset(new_data + t->max_size, 0x0,
(new_max - t->max_size) * sizeof(void*));
t->data = new_data;
t->max_size = new_max;
return 1; /* resized */
}
static int
netsnmp_binary_array_insert_before(netsnmp_container *c, size_t index,
const void *entry, int dirty)
{
binary_array_table *t = (binary_array_table*)c->container_data;
if (NULL == entry)
return -1;
if (index > (t->count + 1)) {
DEBUGMSGTL(("container:insert:before", "index out of range\n"));
return -1;
}
/*
* check if we need to resize the array
*/
_ba_resize_check(t);
/*
* shift array
*/
memmove(&t->data[index+1], &t->data[index],
sizeof(void*) * (t->count - index));
/*
* Insert the new entry into the data array
*/
t->data[index] = NETSNMP_REMOVE_CONST(void *, entry);
++t->count;
if (dirty)
t->dirty = 1;
++c->sync;
return 0;
}
NETSNMP_STATIC_INLINE int
netsnmp_binary_array_insert(netsnmp_container *c, const void *const_entry)
{
binary_array_table *t = (binary_array_table*)c->container_data;
int dirty = 0, i = -2;
size_t next, pos;
void *entry = NETSNMP_REMOVE_CONST(void *, const_entry);
if (NULL == entry)
return -1;
/*
* check key if we have at least 1 item and duplicates aren't allowed
*/
if (! (c->flags & CONTAINER_KEY_ALLOW_DUPLICATES) && t->count) {
i = binary_search(entry, c, 1, &next);
if (i > 0) {
DEBUGMSGTL(("container","not inserting duplicate key\n"));
return -1;
}
}
/*
* if unsorted, just add at the end
*/
if (c->flags & CONTAINER_KEY_UNSORTED) {
pos = t->count;
dirty = 1;
} else {
/** if we haven't searched for key yet, do it now */
if (-2 == i) {
if (0 == t->count) {
next = 0;
i = -1;
} else
i = binary_search(entry, c, 1, &next);
}
pos = next;
if ( i > 0 ) /* if key found, advance past any dups */
while (pos < t->count && c->compare(t->data[pos], entry) == 0)
++pos;
}
return netsnmp_binary_array_insert_before(c, pos, entry, dirty);
}
/**********************************************************************
*
* Special case support for subsets
*
*/
static int
binary_search_for_start(netsnmp_index *val, netsnmp_container *c)
{
binary_array_table *t = (binary_array_table*)c->container_data;
size_t len = t->count;
size_t half;
size_t middle;
size_t first = 0;
int result = 0;
if (!len)
return -1;
if (t->dirty)
Sort_Array(c);
while (len > 0) {
half = len >> 1;
middle = first + half;
if ((result = c->ncompare(t->data[middle], val)) < 0) {
first = middle + 1;
len = len - half - 1;
} else
len = half;
}
if ((first >= t->count) ||
c->ncompare(t->data[first], val) != 0)
return -1;
return first;
}
void **
netsnmp_binary_array_get_subset(netsnmp_container *c, void *key, int *len)
{
binary_array_table *t;
void **subset;
int start, end;
size_t i;
/*
* if there is no data, return NULL;
*/
if (!c || !key || !len)
return NULL;
t = (binary_array_table*)c->container_data;
netsnmp_assert(c->ncompare);
if (!t->count || !c->ncompare)
return NULL;
/*
* if the table is dirty, sort it.
*/
if (t->dirty)
Sort_Array(c);
/*
* find matching items
*/
start = end = binary_search_for_start((netsnmp_index *)key, c);
if (start == -1)
return NULL;
for (i = start + 1; i < t->count; ++i) {
if (0 != c->ncompare(t->data[i], key))
break;
++end;
}
*len = end - start + 1;
if (*len <= 0)
return NULL;
subset = (void **)malloc((*len) * sizeof(void*));
if (subset)
memcpy(subset, &t->data[start], sizeof(void*) * (*len));
return subset;
}
/**********************************************************************
*
* container
*
*/
static void *
_ba_find(netsnmp_container *container, const void *data)
{
return netsnmp_binary_array_get(container, data, 1);
}
static void *
_ba_find_next(netsnmp_container *container, const void *data)
{
return netsnmp_binary_array_get(container, data, 0);
}
static int
_ba_insert(netsnmp_container *container, const void *data)
{
return netsnmp_binary_array_insert(container, data);
}
static int
_ba_insert_before(netsnmp_container *container, size_t index, void *data)
{
/** don't trust users direct-acces inserts, mark array dirty */
return netsnmp_binary_array_insert_before(container, index, data, 1);
}
static int
_ba_remove(netsnmp_container *container, const void *data)
{
return netsnmp_binary_array_remove(container,data, NULL);
}
static int
_ba_free(netsnmp_container *container)
{
netsnmp_binary_array_release(container);
return 0;
}
static size_t
_ba_size(netsnmp_container *container)
{
return netsnmp_binary_array_count(container);
}
static void
_ba_for_each(netsnmp_container *container, netsnmp_container_obj_func *f,
void *context)
{
netsnmp_binary_array_for_each(container, f, context, 1);
}
static void
_ba_clear(netsnmp_container *container, netsnmp_container_obj_func *f,
void *context)
{
netsnmp_binary_array_clear(container, f, context);
}
static netsnmp_void_array *
_ba_get_subset(netsnmp_container *container, void *data)
{
netsnmp_void_array * va;
void ** rtn;
int len;
rtn = netsnmp_binary_array_get_subset(container, data, &len);
if (NULL==rtn)
return NULL;
va = SNMP_MALLOC_TYPEDEF(netsnmp_void_array);
if (va == NULL) {
free(rtn);
return NULL;
}
va->size = len;
va->array = rtn;
return va;
}
static int _ba_options(netsnmp_container *c, int set, u_int flags)
{
return netsnmp_binary_array_options_set(c, set, flags);
}
static netsnmp_container *
_ba_duplicate(netsnmp_container *c, void *ctx, u_int flags)
{
netsnmp_container *dup;
binary_array_table *dupt, *t;
if (flags) {
snmp_log(LOG_ERR, "binary arry duplicate does not supprt flags yet\n");
return NULL;
}
dup = netsnmp_container_get_binary_array();
if (NULL == dup) {
snmp_log(LOG_ERR," no memory for binary array duplicate\n");
return NULL;
}
/*
* deal with container stuff
*/
if (netsnmp_container_data_dup(dup, c) != 0) {
netsnmp_binary_array_release(dup);
return NULL;
}
/*
* deal with data
*/
dupt = (binary_array_table*)dup->container_data;
t = (binary_array_table*)c->container_data;
dupt->max_size = t->max_size;
dupt->count = t->count;
dupt->dirty = t->dirty;
/*
* shallow copy
*/
dupt->data = (void**) malloc(dupt->max_size * sizeof(void*));
if (NULL == dupt->data) {
snmp_log(LOG_ERR, "no memory for binary array duplicate\n");
netsnmp_binary_array_release(dup);
return NULL;
}
memcpy(dupt->data, t->data, dupt->max_size * sizeof(void*));
return dup;
}
netsnmp_container *
netsnmp_container_get_binary_array(void)
{
/*
* allocate memory
*/
netsnmp_container *c = SNMP_MALLOC_TYPEDEF(netsnmp_container);
if (NULL==c) {
snmp_log(LOG_ERR, "couldn't allocate memory\n");
return NULL;
}
c->container_data = netsnmp_binary_array_initialize();
/*
* NOTE: CHANGES HERE MUST BE DUPLICATED IN duplicate AS WELL!!
*/
netsnmp_init_container(c, NULL, _ba_free, _ba_size, NULL, _ba_insert,
_ba_remove, _ba_find);
c->find_next = _ba_find_next;
c->get_subset = _ba_get_subset;
c->get_iterator = _ba_iterator_get;
c->for_each = _ba_for_each;
c->clear = _ba_clear;
c->options = _ba_options;
c->duplicate = _ba_duplicate;
c->get_at = netsnmp_binary_array_get_at;
c->remove_at = netsnmp_binary_array_remove_at;
c->insert_before = _ba_insert_before;
return c;
}
netsnmp_factory *
netsnmp_container_get_binary_array_factory(void)
{
static netsnmp_factory f = { "binary_array",
(netsnmp_factory_produce_f*)
netsnmp_container_get_binary_array };
return &f;
}
void
netsnmp_container_binary_array_init(void)
{
netsnmp_container_register("binary_array",
netsnmp_container_get_binary_array_factory());
}
/**********************************************************************
*
* iterator
*
*/
NETSNMP_STATIC_INLINE binary_array_table *
_ba_it2cont(binary_array_iterator *it)
{
if(NULL == it) {
netsnmp_assert(NULL != it);
return NULL;
}
if(NULL == it->base.container) {
netsnmp_assert(NULL != it->base.container);
return NULL;
}
if(NULL == it->base.container->container_data) {
netsnmp_assert(NULL != it->base.container->container_data);
return NULL;
}
return (binary_array_table*)(it->base.container->container_data);
}
NETSNMP_STATIC_INLINE void *
_ba_iterator_position(binary_array_iterator *it, size_t pos)
{
binary_array_table *t = _ba_it2cont(it);
if (NULL == t)
return t; /* msg already logged */
if(it->base.container->sync != it->base.sync) {
DEBUGMSGTL(("container:iterator", "out of sync\n"));
return NULL;
}
if(0 == t->count) {
DEBUGMSGTL(("container:iterator", "empty\n"));
return NULL;
}
else if(pos >= t->count) {
DEBUGMSGTL(("container:iterator", "end of container\n"));
return NULL;
}
return t->data[ pos ];
}
static void *
_ba_iterator_curr(binary_array_iterator *it)
{
if(NULL == it) {
netsnmp_assert(NULL != it);
return NULL;
}
return _ba_iterator_position(it, it->pos);
}
static void *
_ba_iterator_first(binary_array_iterator *it)
{
return _ba_iterator_position(it, 0);
}
static void *
_ba_iterator_next(binary_array_iterator *it)
{
if(NULL == it) {
netsnmp_assert(NULL != it);
return NULL;
}
++it->pos;
return _ba_iterator_position(it, it->pos);
}
static void *
_ba_iterator_last(binary_array_iterator *it)
{
binary_array_table* t = _ba_it2cont(it);
if(NULL == t) {
netsnmp_assert(NULL != t);
return NULL;
}
return _ba_iterator_position(it, t->count - 1 );
}
static int
_ba_iterator_remove(binary_array_iterator *it)
{
binary_array_table* t = _ba_it2cont(it);
if(NULL == t) {
netsnmp_assert(NULL != t);
return -1;
}
/*
* since this iterator was used for the remove, keep it in sync with
* the container. Also, back up one so that next will be the position
* that was just removed.
*/
++it->base.sync;
return netsnmp_binary_array_remove_at(it->base.container, it->pos--, NULL);
}
static int
_ba_iterator_reset(binary_array_iterator *it)
{
binary_array_table* t = _ba_it2cont(it);
if(NULL == t) {
netsnmp_assert(NULL != t);
return -1;
}
if (t->dirty)
Sort_Array(it->base.container);
/*
* save sync count, to make sure container doesn't change while
* iterator is in use.
*/
it->base.sync = it->base.container->sync;
it->pos = 0;
return 0;
}
static int
_ba_iterator_release(netsnmp_iterator *it)
{
free(it);
return 0;
}
static netsnmp_iterator *
_ba_iterator_get(netsnmp_container *c)
{
binary_array_iterator* it;
if(NULL == c)
return NULL;
it = SNMP_MALLOC_TYPEDEF(binary_array_iterator);
if(NULL == it)
return NULL;
it->base.container = c;
it->base.first = (netsnmp_iterator_rtn*)_ba_iterator_first;
it->base.next = (netsnmp_iterator_rtn*)_ba_iterator_next;
it->base.curr = (netsnmp_iterator_rtn*)_ba_iterator_curr;
it->base.last = (netsnmp_iterator_rtn*)_ba_iterator_last;
it->base.remove = (netsnmp_iterator_rc*)_ba_iterator_remove;
it->base.reset = (netsnmp_iterator_rc*)_ba_iterator_reset;
it->base.release = (netsnmp_iterator_rc*)_ba_iterator_release;
(void)_ba_iterator_reset(it);
return (netsnmp_iterator *)it;
}