net-snmp 5.7
|
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 */