00001 /* 00002 * container_binary_array.c 00003 * $Id$ 00004 * 00005 * see comments in header file. 00006 * 00007 */ 00008 00009 #include <net-snmp/net-snmp-config.h> 00010 00011 #if HAVE_IO_H 00012 #include <io.h> 00013 #endif 00014 #include <stdio.h> 00015 #if HAVE_STDLIB_H 00016 #include <stdlib.h> 00017 #endif 00018 #if HAVE_MALLOC_H 00019 #include <malloc.h> 00020 #endif 00021 #include <sys/types.h> 00022 #if HAVE_STRING_H 00023 #include <string.h> 00024 #else 00025 #include <strings.h> 00026 #endif 00027 00028 #include <net-snmp/net-snmp-includes.h> 00029 #include <net-snmp/types.h> 00030 #include <net-snmp/library/snmp_api.h> 00031 #include <net-snmp/library/container.h> 00032 #include <net-snmp/library/container_binary_array.h> 00033 #include <net-snmp/library/tools.h> 00034 #include <net-snmp/library/snmp_assert.h> 00035 00036 typedef struct binary_array_table_s { 00037 size_t max_size; /* Size of the current data table */ 00038 size_t count; /* Index of the next free entry */ 00039 u_int flags; /* flags */ 00040 int dirty; 00041 int data_size; /* Size of an individual entry */ 00042 void **data; /* The table itself */ 00043 } binary_array_table; 00044 00045 typedef struct binary_array_iterator_s { 00046 netsnmp_iterator base; 00047 00048 size_t pos; 00049 } binary_array_iterator; 00050 00051 static netsnmp_iterator *_ba_iterator_get(netsnmp_container *c); 00052 00053 /********************************************************************** 00054 * 00055 * 00056 * 00057 */ 00058 static void 00059 array_qsort(void **data, int first, int last, netsnmp_container_compare *f) 00060 { 00061 int i, j; 00062 void *mid, *tmp; 00063 00064 i = first; 00065 j = last; 00066 mid = data[(first+last)/2]; 00067 00068 do { 00069 while ( ((*f)(data[i], mid) < 0) && (i < last)) 00070 ++i; 00071 while ( ((*f)(mid, data[j]) < 0) && (j > first)) 00072 --j; 00073 00074 if(i < j) { 00075 tmp = data[i]; 00076 data[i] = data[j]; 00077 data[j] = tmp; 00078 ++i; 00079 --j; 00080 } 00081 else if (i == j) { 00082 ++i; 00083 --j; 00084 break; 00085 } 00086 } while(i <= j); 00087 00088 if (j > first) 00089 array_qsort(data, first, j, f); 00090 00091 if (i < last) 00092 array_qsort(data, i, last, f); 00093 } 00094 00095 static int 00096 Sort_Array(netsnmp_container *c) 00097 { 00098 binary_array_table *t = (binary_array_table*)c->container_data; 00099 netsnmp_assert(t!=NULL); 00100 netsnmp_assert(c->compare!=NULL); 00101 00102 if (t->flags & CONTAINER_KEY_UNSORTED) 00103 return 0; 00104 00105 if (t->dirty) { 00106 /* 00107 * Sort the table 00108 */ 00109 if (t->count > 1) 00110 array_qsort(t->data, 0, t->count - 1, c->compare); 00111 t->dirty = 0; 00112 00113 ++c->sync; 00114 } 00115 00116 return 1; 00117 } 00118 00119 static int 00120 binary_search(const void *val, netsnmp_container *c, int exact) 00121 { 00122 binary_array_table *t = (binary_array_table*)c->container_data; 00123 size_t len = t->count; 00124 size_t half; 00125 size_t middle = 0; 00126 size_t first = 0; 00127 int result = 0; 00128 00129 if (!len) 00130 return -1; 00131 00132 if (t->dirty) 00133 Sort_Array(c); 00134 00135 while (len > 0) { 00136 half = len >> 1; 00137 middle = first; 00138 middle += half; 00139 if ((result = 00140 c->compare(t->data[middle], val)) < 0) { 00141 first = middle; 00142 ++first; 00143 len = len - half - 1; 00144 } else { 00145 if(result == 0) { 00146 first = middle; 00147 break; 00148 } 00149 len = half; 00150 } 00151 } 00152 00153 if (first >= t->count) 00154 return -1; 00155 00156 if(first != middle) { 00157 /* last compare wasn't against first, so get actual result */ 00158 result = c->compare(t->data[first], val); 00159 } 00160 00161 if(result == 0) { 00162 if (!exact) { 00163 if (++first == t->count) 00164 first = -1; 00165 } 00166 } 00167 else { 00168 if(exact) 00169 first = -1; 00170 } 00171 00172 return first; 00173 } 00174 00175 NETSNMP_STATIC_INLINE binary_array_table * 00176 netsnmp_binary_array_initialize(void) 00177 { 00178 binary_array_table *t; 00179 00180 t = SNMP_MALLOC_TYPEDEF(binary_array_table); 00181 if (t == NULL) 00182 return NULL; 00183 00184 t->max_size = 0; 00185 t->count = 0; 00186 t->dirty = 0; 00187 t->data_size = sizeof(void*); 00188 t->data = NULL; 00189 00190 return t; 00191 } 00192 00193 void 00194 netsnmp_binary_array_release(netsnmp_container *c) 00195 { 00196 binary_array_table *t = (binary_array_table*)c->container_data; 00197 if (t->data != NULL) { 00198 SNMP_FREE(t->data); 00199 } 00200 SNMP_FREE(t); 00201 SNMP_FREE(c); 00202 } 00203 00204 int 00205 netsnmp_binary_array_options_set(netsnmp_container *c, int set, u_int flags) 00206 { 00207 binary_array_table *t = (binary_array_table*)c->container_data; 00208 if (set) 00209 t->flags = flags; 00210 else 00211 return ((t->flags & flags) == flags); 00212 return flags; 00213 } 00214 00215 NETSNMP_STATIC_INLINE size_t 00216 netsnmp_binary_array_count(netsnmp_container *c) 00217 { 00218 binary_array_table *t = (binary_array_table*)c->container_data; 00219 /* 00220 * return count 00221 */ 00222 return t ? t->count : 0; 00223 } 00224 00225 NETSNMP_STATIC_INLINE void * 00226 netsnmp_binary_array_get(netsnmp_container *c, const void *key, int exact) 00227 { 00228 binary_array_table *t = (binary_array_table*)c->container_data; 00229 int index = 0; 00230 00231 /* 00232 * if there is no data, return NULL; 00233 */ 00234 if (!t->count) 00235 return NULL; 00236 00237 /* 00238 * if the table is dirty, sort it. 00239 */ 00240 if (t->dirty) 00241 Sort_Array(c); 00242 00243 /* 00244 * if there is a key, search. Otherwise default is 0; 00245 */ 00246 if (key) { 00247 if ((index = binary_search(key, c, exact)) == -1) 00248 return NULL; 00249 } 00250 00251 return t->data[index]; 00252 } 00253 00254 int 00255 netsnmp_binary_array_remove(netsnmp_container *c, const void *key, void **save) 00256 { 00257 binary_array_table *t = (binary_array_table*)c->container_data; 00258 size_t index = 0; 00259 00260 if (save) 00261 *save = NULL; 00262 00263 /* 00264 * if there is no data, return NULL; 00265 */ 00266 if (!t->count) 00267 return 0; 00268 00269 /* 00270 * if the table is dirty, sort it. 00271 */ 00272 if (t->dirty) 00273 Sort_Array(c); 00274 00275 /* 00276 * search 00277 */ 00278 if ((index = binary_search(key, c, 1)) == -1) 00279 return -1; 00280 00281 /* 00282 * find old data and save it, if ptr provided 00283 */ 00284 if (save) 00285 *save = t->data[index]; 00286 00287 /* 00288 * if entry was last item, just decrement count 00289 */ 00290 --t->count; 00291 if (index != t->count) { 00292 /* 00293 * otherwise, shift array down 00294 */ 00295 memmove(&t->data[index], &t->data[index+1], t->data_size * (t->count - index)); 00296 } 00297 00298 return 0; 00299 } 00300 00301 NETSNMP_STATIC_INLINE void 00302 netsnmp_binary_array_for_each(netsnmp_container *c, 00303 netsnmp_container_obj_func *fe, 00304 void *context, int sort) 00305 { 00306 binary_array_table *t = (binary_array_table*)c->container_data; 00307 size_t i; 00308 00309 if (sort && t->dirty) 00310 Sort_Array(c); 00311 00312 for (i = 0; i < t->count; ++i) 00313 (*fe) (t->data[i], context); 00314 } 00315 00316 NETSNMP_STATIC_INLINE void 00317 netsnmp_binary_array_clear(netsnmp_container *c, 00318 netsnmp_container_obj_func *fe, 00319 void *context) 00320 { 00321 binary_array_table *t = (binary_array_table*)c->container_data; 00322 00323 if( NULL != fe ) { 00324 size_t i; 00325 00326 for (i = 0; i < t->count; ++i) 00327 (*fe) (t->data[i], context); 00328 } 00329 00330 t->count = 0; 00331 t->dirty = 0; 00332 ++c->sync; 00333 } 00334 00335 NETSNMP_STATIC_INLINE int 00336 netsnmp_binary_array_insert(netsnmp_container *c, const void *entry) 00337 { 00338 binary_array_table *t = (binary_array_table*)c->container_data; 00339 int new_max; 00340 void *new_data; /* Used for * a) extending the data table 00341 * * b) the next entry to use */ 00342 /* 00343 * check for duplicates 00344 */ 00345 if (! (t->flags & CONTAINER_KEY_ALLOW_DUPLICATES)) { 00346 new_data = netsnmp_binary_array_get(c, entry, 1); 00347 if (NULL != new_data) { 00348 DEBUGMSGTL(("container","not inserting duplicate key\n")); 00349 return -1; 00350 } 00351 } 00352 00353 /* 00354 * check if we need to resize the array 00355 */ 00356 if (t->max_size <= t->count) { 00357 /* 00358 * Table is full, so extend it to double the size 00359 */ 00360 new_max = 2 * t->max_size; 00361 if (new_max == 0) 00362 new_max = 10; /* Start with 10 entries */ 00363 00364 new_data = (void *) calloc(new_max, t->data_size); 00365 if (new_data == NULL) 00366 return -1; 00367 00368 if (t->data) { 00369 memcpy(new_data, t->data, t->max_size * t->data_size); 00370 SNMP_FREE(t->data); 00371 } 00372 t->data = (void**)new_data; 00373 t->max_size = new_max; 00374 } 00375 00376 /* 00377 * Insert the new entry into the data array 00378 */ 00379 t->data[t->count++] = (void *)entry; 00380 t->dirty = 1; 00381 return 0; 00382 } 00383 00384 /********************************************************************** 00385 * 00386 * Special case support for subsets 00387 * 00388 */ 00389 static int 00390 binary_search_for_start(netsnmp_index *val, netsnmp_container *c) 00391 { 00392 binary_array_table *t = (binary_array_table*)c->container_data; 00393 size_t len = t->count; 00394 size_t half; 00395 size_t middle; 00396 size_t first = 0; 00397 int result = 0; 00398 00399 if (!len) 00400 return -1; 00401 00402 if (t->dirty) 00403 Sort_Array(c); 00404 00405 while (len > 0) { 00406 half = len >> 1; 00407 middle = first; 00408 middle += half; 00409 if ((result = c->ncompare(t->data[middle], val)) < 0) { 00410 first = middle; 00411 ++first; 00412 len = len - half - 1; 00413 } else 00414 len = half; 00415 } 00416 00417 if ((first >= t->count) || 00418 c->ncompare(t->data[first], val) != 0) 00419 return -1; 00420 00421 return first; 00422 } 00423 00424 void ** 00425 netsnmp_binary_array_get_subset(netsnmp_container *c, void *key, int *len) 00426 { 00427 binary_array_table *t = (binary_array_table*)c->container_data; 00428 void **subset; 00429 int start, end; 00430 size_t i; 00431 00432 /* 00433 * if there is no data, return NULL; 00434 */ 00435 if (!t->count || !key) 00436 return NULL; 00437 00438 /* 00439 * if the table is dirty, sort it. 00440 */ 00441 if (t->dirty) 00442 Sort_Array(c); 00443 00444 /* 00445 * find matching items 00446 */ 00447 start = end = binary_search_for_start((netsnmp_index *)key, c); 00448 if (start == -1) 00449 return NULL; 00450 00451 for (i = start + 1; i < t->count; ++i) { 00452 if (0 != c->ncompare(t->data[i], key)) 00453 break; 00454 ++end; 00455 } 00456 00457 *len = end - start + 1; 00458 subset = (void **)malloc((*len) * t->data_size); 00459 if (subset) 00460 memcpy(subset, &t->data[start], t->data_size * (*len)); 00461 00462 return subset; 00463 } 00464 00465 /********************************************************************** 00466 * 00467 * container 00468 * 00469 */ 00470 static void * 00471 _ba_find(netsnmp_container *container, const void *data) 00472 { 00473 return netsnmp_binary_array_get(container, data, 1); 00474 } 00475 00476 static void * 00477 _ba_find_next(netsnmp_container *container, const void *data) 00478 { 00479 return netsnmp_binary_array_get(container, data, 0); 00480 } 00481 00482 static int 00483 _ba_insert(netsnmp_container *container, const void *data) 00484 { 00485 return netsnmp_binary_array_insert(container, data); 00486 } 00487 00488 static int 00489 _ba_remove(netsnmp_container *container, const void *data) 00490 { 00491 return netsnmp_binary_array_remove(container,data, NULL); 00492 } 00493 00494 static int 00495 _ba_free(netsnmp_container *container) 00496 { 00497 netsnmp_binary_array_release(container); 00498 return 0; 00499 } 00500 00501 static size_t 00502 _ba_size(netsnmp_container *container) 00503 { 00504 return netsnmp_binary_array_count(container); 00505 } 00506 00507 static void 00508 _ba_for_each(netsnmp_container *container, netsnmp_container_obj_func *f, 00509 void *context) 00510 { 00511 netsnmp_binary_array_for_each(container, f, context, 1); 00512 } 00513 00514 static void 00515 _ba_clear(netsnmp_container *container, netsnmp_container_obj_func *f, 00516 void *context) 00517 { 00518 netsnmp_binary_array_clear(container, f, context); 00519 } 00520 00521 static netsnmp_void_array * 00522 _ba_get_subset(netsnmp_container *container, void *data) 00523 { 00524 netsnmp_void_array * va; 00525 void ** rtn; 00526 int len; 00527 00528 rtn = netsnmp_binary_array_get_subset(container, data, &len); 00529 if ((NULL==rtn) || (len <=0)) 00530 return NULL; 00531 00532 va = SNMP_MALLOC_TYPEDEF(netsnmp_void_array); 00533 if (NULL==va) 00534 { 00535 free (rtn); 00536 return NULL; 00537 } 00538 00539 va->size = len; 00540 va->array = rtn; 00541 00542 return va; 00543 } 00544 00545 netsnmp_container * 00546 netsnmp_container_get_binary_array(void) 00547 { 00548 /* 00549 * allocate memory 00550 */ 00551 netsnmp_container *c = SNMP_MALLOC_TYPEDEF(netsnmp_container); 00552 if (NULL==c) { 00553 snmp_log(LOG_ERR, "couldn't allocate memory\n"); 00554 return NULL; 00555 } 00556 00557 c->container_data = netsnmp_binary_array_initialize(); 00558 00559 c->get_size = _ba_size; 00560 c->init = NULL; 00561 c->cfree = _ba_free; 00562 c->insert = _ba_insert; 00563 c->remove = _ba_remove; 00564 c->find = _ba_find; 00565 c->find_next = _ba_find_next; 00566 c->get_subset = _ba_get_subset; 00567 c->get_iterator = _ba_iterator_get; 00568 c->for_each = _ba_for_each; 00569 c->clear = _ba_clear; 00570 00571 return c; 00572 } 00573 00574 netsnmp_factory * 00575 netsnmp_container_get_binary_array_factory(void) 00576 { 00577 static netsnmp_factory f = { "binary_array", 00578 (netsnmp_factory_produce_f*) 00579 netsnmp_container_get_binary_array }; 00580 00581 return &f; 00582 } 00583 00584 void 00585 netsnmp_container_binary_array_init(void) 00586 { 00587 netsnmp_container_register("binary_array", 00588 netsnmp_container_get_binary_array_factory()); 00589 } 00590 00591 /********************************************************************** 00592 * 00593 * iterator 00594 * 00595 */ 00596 NETSNMP_STATIC_INLINE binary_array_table * 00597 _ba_it2cont(binary_array_iterator *it) 00598 { 00599 if(NULL == it) { 00600 netsnmp_assert(NULL != it); 00601 return NULL; 00602 } 00603 if(NULL == it->base.container) { 00604 netsnmp_assert(NULL != it->base.container); 00605 return NULL; 00606 } 00607 if(NULL == it->base.container->container_data) { 00608 netsnmp_assert(NULL != it->base.container->container_data); 00609 return NULL; 00610 } 00611 00612 return (binary_array_table*)(it->base.container->container_data); 00613 } 00614 00615 NETSNMP_STATIC_INLINE void * 00616 _ba_iterator_position(binary_array_iterator *it, size_t pos) 00617 { 00618 binary_array_table *t = _ba_it2cont(it); 00619 if (NULL == t) 00620 return t; /* msg already logged */ 00621 00622 if(it->base.container->sync != it->base.sync) { 00623 DEBUGMSGTL(("container:iterator", "out of sync\n")); 00624 return NULL; 00625 } 00626 00627 if(0 == t->count) { 00628 DEBUGMSGTL(("container:iterator", "empty\n")); 00629 return NULL; 00630 } 00631 else if(pos >= t->count) { 00632 DEBUGMSGTL(("container:iterator", "end of containter\n")); 00633 return NULL; 00634 } 00635 00636 return t->data[ pos ]; 00637 } 00638 00639 static void * 00640 _ba_iterator_curr(binary_array_iterator *it) 00641 { 00642 if(NULL == it) { 00643 netsnmp_assert(NULL != it); 00644 return NULL; 00645 } 00646 00647 return _ba_iterator_position(it, it->pos); 00648 } 00649 00650 static void * 00651 _ba_iterator_first(binary_array_iterator *it) 00652 { 00653 return _ba_iterator_position(it, 0); 00654 } 00655 00656 static void * 00657 _ba_iterator_next(binary_array_iterator *it) 00658 { 00659 if(NULL == it) { 00660 netsnmp_assert(NULL != it); 00661 return NULL; 00662 } 00663 00664 ++it->pos; 00665 00666 return _ba_iterator_position(it, it->pos); 00667 } 00668 00669 static void * 00670 _ba_iterator_last(binary_array_iterator *it) 00671 { 00672 binary_array_table* t = _ba_it2cont(it); 00673 if(NULL == t) { 00674 netsnmp_assert(NULL != t); 00675 return NULL; 00676 } 00677 00678 return _ba_iterator_position(it, t->count - 1 ); 00679 } 00680 00681 static int 00682 _ba_iterator_reset(binary_array_iterator *it) 00683 { 00684 binary_array_table* t = _ba_it2cont(it); 00685 if(NULL == t) { 00686 netsnmp_assert(NULL != t); 00687 return -1; 00688 } 00689 00690 if (t->dirty) 00691 Sort_Array(it->base.container); 00692 00693 /* 00694 * save sync count, to make sure container doesn't change while 00695 * iterator is in use. 00696 */ 00697 it->base.sync = it->base.container->sync; 00698 00699 it->pos = 0; 00700 00701 return 0; 00702 } 00703 00704 static int 00705 _ba_iterator_release(netsnmp_iterator *it) 00706 { 00707 free(it); 00708 00709 return 0; 00710 } 00711 00712 static netsnmp_iterator * 00713 _ba_iterator_get(netsnmp_container *c) 00714 { 00715 binary_array_iterator* it; 00716 00717 if(NULL == c) 00718 return NULL; 00719 00720 it = SNMP_MALLOC_TYPEDEF(binary_array_iterator); 00721 if(NULL == it) 00722 return NULL; 00723 00724 it->base.container = c; 00725 00726 it->base.first = (netsnmp_iterator_rtn*)_ba_iterator_first; 00727 it->base.next = (netsnmp_iterator_rtn*)_ba_iterator_next; 00728 it->base.curr = (netsnmp_iterator_rtn*)_ba_iterator_curr; 00729 it->base.last = (netsnmp_iterator_rtn*)_ba_iterator_last; 00730 it->base.reset = (netsnmp_iterator_rc*)_ba_iterator_reset; 00731 it->base.release = (netsnmp_iterator_rc*)_ba_iterator_release; 00732 00733 (void)_ba_iterator_reset(it); 00734 00735 return (netsnmp_iterator *)it; 00736 }
Last modified: Wednesday, 01-Aug-2018 04:41:28 UTC
For questions regarding web content and site functionality, please write to the net-snmp-users mail list.