00001
00002
00003
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;
00040 sl_node *head;
00041
00042 int unsorted;
00043 int 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
00057
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
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 int
00089 _ssll_free(netsnmp_container *c)
00090 {
00091 if(c) {
00092 free(c);
00093 }
00094 return 0;
00095 }
00096
00097 static void *
00098 _ssll_find(netsnmp_container *c, const void *data)
00099 {
00100 if((NULL == c) || (NULL == data))
00101 return NULL;
00102
00103 return _get(c, data, 1);
00104 }
00105
00106 static void *
00107 _ssll_find_next(netsnmp_container *c, const void *data)
00108 {
00109 if(NULL == c)
00110 return NULL;
00111
00112 return _get(c, data, 0);
00113 }
00114
00115 static int
00116 _ssll_insert(netsnmp_container *c, const void *data)
00117 {
00118 sl_container *sl = (sl_container*)c;
00119 sl_node *new_node, *curr = sl->head;
00120
00121 if(NULL == c)
00122 return -1;
00123
00124 new_node = SNMP_MALLOC_TYPEDEF(sl_node);
00125 if(NULL == new_node)
00126 return -1;
00127 new_node->data = (void *)data;
00128 ++sl->count;
00129
00130
00131
00132
00133 if(NULL == sl->head) {
00134 sl->head = new_node;
00135 return 0;
00136 }
00137
00138
00139
00140
00141 if (1 == sl->unsorted) {
00142
00143
00144
00145 if (1 == sl->fifo) {
00146
00147
00148
00149 while(NULL != curr->next)
00150 curr = curr->next;
00151 curr->next = new_node;
00152 }
00153 else {
00154
00155
00156
00157 new_node->next = sl->head;
00158 sl->head = new_node;
00159 }
00160 }
00161 else {
00162
00163
00164
00165 sl_node *last = NULL;
00166 for( ; curr; last = curr, curr = curr->next) {
00167 if(sl->c.compare(curr->data, data) > 0)
00168 break;
00169 }
00170 if(NULL == last) {
00171 new_node->next = sl->head;
00172 sl->head = new_node;
00173 }
00174 else {
00175 new_node->next = last->next;
00176 last->next = new_node;
00177 }
00178 }
00179
00180 return 0;
00181 }
00182
00183 static int
00184 _ssll_remove(netsnmp_container *c, const void *data)
00185 {
00186 sl_container *sl = (sl_container*)c;
00187 sl_node *curr = sl->head;
00188
00189 if((NULL == c) || (NULL == curr))
00190 return -1;
00191
00192
00193
00194
00195 if ((NULL == data) ||
00196 (sl->c.compare(sl->head->data, data) == 0)) {
00197 curr = sl->head;
00198 sl->head = sl->head->next;
00199 }
00200 else {
00201 sl_node *last = sl->head;
00202 int rc;
00203 for(curr = sl->head->next ; curr; last = curr, curr = curr->next) {
00204 rc = sl->c.compare(curr->data, data);
00205 if (rc == 0) {
00206 last->next = curr->next;
00207 break;
00208 }
00209 else if ((rc > 0) && (0 == sl->unsorted)) {
00210
00211
00212
00213 curr = NULL;
00214 break;
00215 }
00216 }
00217 }
00218
00219 if(NULL == curr)
00220 return -2;
00221
00222
00223
00224
00225 free(curr);
00226 --sl->count;
00227
00228 return 0;
00229 }
00230
00231 static size_t
00232 _ssll_size(netsnmp_container *c)
00233 {
00234 sl_container *sl = (sl_container*)c;
00235
00236 if(NULL == c)
00237 return 0;
00238
00239 return sl->count;
00240 }
00241
00242 static void
00243 _ssll_for_each(netsnmp_container *c, netsnmp_container_obj_func *f,
00244 void *context)
00245 {
00246 sl_container *sl = (sl_container*)c;
00247 sl_node *curr;
00248
00249 if(NULL == c)
00250 return;
00251
00252 for(curr = sl->head; curr; curr = curr->next)
00253 (*f) ((void *)curr->data, context);
00254 }
00255
00256 static void
00257 _ssll_clear(netsnmp_container *c, netsnmp_container_obj_func *f,
00258 void *context)
00259 {
00260 sl_container *sl = (sl_container*)c;
00261 sl_node *curr, *next;
00262
00263 if(NULL == c)
00264 return;
00265
00266 for(curr = sl->head; curr; curr = next) {
00267
00268 next = curr->next;
00269
00270 if( NULL != f ) {
00271 curr->next = NULL;
00272 (*f) ((void *)curr->data, context);
00273 }
00274
00275
00276
00277
00278 free(curr);
00279 }
00280 sl->head = NULL;
00281 sl->count = 0;
00282 }
00283
00284
00285
00286
00287
00288
00289 netsnmp_container *
00290 netsnmp_container_get_ssll(void)
00291 {
00292
00293
00294
00295 sl_container *sl = SNMP_MALLOC_TYPEDEF(sl_container);
00296 if (NULL==sl) {
00297 snmp_log(LOG_ERR, "couldn't allocate memory\n");
00298 return NULL;
00299 }
00300
00301 sl->c.cfree = (netsnmp_container_rc*)_ssll_free;
00302
00303 sl->c.get_size = _ssll_size;
00304 sl->c.init = NULL;
00305 sl->c.insert = _ssll_insert;
00306 sl->c.remove = _ssll_remove;
00307 sl->c.find = _ssll_find;
00308 sl->c.find_next = _ssll_find_next;
00309 sl->c.get_subset = NULL;
00310 sl->c.get_iterator = NULL;
00311 sl->c.for_each = _ssll_for_each;
00312 sl->c.clear = _ssll_clear;
00313
00314
00315 return (netsnmp_container*)sl;
00316 }
00317
00318 netsnmp_factory *
00319 netsnmp_container_get_ssll_factory(void)
00320 {
00321 static netsnmp_factory f = {"sorted_singly_linked_list",
00322 (netsnmp_factory_produce_f*)
00323 netsnmp_container_get_ssll };
00324
00325 return &f;
00326 }
00327
00328
00329 netsnmp_container *
00330 netsnmp_container_get_usll(void)
00331 {
00332
00333
00334
00335 sl_container *sl = (sl_container *)netsnmp_container_get_ssll();
00336 if (NULL==sl)
00337 return NULL;
00338
00339 sl->unsorted = 1;
00340
00341 return (netsnmp_container*)sl;
00342 }
00343
00344 netsnmp_container *
00345 netsnmp_container_get_singly_linked_list(int fifo)
00346 {
00347 sl_container *sl = (sl_container *)netsnmp_container_get_usll();
00348 if (NULL == sl)
00349 return NULL;
00350
00351 sl->fifo = fifo;
00352
00353 return (netsnmp_container *)sl;
00354 }
00355
00356 netsnmp_container *
00357 netsnmp_container_get_fifo(void)
00358 {
00359 return netsnmp_container_get_singly_linked_list(1);
00360 }
00361
00362 netsnmp_factory *
00363 netsnmp_container_get_usll_factory(void)
00364 {
00365 static netsnmp_factory f = {"unsorted_singly_linked_list-lifo",
00366 (netsnmp_factory_produce_f*)
00367 netsnmp_container_get_usll };
00368
00369 return &f;
00370 }
00371
00372 netsnmp_factory *
00373 netsnmp_container_get_fifo_factory(void)
00374 {
00375 static netsnmp_factory f = {"unsorted_singly_linked_list-fifo",
00376 (netsnmp_factory_produce_f*)
00377 netsnmp_container_get_fifo };
00378
00379 return &f;
00380 }
00381
00382 void
00383 netsnmp_container_ssll_init(void)
00384 {
00385 netsnmp_container_register("sorted_singly_linked_list",
00386 netsnmp_container_get_ssll_factory());
00387 netsnmp_container_register("unsorted_singly_linked_list",
00388 netsnmp_container_get_usll_factory());
00389 netsnmp_container_register("lifo",
00390 netsnmp_container_get_usll_factory());
00391 netsnmp_container_register("fifo",
00392 netsnmp_container_get_fifo_factory());
00393 }
00394