1 /*
2 * container_list_sl.c
3 * $Id$
4 *
5 */
6 #include <net-snmp/net-snmp-config.h>
7 #include <net-snmp/net-snmp-features.h>
8
9 #include <stdio.h>
10 #if HAVE_STDLIB_H
11 #include <stdlib.h>
12 #endif
13 #if HAVE_MALLOC_H
14 #include <malloc.h>
15 #endif
16 #include <sys/types.h>
17 #if HAVE_STRING_H
18 #include <string.h>
19 #else
20 #include <strings.h>
21 #endif
22
23 #include <net-snmp/net-snmp-includes.h>
24 #include <net-snmp/types.h>
25 #include <net-snmp/library/snmp_api.h>
26 #include <net-snmp/library/container.h>
27 #include <net-snmp/library/tools.h>
28 #include <net-snmp/library/snmp_assert.h>
29
30 #include <net-snmp/library/container_list_ssll.h>
31
32 netsnmp_feature_child_of(container_linked_list, container_types);
33 netsnmp_feature_child_of(container_fifo, container_types);
34 netsnmp_feature_child_of(container_lifo, container_types);
35
36 /* this is a fancy way of cleaning up ifdefs */
37 #ifdef NETSNMP_FEATURE_REQUIRE_CONTAINER_FIFO
38 netsnmp_feature_require(container_linked_list);
39 #endif /* NETSNMP_FEATURE_REQUIRE_CONTAINER_FIFO */
40 #ifdef NETSNMP_FEATURE_REQUIRE_CONTAINER_LIFO
41 netsnmp_feature_require(container_linked_list);
42 #endif /* NETSNMP_FEATURE_REQUIRE_CONTAINER_LIFO */
43
44 #ifndef NETSNMP_FEATURE_REMOVE_CONTAINER_LINKED_LIST
45 typedef struct sl_node {
46 void *data;
47 struct sl_node *next;
48 } sl_node;
49
50 typedef struct sl_container_s {
51 netsnmp_container c;
52
53 size_t count; /* Index of the next free entry */
54 sl_node *head; /* head of list */
55
56 int unsorted; /* unsorted list? */
57 int fifo; /* lifo or fifo? */
58
59 } sl_container;
60
61 typedef struct ssll_iterator_s {
62 netsnmp_iterator base;
63
64 sl_node *pos;
65 sl_node *last;
66 } ssll_iterator;
67
68 static netsnmp_iterator *_ssll_iterator_get(netsnmp_container *c);
69
70
71 static void *
_get(netsnmp_container * c,const void * key,int exact)72 _get(netsnmp_container *c, const void *key, int exact)
73 {
74 sl_container *sl = (sl_container*)c;
75 sl_node *curr = sl->head;
76 int rc = 0;
77
78 /*
79 * note: get-next on unsorted list is meaningless. we
80 * don't try to search whole array, looking for the next highest.
81 */
82 if( (NULL != curr) && (NULL != key)) {
83 while (curr) {
84 rc = sl->c.compare(curr->data, key);
85 if (rc == 0)
86 break;
87 else if (rc > 0) {
88 if (0 == sl->unsorted) {
89 /*
90 * if sorted, we can stop.
91 */
92 break;
93 }
94 }
95 curr = curr->next;
96 }
97
98 if((curr) && (!exact) && (rc == 0)) {
99 curr = curr->next;
100 }
101 }
102
103 return curr ? curr->data : NULL;
104 }
105
106 /**********************************************************************
107 *
108 *
109 *
110 **********************************************************************/
111 static int
_ssll_free(netsnmp_container * c)112 _ssll_free(netsnmp_container *c)
113 {
114 if(c) {
115 free(c);
116 }
117 return 0;
118 }
119
120 static void *
_ssll_find(netsnmp_container * c,const void * data)121 _ssll_find(netsnmp_container *c, const void *data)
122 {
123 if((NULL == c) || (NULL == data))
124 return NULL;
125
126 return _get(c, data, 1);
127 }
128
129 static void *
_ssll_find_next(netsnmp_container * c,const void * data)130 _ssll_find_next(netsnmp_container *c, const void *data)
131 {
132 if(NULL == c)
133 return NULL;
134
135 return _get(c, data, 0);
136 }
137
138 static int
_ssll_insert(netsnmp_container * c,const void * data)139 _ssll_insert(netsnmp_container *c, const void *data)
140 {
141 sl_container *sl = (sl_container*)c;
142 sl_node *new_node, *curr;
143
144 if (c == NULL)
145 return -1;
146
147 curr = sl->head;
148
149 new_node = SNMP_MALLOC_TYPEDEF(sl_node);
150 if (new_node == NULL)
151 return -1;
152 new_node->data = NETSNMP_REMOVE_CONST(void *, data);
153 ++sl->count;
154 ++c->sync;
155
156 /*
157 * first node?
158 */
159 if(NULL == sl->head) {
160 sl->head = new_node;
161 return 0;
162 }
163
164 /*
165 * sorted or unsorted insert?
166 */
167 if (1 == sl->unsorted) {
168 /*
169 * unsorted: fifo, or lifo?
170 */
171 if (1 == sl->fifo) {
172 /*
173 * fifo: insert at tail
174 */
175 while(NULL != curr->next)
176 curr = curr->next;
177 curr->next = new_node;
178 }
179 else {
180 /*
181 * lifo: insert at head
182 */
183 new_node->next = sl->head;
184 sl->head = new_node;
185 }
186 }
187 else {
188 /*
189 * sorted
190 */
191 sl_node *last = NULL;
192 for( ; curr; last = curr, curr = curr->next) {
193 if(sl->c.compare(curr->data, data) > 0)
194 break;
195 }
196 if(NULL == last) {
197 new_node->next = sl->head;
198 sl->head = new_node;
199 }
200 else {
201 new_node->next = last->next;
202 last->next = new_node;
203 }
204 }
205
206 return 0;
207 }
208
209 static int
_ssll_remove(netsnmp_container * c,const void * data)210 _ssll_remove(netsnmp_container *c, const void *data)
211 {
212 sl_container *sl = (sl_container*)c;
213 sl_node *curr;
214
215 if (c == NULL)
216 return -1;
217
218 curr = sl->head;
219 if (curr == NULL)
220 return -1;
221
222 /*
223 * special case for NULL data, act like stack
224 */
225 if ((NULL == data) ||
226 (sl->c.compare(sl->head->data, data) == 0)) {
227 curr = sl->head;
228 sl->head = sl->head->next;
229 }
230 else {
231 sl_node *last = sl->head;
232 int rc;
233 for(curr = sl->head->next ; curr; last = curr, curr = curr->next) {
234 rc = sl->c.compare(curr->data, data);
235 if (rc == 0) {
236 last->next = curr->next;
237 break;
238 }
239 else if ((rc > 0) && (0 == sl->unsorted)) {
240 /*
241 * if sorted and rc > 0, didn't find entry
242 */
243 curr = NULL;
244 break;
245 }
246 }
247 }
248
249 if(NULL == curr)
250 return -2;
251
252 /*
253 * free our node structure, but not the data
254 */
255 free(curr);
256 --sl->count;
257 ++c->sync;
258
259 return 0;
260 }
261
262 static size_t
_ssll_size(netsnmp_container * c)263 _ssll_size(netsnmp_container *c)
264 {
265 sl_container *sl = (sl_container*)c;
266
267 if(NULL == c)
268 return 0;
269
270 return sl->count;
271 }
272
273 static void
_ssll_for_each(netsnmp_container * c,netsnmp_container_obj_func * f,void * context)274 _ssll_for_each(netsnmp_container *c, netsnmp_container_obj_func *f,
275 void *context)
276 {
277 sl_container *sl = (sl_container*)c;
278 sl_node *curr;
279
280 if(NULL == c)
281 return;
282
283 for(curr = sl->head; curr; curr = curr->next)
284 (*f) ((void *)curr->data, context);
285 }
286
287 static void
_ssll_clear(netsnmp_container * c,netsnmp_container_obj_func * f,void * context)288 _ssll_clear(netsnmp_container *c, netsnmp_container_obj_func *f,
289 void *context)
290 {
291 sl_container *sl = (sl_container*)c;
292 sl_node *curr, *next;
293
294 if(NULL == c)
295 return;
296
297 for(curr = sl->head; curr; curr = next) {
298
299 next = curr->next;
300
301 if( NULL != f ) {
302 curr->next = NULL;
303 (*f) ((void *)curr->data, context);
304 }
305
306 /*
307 * free our node structure, but not the data
308 */
309 free(curr);
310 }
311 sl->head = NULL;
312 sl->count = 0;
313 ++c->sync;
314 }
315
316 /**********************************************************************
317 *
318 *
319 *
320 **********************************************************************/
321 netsnmp_container *
netsnmp_container_get_ssll(void)322 netsnmp_container_get_ssll(void)
323 {
324 /*
325 * allocate memory
326 */
327 sl_container *sl = SNMP_MALLOC_TYPEDEF(sl_container);
328 if (NULL==sl) {
329 snmp_log(LOG_ERR, "couldn't allocate memory\n");
330 return NULL;
331 }
332
333 netsnmp_init_container((netsnmp_container *)sl, NULL, _ssll_free,
334 _ssll_size, NULL, _ssll_insert, _ssll_remove,
335 _ssll_find);
336 sl->c.find_next = _ssll_find_next;
337 sl->c.get_subset = NULL;
338 sl->c.get_iterator =_ssll_iterator_get;
339 sl->c.for_each = _ssll_for_each;
340 sl->c.clear = _ssll_clear;
341
342
343 return (netsnmp_container*)sl;
344 }
345
346 netsnmp_factory *
netsnmp_container_get_ssll_factory(void)347 netsnmp_container_get_ssll_factory(void)
348 {
349 static netsnmp_factory f = {"sorted_singly_linked_list",
350 (netsnmp_factory_produce_f*)
351 netsnmp_container_get_ssll };
352
353 return &f;
354 }
355
356
357 netsnmp_container *
netsnmp_container_get_usll(void)358 netsnmp_container_get_usll(void)
359 {
360 /*
361 * allocate memory
362 */
363 sl_container *sl = (sl_container *)netsnmp_container_get_ssll();
364 if (NULL==sl)
365 return NULL; /* msg already logged */
366
367 sl->unsorted = 1;
368
369 return (netsnmp_container*)sl;
370 }
371
372 netsnmp_container *
netsnmp_container_get_singly_linked_list(int fifo)373 netsnmp_container_get_singly_linked_list(int fifo)
374 {
375 sl_container *sl = (sl_container *)netsnmp_container_get_usll();
376 if (NULL == sl)
377 return NULL; /* error already logged */
378
379 sl->fifo = fifo;
380
381 return (netsnmp_container *)sl;
382 }
383
384 netsnmp_container *
netsnmp_container_get_fifo(void)385 netsnmp_container_get_fifo(void)
386 {
387 return netsnmp_container_get_singly_linked_list(1);
388 }
389
390 netsnmp_factory *
netsnmp_container_get_usll_factory(void)391 netsnmp_container_get_usll_factory(void)
392 {
393 static netsnmp_factory f = {"unsorted_singly_linked_list-lifo",
394 (netsnmp_factory_produce_f*)
395 netsnmp_container_get_usll };
396
397 return &f;
398 }
399
400 netsnmp_factory *
netsnmp_container_get_fifo_factory(void)401 netsnmp_container_get_fifo_factory(void)
402 {
403 static netsnmp_factory f = {"unsorted_singly_linked_list-fifo",
404 (netsnmp_factory_produce_f*)
405 netsnmp_container_get_fifo };
406
407 return &f;
408 }
409
410 void
netsnmp_container_ssll_init(void)411 netsnmp_container_ssll_init(void)
412 {
413 netsnmp_container_register("sorted_singly_linked_list",
414 netsnmp_container_get_ssll_factory());
415 netsnmp_container_register("unsorted_singly_linked_list",
416 netsnmp_container_get_usll_factory());
417 netsnmp_container_register("lifo",
418 netsnmp_container_get_usll_factory());
419 netsnmp_container_register("fifo",
420 netsnmp_container_get_fifo_factory());
421 }
422
423
424 /**********************************************************************
425 *
426 * iterator
427 *
428 */
429 NETSNMP_STATIC_INLINE sl_container *
_ssll_it2cont(ssll_iterator * it)430 _ssll_it2cont(ssll_iterator *it)
431 {
432 if(NULL == it) {
433 netsnmp_assert(NULL != it);
434 return NULL;
435 }
436
437 if(NULL == it->base.container) {
438 netsnmp_assert(NULL != it->base.container);
439 return NULL;
440 }
441
442 if(it->base.container->sync != it->base.sync) {
443 DEBUGMSGTL(("container:iterator", "out of sync\n"));
444 return NULL;
445 }
446
447 return (sl_container *)it->base.container;
448 }
449
450 static void *
_ssll_iterator_curr(ssll_iterator * it)451 _ssll_iterator_curr(ssll_iterator *it)
452 {
453 sl_container *t = _ssll_it2cont(it);
454 if ((NULL == t) || (NULL == it->pos))
455 return NULL;
456
457 return it->pos->data;
458 }
459
460 static void *
_ssll_iterator_first(ssll_iterator * it)461 _ssll_iterator_first(ssll_iterator *it)
462 {
463 sl_container *t = _ssll_it2cont(it);
464 if ((NULL == t) || (NULL == t->head))
465 return NULL;
466
467 return t->head->data;
468 }
469
470 static void *
_ssll_iterator_next(ssll_iterator * it)471 _ssll_iterator_next(ssll_iterator *it)
472 {
473 sl_container *t = _ssll_it2cont(it);
474 if ((NULL == t) || (NULL == it->pos))
475 return NULL;
476
477 it->pos = it->pos->next;
478 if (NULL == it->pos)
479 return NULL;
480
481 return it->pos->data;
482 }
483
484 static void *
_ssll_iterator_last(ssll_iterator * it)485 _ssll_iterator_last(ssll_iterator *it)
486 {
487 sl_node *n;
488 sl_container *t = _ssll_it2cont(it);
489 if(NULL == t)
490 return NULL;
491
492 if (it->last)
493 return it->last;
494
495 n = it->pos ? it->pos : t->head;
496 if (NULL == n)
497 return NULL;
498
499 while (n->next)
500 n = n->next;
501
502 it->last = n;
503
504 return it->last->data;
505 }
506
507 static int
_ssll_iterator_reset(ssll_iterator * it)508 _ssll_iterator_reset(ssll_iterator *it)
509 {
510 sl_container *t;
511
512 /** can't use it2conf cuz we might be out of sync */
513 if(NULL == it) {
514 netsnmp_assert(NULL != it);
515 return 0;
516 }
517
518 if(NULL == it->base.container) {
519 netsnmp_assert(NULL != it->base.container);
520 return 0;
521 }
522 t = (sl_container *)it->base.container;
523 if(NULL == t)
524 return -1;
525
526 it->last = NULL;
527 it->pos = t->head;
528
529 /*
530 * save sync count, to make sure container doesn't change while
531 * iterator is in use.
532 */
533 it->base.sync = it->base.container->sync;
534
535 return 0;
536 }
537
538 static int
_ssll_iterator_release(netsnmp_iterator * it)539 _ssll_iterator_release(netsnmp_iterator *it)
540 {
541 free(it);
542
543 return 0;
544 }
545
546 static netsnmp_iterator *
_ssll_iterator_get(netsnmp_container * c)547 _ssll_iterator_get(netsnmp_container *c)
548 {
549 ssll_iterator* it;
550
551 if(NULL == c)
552 return NULL;
553
554 it = SNMP_MALLOC_TYPEDEF(ssll_iterator);
555 if(NULL == it)
556 return NULL;
557
558 it->base.container = c;
559
560 it->base.first = (netsnmp_iterator_rtn*)_ssll_iterator_first;
561 it->base.next = (netsnmp_iterator_rtn*)_ssll_iterator_next;
562 it->base.curr = (netsnmp_iterator_rtn*)_ssll_iterator_curr;
563 it->base.last = (netsnmp_iterator_rtn*)_ssll_iterator_last;
564 it->base.reset = (netsnmp_iterator_rc*)_ssll_iterator_reset;
565 it->base.release = (netsnmp_iterator_rc*)_ssll_iterator_release;
566
567 (void)_ssll_iterator_reset(it);
568
569 return (netsnmp_iterator *)it;
570 }
571 #else /* NETSNMP_FEATURE_REMOVE_CONTAINER_LINKED_LIST */
572 netsnmp_feature_unused(container_linked_list);
573 #endif /* NETSNMP_FEATURE_REMOVE_CONTAINER_LINKED_LIST */
574