container_list_ssll.c

00001 /*
00002  * container_list_sl.c
00003  * $Id$
00004  *
00005  */
00006 #include <net-snmp/net-snmp-config.h>
00007 
00008 #include <stdio.h>
00009 #if HAVE_STDLIB_H
00010 #include <stdlib.h>
00011 #endif
00012 #if HAVE_MALLOC_H
00013 #include <malloc.h>
00014 #endif
00015 #include <sys/types.h>
00016 #if HAVE_STRING_H
00017 #include <string.h>
00018 #else
00019 #include <strings.h>
00020 #endif
00021 
00022 #include <net-snmp/net-snmp-includes.h>
00023 #include <net-snmp/types.h>
00024 #include <net-snmp/library/snmp_api.h>
00025 #include <net-snmp/library/container.h>
00026 #include <net-snmp/library/tools.h>
00027 #include <net-snmp/library/snmp_assert.h>
00028 
00029 #include <net-snmp/library/container_list_ssll.h>
00030 
00031 typedef struct sl_node {
00032    void           *data;
00033    struct sl_node *next;
00034 } sl_node;
00035 
00036 typedef struct sl_container_s {
00037    netsnmp_container          c;
00038    
00039    size_t                     count;      /* Index of the next free entry */
00040    sl_node                   *head;       /* head of list */
00041 
00042    int                        unsorted;   /* unsorted list? */
00043    int                        fifo;       /* lifo or fifo? */
00044 
00045 } sl_container;
00046 
00047 typedef struct ssll_iterator_s {
00048     netsnmp_iterator base;
00049  
00050     sl_node         *pos;
00051     sl_node         *last;
00052 } ssll_iterator;
00053 
00054 static netsnmp_iterator *_ssll_iterator_get(netsnmp_container *c);
00055 
00056 
00057 static void *
00058 _get(netsnmp_container *c, const void *key, int exact)
00059 {
00060     sl_container *sl = (sl_container*)c;
00061     sl_node  *curr = sl->head;
00062     int rc = 0;
00063     
00064     /*
00065      * note: get-next on unsorted list is meaningless. we
00066      * don't try to search whole array, looking for the next highest.
00067      */
00068     if( (NULL != curr) && (NULL != key)) {
00069         while (curr) {
00070             rc = sl->c.compare(curr->data, key);
00071             if (rc == 0)
00072                 break;
00073             else if (rc > 0) {
00074                 if (0 == sl->unsorted) {
00075                     /*
00076                      * if sorted, we can stop.
00077                      */
00078                     break;
00079                 }
00080             }
00081             curr = curr->next;
00082         }
00083         
00084         if((curr) && (!exact) && (rc == 0)) {
00085             curr = curr->next;
00086         }
00087     }
00088     
00089     return curr ? curr->data : NULL;
00090 }
00091 
00092 /**********************************************************************
00093  *
00094  *
00095  *
00096  **********************************************************************/
00097 static int
00098 _ssll_free(netsnmp_container *c)
00099 {
00100     if(c) {
00101         free(c);
00102     }
00103     return 0;
00104 }
00105 
00106 static void *
00107 _ssll_find(netsnmp_container *c, const void *data)
00108 {
00109     if((NULL == c) || (NULL == data))
00110         return NULL;
00111 
00112     return _get(c, data, 1);
00113 }
00114 
00115 static void *
00116 _ssll_find_next(netsnmp_container *c, const void *data)
00117 {
00118     if(NULL == c)
00119         return NULL;
00120 
00121     return _get(c, data, 0);
00122 }
00123 
00124 static int
00125 _ssll_insert(netsnmp_container *c, const void *data)
00126 {
00127     sl_container *sl = (sl_container*)c;
00128     sl_node  *new_node, *curr = sl->head;
00129     
00130     if(NULL == c)
00131         return -1;
00132     
00133     new_node = SNMP_MALLOC_TYPEDEF(sl_node);
00134     if(NULL == new_node)
00135         return -1;
00136     new_node->data = (void *)data;
00137     ++sl->count;
00138     ++c->sync;
00139 
00140     /*
00141      * first node?
00142      */
00143     if(NULL == sl->head) {
00144         sl->head = new_node;
00145         return 0;
00146     }
00147 
00148     /*
00149      * sorted or unsorted insert?
00150      */
00151     if (1 == sl->unsorted) {
00152         /*
00153          * unsorted: fifo, or lifo?
00154          */
00155         if (1 == sl->fifo) {
00156             /*
00157              * fifo: insert at tail
00158              */
00159             while(NULL != curr->next)
00160                 curr = curr->next;
00161             curr->next = new_node;
00162         }
00163         else {
00164             /*
00165              * lifo: insert at head
00166              */
00167             new_node->next = sl->head;
00168             sl->head = new_node;
00169         }
00170     }
00171     else {
00172         /*
00173          * sorted
00174          */
00175         sl_node *last = NULL;
00176         for( ; curr; last = curr, curr = curr->next) {
00177             if(sl->c.compare(curr->data, data) > 0)
00178                 break;
00179         }
00180         if(NULL == last) {
00181             new_node->next = sl->head;
00182             sl->head = new_node;
00183         }
00184         else {
00185             new_node->next = last->next;
00186             last->next = new_node;
00187         }
00188     }
00189     
00190     return 0;
00191 }
00192 
00193 static int
00194 _ssll_remove(netsnmp_container *c, const void *data)
00195 {
00196     sl_container *sl = (sl_container*)c;
00197     sl_node  *curr = sl->head;
00198     
00199     if((NULL == c) || (NULL == curr))
00200         return -1;
00201     
00202     /*
00203      * special case for NULL data, act like stack
00204      */
00205     if ((NULL == data) ||
00206         (sl->c.compare(sl->head->data, data) == 0)) {
00207         curr = sl->head;
00208         sl->head = sl->head->next;
00209     }
00210     else {
00211         sl_node *last = sl->head;
00212         int rc;
00213         for(curr = sl->head->next ; curr; last = curr, curr = curr->next) {
00214             rc = sl->c.compare(curr->data, data);
00215             if (rc == 0) {
00216                 last->next = curr->next;
00217                 break;
00218             }
00219             else if ((rc > 0) && (0 == sl->unsorted)) {
00220                 /*
00221                  * if sorted and rc > 0, didn't find entry
00222                  */
00223                 curr = NULL;
00224                 break;
00225             }
00226         }
00227     }
00228 
00229     if(NULL == curr)
00230         return -2;
00231     
00232     /*
00233      * free our node structure, but not the data
00234      */
00235     free(curr);
00236     --sl->count;
00237     ++c->sync;
00238     
00239     return 0;
00240 }
00241 
00242 static size_t
00243 _ssll_size(netsnmp_container *c)
00244 {
00245     sl_container *sl = (sl_container*)c;
00246     
00247     if(NULL == c)
00248         return 0;
00249 
00250     return sl->count;
00251 }
00252 
00253 static void
00254 _ssll_for_each(netsnmp_container *c, netsnmp_container_obj_func *f,
00255              void *context)
00256 {
00257     sl_container *sl = (sl_container*)c;
00258     sl_node  *curr;
00259     
00260     if(NULL == c)
00261         return;
00262     
00263     for(curr = sl->head; curr; curr = curr->next)
00264         (*f) ((void *)curr->data, context);
00265 }
00266 
00267 static void
00268 _ssll_clear(netsnmp_container *c, netsnmp_container_obj_func *f,
00269              void *context)
00270 {
00271     sl_container *sl = (sl_container*)c;
00272     sl_node  *curr, *next;
00273     
00274     if(NULL == c)
00275         return;
00276     
00277     for(curr = sl->head; curr; curr = next) {
00278 
00279         next = curr->next;
00280 
00281         if( NULL != f ) {
00282             curr->next = NULL;
00283             (*f) ((void *)curr->data, context);
00284         }
00285 
00286         /*
00287          * free our node structure, but not the data
00288          */
00289         free(curr);
00290     }
00291     sl->head = NULL;
00292     sl->count = 0;
00293     ++c->sync;
00294 }
00295 
00296 /**********************************************************************
00297  *
00298  *
00299  *
00300  **********************************************************************/
00301 netsnmp_container *
00302 netsnmp_container_get_ssll(void)
00303 {
00304     /*
00305      * allocate memory
00306      */
00307     sl_container *sl = SNMP_MALLOC_TYPEDEF(sl_container);
00308     if (NULL==sl) {
00309         snmp_log(LOG_ERR, "couldn't allocate memory\n");
00310         return NULL;
00311     }
00312 
00313     sl->c.cfree = _ssll_free;
00314         
00315     sl->c.get_size = _ssll_size;
00316     sl->c.init = NULL;
00317     sl->c.insert = _ssll_insert;
00318     sl->c.remove = _ssll_remove;
00319     sl->c.find = _ssll_find;
00320     sl->c.find_next = _ssll_find_next;
00321     sl->c.get_subset = NULL;
00322     sl->c.get_iterator =_ssll_iterator_get;
00323     sl->c.for_each = _ssll_for_each;
00324     sl->c.clear = _ssll_clear;
00325 
00326        
00327     return (netsnmp_container*)sl;
00328 }
00329 
00330 netsnmp_factory *
00331 netsnmp_container_get_ssll_factory(void)
00332 {
00333     static netsnmp_factory f = {"sorted_singly_linked_list",
00334                                 (netsnmp_factory_produce_f*)
00335                                 netsnmp_container_get_ssll };
00336     
00337     return &f;
00338 }
00339 
00340 
00341 netsnmp_container *
00342 netsnmp_container_get_usll(void)
00343 {
00344     /*
00345      * allocate memory
00346      */
00347     sl_container *sl = (sl_container *)netsnmp_container_get_ssll();
00348     if (NULL==sl)
00349         return NULL; /* msg already logged */
00350 
00351     sl->unsorted = 1;
00352 
00353     return (netsnmp_container*)sl;
00354 }
00355 
00356 netsnmp_container *
00357 netsnmp_container_get_singly_linked_list(int fifo)
00358 {
00359     sl_container *sl = (sl_container *)netsnmp_container_get_usll();
00360     if (NULL == sl)
00361         return NULL; /* error already logged */
00362 
00363     sl->fifo = fifo;
00364 
00365     return (netsnmp_container *)sl;
00366 }
00367 
00368 netsnmp_container *
00369 netsnmp_container_get_fifo(void)
00370 {
00371     return netsnmp_container_get_singly_linked_list(1);
00372 }
00373 
00374 netsnmp_factory *
00375 netsnmp_container_get_usll_factory(void)
00376 {
00377     static netsnmp_factory f = {"unsorted_singly_linked_list-lifo",
00378                                 (netsnmp_factory_produce_f*)
00379                                 netsnmp_container_get_usll };
00380     
00381     return &f;
00382 }
00383 
00384 netsnmp_factory *
00385 netsnmp_container_get_fifo_factory(void)
00386 {
00387     static netsnmp_factory f = {"unsorted_singly_linked_list-fifo",
00388                                 (netsnmp_factory_produce_f*)
00389                                 netsnmp_container_get_fifo };
00390     
00391     return &f;
00392 }
00393 
00394 void
00395 netsnmp_container_ssll_init(void)
00396 {
00397     netsnmp_container_register("sorted_singly_linked_list",
00398                                netsnmp_container_get_ssll_factory());
00399     netsnmp_container_register("unsorted_singly_linked_list",
00400                                netsnmp_container_get_usll_factory());
00401     netsnmp_container_register("lifo",
00402                                netsnmp_container_get_usll_factory());
00403     netsnmp_container_register("fifo",
00404                                netsnmp_container_get_fifo_factory());
00405 }
00406 
00407 
00408 /**********************************************************************
00409  *
00410  * iterator
00411  *
00412  */
00413 NETSNMP_STATIC_INLINE sl_container *
00414 _ssll_it2cont(ssll_iterator *it)
00415 {
00416     if(NULL == it) {
00417         netsnmp_assert(NULL != it);
00418         return NULL;
00419     }
00420 
00421     if(NULL == it->base.container) {
00422         netsnmp_assert(NULL != it->base.container);
00423         return NULL;
00424     }
00425 
00426     if(it->base.container->sync != it->base.sync) {
00427         DEBUGMSGTL(("container:iterator", "out of sync\n"));
00428         return NULL;
00429     }
00430 
00431     return (sl_container *)it->base.container;
00432 }
00433 
00434 static void *
00435 _ssll_iterator_curr(ssll_iterator *it)
00436 {
00437     sl_container *t = _ssll_it2cont(it);
00438     if ((NULL == t) || (NULL == it->pos))
00439         return NULL;
00440 
00441     return it->pos->data;
00442 }
00443 
00444 static void *
00445 _ssll_iterator_first(ssll_iterator *it)
00446 {
00447     sl_container *t = _ssll_it2cont(it);
00448     if ((NULL == t) || (NULL == t->head))
00449         return NULL;
00450 
00451     return t->head->data;
00452 }
00453 
00454 static void *
00455 _ssll_iterator_next(ssll_iterator *it)
00456 {
00457     sl_container *t = _ssll_it2cont(it);
00458     if ((NULL == t) || (NULL == it->pos))
00459         return NULL;
00460 
00461     it->pos = it->pos->next;
00462     if (NULL == it->pos)
00463         return NULL;
00464 
00465     return it->pos->data;
00466 }
00467 
00468 static void *
00469 _ssll_iterator_last(ssll_iterator *it)
00470 {
00471     sl_node      *n;
00472     sl_container *t = _ssll_it2cont(it);
00473     if(NULL == t)
00474         return NULL;
00475     
00476     if (it->last)
00477         return it->last;
00478 
00479     n = it->pos ? it->pos : t->head;
00480     if (NULL == n)
00481         return NULL;
00482 
00483     while(n->next)
00484         n = n->next;
00485 
00486     if (NULL == n)
00487         return NULL;
00488 
00489     it->last = n;
00490 
00491     return it->last->data;
00492 }
00493 
00494 static int
00495 _ssll_iterator_reset(ssll_iterator *it)
00496 {
00497     sl_container *t;
00498 
00500     if(NULL == it) {
00501         netsnmp_assert(NULL != it);
00502         return 0;
00503     }
00504 
00505     if(NULL == it->base.container) {
00506         netsnmp_assert(NULL != it->base.container);
00507         return 0;
00508     }
00509     t = (sl_container *)it->base.container;
00510     if(NULL == t)
00511         return -1;
00512 
00513     it->last = NULL;
00514     it->pos = t->head;
00515 
00516     /*
00517      * save sync count, to make sure container doesn't change while
00518      * iterator is in use.
00519      */
00520     it->base.sync = it->base.container->sync;
00521 
00522     return 0;
00523 }
00524 
00525 static int
00526 _ssll_iterator_release(netsnmp_iterator *it)
00527 {
00528     free(it);
00529 
00530     return 0;
00531 }
00532 
00533 static netsnmp_iterator *
00534 _ssll_iterator_get(netsnmp_container *c)
00535 {
00536     ssll_iterator* it;
00537 
00538     if(NULL == c)
00539         return NULL;
00540 
00541     it = SNMP_MALLOC_TYPEDEF(ssll_iterator);
00542     if(NULL == it)
00543         return NULL;
00544 
00545     it->base.container = c;
00546     
00547     it->base.first = (netsnmp_iterator_rtn*)_ssll_iterator_first;
00548     it->base.next = (netsnmp_iterator_rtn*)_ssll_iterator_next;
00549     it->base.curr = (netsnmp_iterator_rtn*)_ssll_iterator_curr;
00550     it->base.last = (netsnmp_iterator_rtn*)_ssll_iterator_last;
00551     it->base.reset = (netsnmp_iterator_rc*)_ssll_iterator_reset;
00552     it->base.release = (netsnmp_iterator_rc*)_ssll_iterator_release;
00553 
00554     (void)_ssll_iterator_reset(it);
00555 
00556     return (netsnmp_iterator *)it;
00557 }