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