00001
00002
00003
00004
00005
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;
00038 size_t count;
00039 u_int flags;
00040 int dirty;
00041 int data_size;
00042 void **data;
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
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
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
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
00233
00234 if (!t->count)
00235 return 0;
00236
00237
00238
00239
00240 if (t->dirty)
00241 Sort_Array(c);
00242
00243
00244
00245
00246 if (key) {
00247 if ((index = binary_search(key, c, exact)) == -1)
00248 return 0;
00249 }
00250
00251 return t->data[index];
00252 }
00253
00254 NETSNMP_STATIC_INLINE int
00255 netsnmp_binary_array_replace(netsnmp_container *c, void *entry)
00256 {
00257 binary_array_table *t = (binary_array_table*)c->container_data;
00258 int index = 0;
00259
00260
00261
00262
00263 if (!t->count)
00264 return 0;
00265
00266
00267
00268
00269 if (t->dirty)
00270 Sort_Array(c);
00271
00272
00273
00274
00275 if ((index = binary_search(entry, c, 1)) == -1)
00276 return 0;
00277
00278 t->data[index] = entry;
00279
00280 return 0;
00281 }
00282
00283 int
00284 netsnmp_binary_array_remove(netsnmp_container *c, const void *key, void **save)
00285 {
00286 binary_array_table *t = (binary_array_table*)c->container_data;
00287 size_t index = 0;
00288
00289 if (save)
00290 *save = NULL;
00291
00292
00293
00294
00295 if (!t->count)
00296 return 0;
00297
00298
00299
00300
00301 if (t->dirty)
00302 Sort_Array(c);
00303
00304
00305
00306
00307 if ((index = binary_search(key, c, 1)) == -1)
00308 return -1;
00309
00310
00311
00312
00313 if (save)
00314 *save = t->data[index];
00315
00316
00317
00318
00319 --t->count;
00320 if (index != t->count) {
00321
00322
00323
00324 memmove(&t->data[index], &t->data[index+1], t->data_size * (t->count - index));
00325 }
00326
00327 return 0;
00328 }
00329
00330 NETSNMP_STATIC_INLINE void
00331 netsnmp_binary_array_for_each(netsnmp_container *c,
00332 netsnmp_container_obj_func *fe,
00333 void *context, int sort)
00334 {
00335 binary_array_table *t = (binary_array_table*)c->container_data;
00336 size_t i;
00337
00338 if (sort && t->dirty)
00339 Sort_Array(c);
00340
00341 for (i = 0; i < t->count; ++i)
00342 (*fe) (t->data[i], context);
00343 }
00344
00345 NETSNMP_STATIC_INLINE void
00346 netsnmp_binary_array_clear(netsnmp_container *c,
00347 netsnmp_container_obj_func *fe,
00348 void *context)
00349 {
00350 binary_array_table *t = (binary_array_table*)c->container_data;
00351
00352 if( NULL != fe ) {
00353 size_t i;
00354
00355 for (i = 0; i < t->count; ++i)
00356 (*fe) (t->data[i], context);
00357 }
00358
00359 t->count = 0;
00360 t->dirty = 0;
00361 ++c->sync;
00362 }
00363
00364 NETSNMP_STATIC_INLINE int
00365 netsnmp_binary_array_insert(netsnmp_container *c, const void *entry)
00366 {
00367 binary_array_table *t = (binary_array_table*)c->container_data;
00368 int new_max;
00369 void *new_data;
00370
00371
00372
00373
00374 if (! (t->flags & CONTAINER_KEY_ALLOW_DUPLICATES)) {
00375 new_data = netsnmp_binary_array_get(c, entry, 1);
00376 if (NULL != new_data) {
00377 DEBUGMSGTL(("container","not inserting duplicate key\n"));
00378 return -1;
00379 }
00380 }
00381
00382
00383
00384
00385 if (t->max_size <= t->count) {
00386
00387
00388
00389 new_max = 2 * t->max_size;
00390 if (new_max == 0)
00391 new_max = 10;
00392
00393 new_data = (void *) calloc(new_max, t->data_size);
00394 if (new_data == NULL)
00395 return -1;
00396
00397 if (t->data) {
00398 memcpy(new_data, t->data, t->max_size * t->data_size);
00399 SNMP_FREE(t->data);
00400 }
00401 t->data = new_data;
00402 t->max_size = new_max;
00403 }
00404
00405
00406
00407
00408 t->data[t->count++] = entry;
00409 t->dirty = 1;
00410 return 0;
00411 }
00412
00413 NETSNMP_STATIC_INLINE void *
00414 netsnmp_binary_array_retrieve(netsnmp_container *c, int *max_oids, int sort)
00415 {
00416 binary_array_table *t = (binary_array_table*)c->container_data;
00417 if (sort && t->dirty)
00418 Sort_Array(c);
00419
00420 *max_oids = t->count;
00421 return t->data;
00422 }
00423
00424
00425
00426
00427
00428
00429 static int
00430 binary_search_for_start(netsnmp_index *val, netsnmp_container *c)
00431 {
00432 binary_array_table *t = (binary_array_table*)c->container_data;
00433 size_t len = t->count;
00434 size_t half;
00435 size_t middle;
00436 size_t first = 0;
00437 int result = 0;
00438
00439 if (!len)
00440 return -1;
00441
00442 if (t->dirty)
00443 Sort_Array(c);
00444
00445 while (len > 0) {
00446 half = len >> 1;
00447 middle = first;
00448 middle += half;
00449 if ((result = c->ncompare(t->data[middle], val)) < 0) {
00450 first = middle;
00451 ++first;
00452 len = len - half - 1;
00453 } else
00454 len = half;
00455 }
00456
00457 if ((first >= t->count) ||
00458 c->ncompare(t->data[first], val) != 0)
00459 return -1;
00460
00461 return first;
00462 }
00463
00464 void **
00465 netsnmp_binary_array_get_subset(netsnmp_container *c, void *key, int *len)
00466 {
00467 binary_array_table *t = (binary_array_table*)c->container_data;
00468 void **subset;
00469 int start, end;
00470 size_t i;
00471
00472
00473
00474
00475 if (!t->count || !key)
00476 return 0;
00477
00478
00479
00480
00481 if (t->dirty)
00482 Sort_Array(c);
00483
00484
00485
00486
00487 start = end = binary_search_for_start(key, c);
00488 if (start == -1)
00489 return 0;
00490
00491 for (i = start + 1; i < t->count; ++i) {
00492 if (0 != c->ncompare(t->data[i], key))
00493 break;
00494 ++end;
00495 }
00496
00497 *len = end - start + 1;
00498 subset = malloc((*len) * t->data_size);
00499 if (subset)
00500 memcpy(subset, &t->data[start], t->data_size * (*len));
00501
00502 return subset;
00503 }
00504
00505
00506
00507
00508
00509
00510 static void *
00511 _ba_find(netsnmp_container *container, const void *data)
00512 {
00513 return netsnmp_binary_array_get(container, data, 1);
00514 }
00515
00516 static void *
00517 _ba_find_next(netsnmp_container *container, const void *data)
00518 {
00519 return netsnmp_binary_array_get(container, data, 0);
00520 }
00521
00522 static int
00523 _ba_insert(netsnmp_container *container, const void *data)
00524 {
00525 return netsnmp_binary_array_insert(container, data);
00526 }
00527
00528 static int
00529 _ba_remove(netsnmp_container *container, const void *data)
00530 {
00531 return netsnmp_binary_array_remove(container,data, NULL);
00532 }
00533
00534 static int
00535 _ba_free(netsnmp_container *container)
00536 {
00537 netsnmp_binary_array_release(container);
00538 return 0;
00539 }
00540
00541 static size_t
00542 _ba_size(netsnmp_container *container)
00543 {
00544 return netsnmp_binary_array_count(container);
00545 }
00546
00547 static void
00548 _ba_for_each(netsnmp_container *container, netsnmp_container_obj_func *f,
00549 void *context)
00550 {
00551 netsnmp_binary_array_for_each(container, f, context, 1);
00552 }
00553
00554 static void
00555 _ba_clear(netsnmp_container *container, netsnmp_container_obj_func *f,
00556 void *context)
00557 {
00558 netsnmp_binary_array_clear(container, f, context);
00559 }
00560
00561 static netsnmp_void_array *
00562 _ba_get_subset(netsnmp_container *container, void *data)
00563 {
00564 netsnmp_void_array * va;
00565 void ** rtn;
00566 int len;
00567
00568 rtn = netsnmp_binary_array_get_subset(container, data, &len);
00569 if ((NULL==rtn) || (len <=0))
00570 return NULL;
00571
00572 va = SNMP_MALLOC_TYPEDEF(netsnmp_void_array);
00573 if (NULL==va)
00574 return NULL;
00575
00576 va->size = len;
00577 va->array = rtn;
00578
00579 return va;
00580 }
00581
00582 netsnmp_container *
00583 netsnmp_container_get_binary_array(void)
00584 {
00585
00586
00587
00588 netsnmp_container *c = SNMP_MALLOC_TYPEDEF(netsnmp_container);
00589 if (NULL==c) {
00590 snmp_log(LOG_ERR, "couldn't allocate memory\n");
00591 return NULL;
00592 }
00593
00594 c->container_data = netsnmp_binary_array_initialize();
00595
00596 c->get_size = _ba_size;
00597 c->init = NULL;
00598 c->cfree = _ba_free;
00599 c->insert = _ba_insert;
00600 c->remove = _ba_remove;
00601 c->find = _ba_find;
00602 c->find_next = _ba_find_next;
00603 c->get_subset = _ba_get_subset;
00604 c->get_iterator = _ba_iterator_get;
00605 c->for_each = _ba_for_each;
00606 c->clear = _ba_clear;
00607
00608 return c;
00609 }
00610
00611 netsnmp_factory *
00612 netsnmp_container_get_binary_array_factory(void)
00613 {
00614 static netsnmp_factory f = { "binary_array",
00615 (netsnmp_factory_produce_f*)
00616 netsnmp_container_get_binary_array };
00617
00618 return &f;
00619 }
00620
00621 void
00622 netsnmp_container_binary_array_init(void)
00623 {
00624 netsnmp_container_register("binary_array",
00625 netsnmp_container_get_binary_array_factory());
00626 }
00627
00628
00629
00630
00631
00632
00633 NETSNMP_STATIC_INLINE binary_array_table *
00634 _ba_it2cont(binary_array_iterator *it)
00635 {
00636 if(NULL == it) {
00637 netsnmp_assert(NULL != it);
00638 return NULL;
00639 }
00640 if(NULL == it->base.container) {
00641 netsnmp_assert(NULL != it->base.container);
00642 return NULL;
00643 }
00644 if(NULL == it->base.container->container_data) {
00645 netsnmp_assert(NULL != it->base.container->container_data);
00646 return NULL;
00647 }
00648
00649 return (binary_array_table*)(it->base.container->container_data);
00650 }
00651
00652 NETSNMP_STATIC_INLINE void *
00653 _ba_iterator_position(binary_array_iterator *it, size_t pos)
00654 {
00655 binary_array_table *t = _ba_it2cont(it);
00656 if (NULL == t)
00657 return t;
00658
00659 if(it->base.container->sync != it->base.sync) {
00660 DEBUGMSGTL(("container:iterator", "out of sync\n"));
00661 return NULL;
00662 }
00663
00664 if(0 == t->count) {
00665 DEBUGMSGTL(("container:iterator", "empty\n"));
00666 return NULL;
00667 }
00668 else if(pos >= t->count) {
00669 DEBUGMSGTL(("container:iterator", "end of containter\n"));
00670 return NULL;
00671 }
00672
00673 return t->data[ pos ];
00674 }
00675
00676 static void *
00677 _ba_iterator_curr(binary_array_iterator *it)
00678 {
00679 if(NULL == it) {
00680 netsnmp_assert(NULL != it);
00681 return NULL;
00682 }
00683
00684 return _ba_iterator_position(it, it->pos);
00685 }
00686
00687 static void *
00688 _ba_iterator_first(binary_array_iterator *it)
00689 {
00690 return _ba_iterator_position(it, 0);
00691 }
00692
00693 static void *
00694 _ba_iterator_next(binary_array_iterator *it)
00695 {
00696 if(NULL == it) {
00697 netsnmp_assert(NULL != it);
00698 return NULL;
00699 }
00700
00701 ++it->pos;
00702
00703 return _ba_iterator_position(it, it->pos);
00704 }
00705
00706 static void *
00707 _ba_iterator_last(binary_array_iterator *it)
00708 {
00709 binary_array_table* t = _ba_it2cont(it);
00710 if(NULL == t) {
00711 netsnmp_assert(NULL != t);
00712 return NULL;
00713 }
00714
00715 return _ba_iterator_position(it, t->count - 1 );
00716 }
00717
00718 static int
00719 _ba_iterator_reset(binary_array_iterator *it)
00720 {
00721 binary_array_table* t = _ba_it2cont(it);
00722 if(NULL == t) {
00723 netsnmp_assert(NULL != t);
00724 return -1;
00725 }
00726
00727 if (t->dirty)
00728 Sort_Array(it->base.container);
00729
00730
00731
00732
00733
00734 it->base.sync = it->base.container->sync;
00735
00736 it->pos = 0;
00737
00738 return 0;
00739 }
00740
00741 static int
00742 _ba_iterator_release(netsnmp_iterator *it)
00743 {
00744 free(it);
00745
00746 return 0;
00747 }
00748
00749 static netsnmp_iterator *
00750 _ba_iterator_get(netsnmp_container *c)
00751 {
00752 binary_array_iterator* it;
00753
00754 if(NULL == c)
00755 return NULL;
00756
00757 it = SNMP_MALLOC_TYPEDEF(binary_array_iterator);
00758 if(NULL == it)
00759 return NULL;
00760
00761 it->base.container = c;
00762
00763 it->base.first = (netsnmp_iterator_rtn*)_ba_iterator_first;
00764 it->base.next = (netsnmp_iterator_rtn*)_ba_iterator_next;
00765 it->base.curr = (netsnmp_iterator_rtn*)_ba_iterator_curr;
00766 it->base.last = (netsnmp_iterator_rtn*)_ba_iterator_last;
00767 it->base.reset = (netsnmp_iterator_rc*)_ba_iterator_reset;
00768 it->base.release = (netsnmp_iterator_rc*)_ba_iterator_release;
00769
00770 (void)_ba_iterator_reset(it);
00771
00772 return (netsnmp_iterator *)it;
00773 }