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