net-snmp  5.4.1
container_list_ssll.c
00001 /*
00002  * container_list_sl.c
00003  * $Id: container_list_ssll.c 11048 2004-09-09 10:43:40Z slif $
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 
00048 static void *
00049 _get(netsnmp_container *c, const void *key, int exact)
00050 {
00051     sl_container *sl = (sl_container*)c;
00052     sl_node  *curr = sl->head;
00053     int rc = 0;
00054     
00055     /*
00056      * note: get-next on unsorted list is meaningless. we
00057      * don't try to search whole array, looking for the next highest.
00058      */
00059     if( (NULL != curr) && (NULL != key)) {
00060         while (curr) {
00061             rc = sl->c.compare(curr->data, key);
00062             if (rc == 0)
00063                 break;
00064             else if (rc > 0) {
00065                 if (0 == sl->unsorted) {
00066                     /*
00067                      * if sorted, we can stop.
00068                      */
00069                     break;
00070                 }
00071             }
00072             curr = curr->next;
00073         }
00074         
00075         if((curr) && (!exact) && (rc == 0)) {
00076             curr = curr->next;
00077         }
00078     }
00079     
00080     return curr ? curr->data : NULL;
00081 }
00082 
00083 /**********************************************************************
00084  *
00085  *
00086  *
00087  **********************************************************************/
00088 static void
00089 _ssll_free(netsnmp_container *c)
00090 {
00091     if(c) {
00092         free(c);
00093     }
00094 }
00095 
00096 static void *
00097 _ssll_find(netsnmp_container *c, const void *data)
00098 {
00099     if((NULL == c) || (NULL == data))
00100         return NULL;
00101 
00102     return _get(c, data, 1);
00103 }
00104 
00105 static void *
00106 _ssll_find_next(netsnmp_container *c, const void *data)
00107 {
00108     if(NULL == c)
00109         return NULL;
00110 
00111     return _get(c, data, 0);
00112 }
00113 
00114 static int
00115 _ssll_insert(netsnmp_container *c, const void *data)
00116 {
00117     sl_container *sl = (sl_container*)c;
00118     sl_node  *new_node, *curr = sl->head;
00119     
00120     if(NULL == c)
00121         return -1;
00122     
00123     new_node = SNMP_MALLOC_TYPEDEF(sl_node);
00124     if(NULL == new_node)
00125         return -1;
00126     new_node->data = (void *)data;
00127     ++sl->count;
00128 
00129     /*
00130      * first node?
00131      */
00132     if(NULL == sl->head) {
00133         sl->head = new_node;
00134         return 0;
00135     }
00136 
00137     /*
00138      * sorted or unsorted insert?
00139      */
00140     if (1 == sl->unsorted) {
00141         /*
00142          * unsorted: fifo, or lifo?
00143          */
00144         if (1 == sl->fifo) {
00145             /*
00146              * fifo: insert at tail
00147              */
00148             while(NULL != curr->next)
00149                 curr = curr->next;
00150             curr->next = new_node;
00151         }
00152         else {
00153             /*
00154              * lifo: insert at head
00155              */
00156             new_node->next = sl->head;
00157             sl->head = new_node;
00158         }
00159     }
00160     else {
00161         /*
00162          * sorted
00163          */
00164         sl_node *last = NULL;
00165         for( ; curr; last = curr, curr = curr->next) {
00166             if(sl->c.compare(curr->data, data) > 0)
00167                 break;
00168         }
00169         if(NULL == last) {
00170             new_node->next = sl->head;
00171             sl->head = new_node;
00172         }
00173         else {
00174             new_node->next = last->next;
00175             last->next = new_node;
00176         }
00177     }
00178     
00179     return 0;
00180 }
00181 
00182 static int
00183 _ssll_remove(netsnmp_container *c, const void *data)
00184 {
00185     sl_container *sl = (sl_container*)c;
00186     sl_node  *curr = sl->head;
00187     
00188     if((NULL == c) || (NULL == curr))
00189         return -1;
00190     
00191     /*
00192      * special case for NULL data, act like stack
00193      */
00194     if ((NULL == data) ||
00195         (sl->c.compare(sl->head->data, data) == 0)) {
00196         curr = sl->head;
00197         sl->head = sl->head->next;
00198     }
00199     else {
00200         sl_node *last = sl->head;
00201         int rc;
00202         for(curr = sl->head->next ; curr; last = curr, curr = curr->next) {
00203             rc = sl->c.compare(curr->data, data);
00204             if (rc == 0) {
00205                 last->next = curr->next;
00206                 break;
00207             }
00208             else if ((rc > 0) && (0 == sl->unsorted)) {
00209                 /*
00210                  * if sorted and rc > 0, didn't find entry
00211                  */
00212                 curr = NULL;
00213                 break;
00214             }
00215         }
00216     }
00217 
00218     if(NULL == curr)
00219         return -2;
00220     
00221     /*
00222      * free our node structure, but not the data
00223      */
00224     free(curr);
00225     --sl->count;
00226     
00227     return 0;
00228 }
00229 
00230 static size_t
00231 _ssll_size(netsnmp_container *c)
00232 {
00233     sl_container *sl = (sl_container*)c;
00234     
00235     if(NULL == c)
00236         return 0;
00237 
00238     return sl->count;
00239 }
00240 
00241 static void
00242 _ssll_for_each(netsnmp_container *c, netsnmp_container_obj_func *f,
00243              void *context)
00244 {
00245     sl_container *sl = (sl_container*)c;
00246     sl_node  *curr;
00247     
00248     if(NULL == c)
00249         return;
00250     
00251     for(curr = sl->head; curr; curr = curr->next)
00252         (*f) ((void *)curr->data, context);
00253 }
00254 
00255 static void
00256 _ssll_clear(netsnmp_container *c, netsnmp_container_obj_func *f,
00257              void *context)
00258 {
00259     sl_container *sl = (sl_container*)c;
00260     sl_node  *curr, *next;
00261     
00262     if(NULL == c)
00263         return;
00264     
00265     for(curr = sl->head; curr; curr = next) {
00266 
00267         next = curr->next;
00268 
00269         if( NULL != f ) {
00270             curr->next = NULL;
00271             (*f) ((void *)curr->data, context);
00272         }
00273 
00274         /*
00275          * free our node structure, but not the data
00276          */
00277         free(curr);
00278     }
00279     sl->head = NULL;
00280     sl->count = 0;
00281 }
00282 
00283 /**********************************************************************
00284  *
00285  *
00286  *
00287  **********************************************************************/
00288 netsnmp_container *
00289 netsnmp_container_get_ssll(void)
00290 {
00291     /*
00292      * allocate memory
00293      */
00294     sl_container *sl = SNMP_MALLOC_TYPEDEF(sl_container);
00295     if (NULL==sl) {
00296         snmp_log(LOG_ERR, "couldn't allocate memory\n");
00297         return NULL;
00298     }
00299 
00300     sl->c.cfree = (netsnmp_container_rc*)_ssll_free;
00301         
00302     sl->c.get_size = _ssll_size;
00303     sl->c.init = NULL;
00304     sl->c.insert = _ssll_insert;
00305     sl->c.remove = _ssll_remove;
00306     sl->c.find = _ssll_find;
00307     sl->c.find_next = _ssll_find_next;
00308     sl->c.get_subset = NULL;
00309     sl->c.get_iterator = NULL;
00310     sl->c.for_each = _ssll_for_each;
00311     sl->c.clear = _ssll_clear;
00312 
00313        
00314     return (netsnmp_container*)sl;
00315 }
00316 
00317 netsnmp_factory *
00318 netsnmp_container_get_ssll_factory(void)
00319 {
00320     static netsnmp_factory f = {"sorted_singly_linked_list",
00321                                 (netsnmp_factory_produce_f*)
00322                                 netsnmp_container_get_ssll };
00323     
00324     return &f;
00325 }
00326 
00327 
00328 netsnmp_container *
00329 netsnmp_container_get_usll(void)
00330 {
00331     /*
00332      * allocate memory
00333      */
00334     sl_container *sl = (sl_container *)netsnmp_container_get_ssll();
00335     if (NULL==sl)
00336         return NULL; /* msg already logged */
00337 
00338     sl->unsorted = 1;
00339 
00340     return (netsnmp_container*)sl;
00341 }
00342 
00343 netsnmp_container *
00344 netsnmp_container_get_singly_linked_list(int fifo)
00345 {
00346     sl_container *sl = (sl_container *)netsnmp_container_get_usll();
00347     if (NULL == sl)
00348         return NULL; /* error already logged */
00349 
00350     sl->fifo = fifo;
00351 
00352     return (netsnmp_container *)sl;
00353 }
00354 
00355 netsnmp_container *
00356 netsnmp_container_get_fifo(void)
00357 {
00358     return netsnmp_container_get_singly_linked_list(1);
00359 }
00360 
00361 netsnmp_factory *
00362 netsnmp_container_get_usll_factory(void)
00363 {
00364     static netsnmp_factory f = {"unsorted_singly_linked_list-lifo",
00365                                 (netsnmp_factory_produce_f*)
00366                                 netsnmp_container_get_usll };
00367     
00368     return &f;
00369 }
00370 
00371 netsnmp_factory *
00372 netsnmp_container_get_fifo_factory(void)
00373 {
00374     static netsnmp_factory f = {"unsorted_singly_linked_list-fifo",
00375                                 (netsnmp_factory_produce_f*)
00376                                 netsnmp_container_get_fifo };
00377     
00378     return &f;
00379 }
00380 
00381 void
00382 netsnmp_container_ssll_init(void)
00383 {
00384     netsnmp_container_register("sorted_singly_linked_list",
00385                                netsnmp_container_get_ssll_factory());
00386     netsnmp_container_register("unsorted_singly_linked_list",
00387                                netsnmp_container_get_usll_factory());
00388     netsnmp_container_register("lifo",
00389                                netsnmp_container_get_usll_factory());
00390     netsnmp_container_register("fifo",
00391                                netsnmp_container_get_fifo_factory());
00392 }
00393