net-snmp
5.4.1
|
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