net-snmp  5.4.1
container_binary_array.c
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 }