From 440d5faa3a328e226435785afe7793251746175f Mon Sep 17 00:00:00 2001 From: David Lamparter Date: Mon, 25 May 2015 06:36:10 +0200 Subject: lib: add "seqlock" wait/broadcast primitive Manually tested rather extensively in addition to included unit tests, should work as intended. NB: The OpenBSD futex() code is "future"; it's not actually in OpenBSD (yet?) and thus untested. Signed-off-by: David Lamparter --- tests/.gitignore | 1 + tests/lib/test_seqlock.c | 122 +++++++++++++++++++++++++++++++++++++++++++++++ tests/subdir.am | 5 ++ 3 files changed, 128 insertions(+) create mode 100644 tests/lib/test_seqlock.c (limited to 'tests') diff --git a/tests/.gitignore b/tests/.gitignore index de648015f1..c29a6c3820 100644 --- a/tests/.gitignore +++ b/tests/.gitignore @@ -32,6 +32,7 @@ /lib/test_privs /lib/test_ringbuf /lib/test_segv +/lib/test_seqlock /lib/test_sig /lib/test_srcdest_table /lib/test_stream diff --git a/tests/lib/test_seqlock.c b/tests/lib/test_seqlock.c new file mode 100644 index 0000000000..6b2b9ed8a5 --- /dev/null +++ b/tests/lib/test_seqlock.c @@ -0,0 +1,122 @@ +/* + * basic test for seqlock + * + * Copyright (C) 2015 David Lamparter + * + * This program is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License as published by the Free + * Software Foundation; either version 2 of the License, or (at your option) + * any later version. + * + * This program is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for + * more details. + * + * You should have received a copy of the GNU General Public License along with + * this program; if not, write to the Free Software Foundation, Inc., 59 Temple + * Place, Suite 330, Boston, MA 02111-1307 USA + */ + +#include +#include +#include +#include +#include +#include +#include + +#include "monotime.h" +#include "seqlock.h" + +static struct seqlock sqlo; +static pthread_t thr1; +static struct timeval start; + +static void writestr(const char *str) +{ + struct iovec iov[2]; + char buf[32]; + int64_t usec = monotime_since(&start, NULL); + + snprintf(buf, sizeof(buf), "[%02"PRId64"] ", usec / 100000); + + iov[0].iov_base = buf; + iov[0].iov_len = strlen(buf); + iov[1].iov_base = (char *)str; + iov[1].iov_len = strlen(str); + writev(1, iov, 2); +} + +static void *thr1func(void *arg) +{ + assert(!seqlock_held(&sqlo)); + assert(seqlock_check(&sqlo, 1)); + seqlock_wait(&sqlo, 1); + writestr("thr1 (unheld)\n"); + + sleep(2); + + assert(seqlock_held(&sqlo)); + assert(seqlock_check(&sqlo, 1)); + seqlock_wait(&sqlo, 1); + writestr("thr1 @1\n"); + + seqlock_wait(&sqlo, 3); + writestr("thr1 @3\n"); + + seqlock_wait(&sqlo, 5); + writestr("thr1 @5\n"); + + seqlock_wait(&sqlo, 7); + writestr("thr1 @7\n"); + + seqlock_wait(&sqlo, 9); + writestr("thr1 @9\n"); + + seqlock_wait(&sqlo, 11); + writestr("thr1 @11\n"); + return NULL; +} + +int main(int argc, char **argv) +{ + monotime(&start); + + seqlock_init(&sqlo); + + assert(!seqlock_held(&sqlo)); + seqlock_acquire_val(&sqlo, 1); + assert(seqlock_held(&sqlo)); + + assert(seqlock_cur(&sqlo) == 1); + assert(seqlock_bump(&sqlo) == 1); + assert(seqlock_cur(&sqlo) == 3); + assert(seqlock_bump(&sqlo) == 3); + assert(seqlock_bump(&sqlo) == 5); + assert(seqlock_bump(&sqlo) == 7); + assert(seqlock_cur(&sqlo) == 9); + + assert(seqlock_held(&sqlo)); + seqlock_release(&sqlo); + assert(!seqlock_held(&sqlo)); + + pthread_create(&thr1, NULL, thr1func, NULL); + sleep(1); + + writestr("main @3\n"); + seqlock_acquire_val(&sqlo, 3); + sleep(2); + + writestr("main @5\n"); + seqlock_bump(&sqlo); + sleep(1); + + writestr("main @9\n"); + seqlock_acquire_val(&sqlo, 9); + sleep(1); + + writestr("main @release\n"); + seqlock_release(&sqlo); + sleep(1); +} diff --git a/tests/subdir.am b/tests/subdir.am index 365fe00cc6..167d8b43f1 100644 --- a/tests/subdir.am +++ b/tests/subdir.am @@ -59,6 +59,7 @@ check_PROGRAMS = \ tests/lib/test_ringbuf \ tests/lib/test_srcdest_table \ tests/lib/test_segv \ + tests/lib/test_seqlock \ tests/lib/test_sig \ tests/lib/test_stream \ tests/lib/test_table \ @@ -236,6 +237,10 @@ tests_lib_test_segv_CFLAGS = $(TESTS_CFLAGS) tests_lib_test_segv_CPPFLAGS = $(TESTS_CPPFLAGS) tests_lib_test_segv_LDADD = $(ALL_TESTS_LDADD) tests_lib_test_segv_SOURCES = tests/lib/test_segv.c +tests_lib_test_seqlock_CFLAGS = $(TESTS_CFLAGS) +tests_lib_test_seqlock_CPPFLAGS = $(TESTS_CPPFLAGS) +tests_lib_test_seqlock_LDADD = $(ALL_TESTS_LDADD) +tests_lib_test_seqlock_SOURCES = tests/lib/test_seqlock.c tests_lib_test_sig_CFLAGS = $(TESTS_CFLAGS) tests_lib_test_sig_CPPFLAGS = $(TESTS_CPPFLAGS) tests_lib_test_sig_LDADD = $(ALL_TESTS_LDADD) -- cgit v1.2.3 From bcea0c0fde0ae5f69aae7bd9d20f643075a14d06 Mon Sep 17 00:00:00 2001 From: David Lamparter Date: Tue, 8 Nov 2016 18:11:20 +0100 Subject: lib: atomlist & atomsort These two are lock-free linked list implementations, the plain one is primarily intended for queues while the sorted one is for general data storage. Signed-off-by: David Lamparter --- lib/atomlist.c | 348 ++++++++++++++++++++++++++++++++++++++ lib/atomlist.h | 347 ++++++++++++++++++++++++++++++++++++++ lib/compiler.h | 7 + lib/subdir.am | 2 + tests/.gitignore | 1 + tests/lib/test_atomlist.c | 404 +++++++++++++++++++++++++++++++++++++++++++++ tests/lib/test_atomlist.py | 6 + tests/subdir.am | 6 + 8 files changed, 1121 insertions(+) create mode 100644 lib/atomlist.c create mode 100644 lib/atomlist.h create mode 100644 tests/lib/test_atomlist.c create mode 100644 tests/lib/test_atomlist.py (limited to 'tests') diff --git a/lib/atomlist.c b/lib/atomlist.c new file mode 100644 index 0000000000..8169ba9eb4 --- /dev/null +++ b/lib/atomlist.c @@ -0,0 +1,348 @@ +/* + * Copyright (c) 2016-2018 David Lamparter, for NetDEF, Inc. + * + * Permission to use, copy, modify, and distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +#ifdef HAVE_CONFIG_H +#include "config.h" +#endif + +#include "atomlist.h" + +void atomlist_add_head(struct atomlist_head *h, struct atomlist_item *item) +{ + atomptr_t prevval; + atomptr_t i = atomptr_i(item); + + atomic_fetch_add_explicit(&h->count, 1, memory_order_relaxed); + + /* updating ->last is possible here, but makes the code considerably + * more complicated... let's not. + */ + prevval = ATOMPTR_NULL; + item->next = ATOMPTR_NULL; + + /* head-insert atomically + * release barrier: item + item->next writes must be completed + */ + while (!atomic_compare_exchange_weak_explicit(&h->first, &prevval, i, + memory_order_release, memory_order_relaxed)) + atomic_store_explicit(&item->next, prevval, + memory_order_relaxed); +} + +void atomlist_add_tail(struct atomlist_head *h, struct atomlist_item *item) +{ + atomptr_t prevval = ATOMPTR_NULL; + atomptr_t i = atomptr_i(item); + atomptr_t hint; + struct atomlist_item *prevptr; + _Atomic atomptr_t *prev; + + item->next = ATOMPTR_NULL; + + atomic_fetch_add_explicit(&h->count, 1, memory_order_relaxed); + + /* place new item into ->last + * release: item writes completed; acquire: DD barrier on hint + */ + hint = atomic_exchange_explicit(&h->last, i, memory_order_acq_rel); + + while (1) { + if (atomptr_p(hint) == NULL) + prev = &h->first; + else + prev = &atomlist_itemp(hint)->next; + + do { + prevval = atomic_load_explicit(prev, + memory_order_consume); + prevptr = atomlist_itemp(prevval); + if (prevptr == NULL) + break; + + prev = &prevptr->next; + } while (prevptr); + + /* last item is being deleted - start over */ + if (atomptr_l(prevval)) { + hint = ATOMPTR_NULL; + continue; + } + + /* no barrier - item->next is NULL and was so in xchg above */ + if (!atomic_compare_exchange_strong_explicit(prev, &prevval, i, + memory_order_consume, + memory_order_consume)) { + hint = prevval; + continue; + } + break; + } +} + +static void atomlist_del_core(struct atomlist_head *h, + struct atomlist_item *item, + _Atomic atomptr_t *hint, + atomptr_t next) +{ + _Atomic atomptr_t *prev = hint ? hint : &h->first, *upd; + atomptr_t prevval, updval; + struct atomlist_item *prevptr; + + /* drop us off "last" if needed. no r/w to barrier. */ + prevval = atomptr_i(item); + atomic_compare_exchange_strong_explicit(&h->last, &prevval, + ATOMPTR_NULL, + memory_order_relaxed, memory_order_relaxed); + + atomic_fetch_sub_explicit(&h->count, 1, memory_order_relaxed); + + /* the following code should be identical (except sort<>list) to + * atomsort_del_hint() + */ + while (1) { + upd = NULL; + updval = ATOMPTR_LOCK; + + do { + prevval = atomic_load_explicit(prev, + memory_order_consume); + + /* track the beginning of a chain of deleted items + * this is neccessary to make this lock-free; we can + * complete deletions started by other threads. + */ + if (!atomptr_l(prevval)) { + updval = prevval; + upd = prev; + } + + prevptr = atomlist_itemp(prevval); + if (prevptr == item) + break; + + prev = &prevptr->next; + } while (prevptr); + + if (prevptr != item) + /* another thread completed our deletion */ + return; + + if (!upd || atomptr_l(updval)) { + /* failed to find non-deleted predecessor... + * have to try again + */ + prev = &h->first; + continue; + } + + if (!atomic_compare_exchange_strong_explicit(upd, &updval, + next, memory_order_consume, + memory_order_consume)) { + /* prev doesn't point to item anymore, something + * was inserted. continue at same position forward. + */ + continue; + } + break; + } +} + +void atomlist_del_hint(struct atomlist_head *h, struct atomlist_item *item, + _Atomic atomptr_t *hint) +{ + atomptr_t next; + + /* mark ourselves in-delete - full barrier */ + next = atomic_fetch_or_explicit(&item->next, ATOMPTR_LOCK, + memory_order_acquire); + assert(!atomptr_l(next)); /* delete race on same item */ + + atomlist_del_core(h, item, hint, next); +} + +struct atomlist_item *atomlist_pop(struct atomlist_head *h) +{ + struct atomlist_item *item; + atomptr_t next; + + /* grab head of the list - and remember it in replval for the + * actual delete below. No matter what, the head of the list is + * where we start deleting because either it's our item, or it's + * some delete-marked items and then our item. + */ + next = atomic_load_explicit(&h->first, memory_order_consume); + + do { + item = atomlist_itemp(next); + if (!item) + return NULL; + + /* try to mark deletion */ + next = atomic_fetch_or_explicit(&item->next, ATOMPTR_LOCK, + memory_order_acquire); + + } while (atomptr_l(next)); + /* if loop is taken: delete race on same item (another pop or del) + * => proceed to next item + * if loop exited here: we have our item selected and marked + */ + atomlist_del_core(h, item, &h->first, next); + return item; +} + +struct atomsort_item *atomsort_add(struct atomsort_head *h, + struct atomsort_item *item, int (*cmpfn)( + const struct atomsort_item *, + const struct atomsort_item *)) +{ + _Atomic atomptr_t *prev; + atomptr_t prevval; + atomptr_t i = atomptr_i(item); + struct atomsort_item *previtem; + int cmpval; + + do { + prev = &h->first; + + do { + prevval = atomic_load_explicit(prev, + memory_order_acquire); + previtem = atomptr_p(prevval); + + if (!previtem || (cmpval = cmpfn(previtem, item)) > 0) + break; + if (cmpval == 0) + return previtem; + + prev = &previtem->next; + } while (1); + + if (atomptr_l(prevval)) + continue; + + item->next = prevval; + if (atomic_compare_exchange_strong_explicit(prev, &prevval, i, + memory_order_release, memory_order_relaxed)) + break; + } while (1); + + atomic_fetch_add_explicit(&h->count, 1, memory_order_relaxed); + return NULL; +} + +static void atomsort_del_core(struct atomsort_head *h, + struct atomsort_item *item, _Atomic atomptr_t *hint, + atomptr_t next) +{ + _Atomic atomptr_t *prev = hint ? hint : &h->first, *upd; + atomptr_t prevval, updval; + struct atomsort_item *prevptr; + + atomic_fetch_sub_explicit(&h->count, 1, memory_order_relaxed); + + /* the following code should be identical (except sort<>list) to + * atomlist_del_core() + */ + while (1) { + upd = NULL; + updval = ATOMPTR_LOCK; + + do { + prevval = atomic_load_explicit(prev, + memory_order_consume); + + /* track the beginning of a chain of deleted items + * this is neccessary to make this lock-free; we can + * complete deletions started by other threads. + */ + if (!atomptr_l(prevval)) { + updval = prevval; + upd = prev; + } + + prevptr = atomsort_itemp(prevval); + if (prevptr == item) + break; + + prev = &prevptr->next; + } while (prevptr); + + if (prevptr != item) + /* another thread completed our deletion */ + return; + + if (!upd || atomptr_l(updval)) { + /* failed to find non-deleted predecessor... + * have to try again + */ + prev = &h->first; + continue; + } + + if (!atomic_compare_exchange_strong_explicit(upd, &updval, + next, memory_order_relaxed, + memory_order_relaxed)) { + /* prev doesn't point to item anymore, something + * was inserted. continue at same position forward. + */ + continue; + } + break; + } +} + +void atomsort_del_hint(struct atomsort_head *h, struct atomsort_item *item, + _Atomic atomptr_t *hint) +{ + atomptr_t next; + + /* mark ourselves in-delete - full barrier */ + next = atomic_fetch_or_explicit(&item->next, ATOMPTR_LOCK, + memory_order_seq_cst); + assert(!atomptr_l(next)); /* delete race on same item */ + + atomsort_del_core(h, item, hint, next); +} + +struct atomsort_item *atomsort_pop(struct atomsort_head *h) +{ + struct atomsort_item *item; + atomptr_t next; + + /* grab head of the list - and remember it in replval for the + * actual delete below. No matter what, the head of the list is + * where we start deleting because either it's our item, or it's + * some delete-marked items and then our item. + */ + next = atomic_load_explicit(&h->first, memory_order_consume); + + do { + item = atomsort_itemp(next); + if (!item) + return NULL; + + /* try to mark deletion */ + next = atomic_fetch_or_explicit(&item->next, ATOMPTR_LOCK, + memory_order_acquire); + + } while (atomptr_l(next)); + /* if loop is taken: delete race on same item (another pop or del) + * => proceed to next item + * if loop exited here: we have our item selected and marked + */ + atomsort_del_core(h, item, &h->first, next); + return item; +} diff --git a/lib/atomlist.h b/lib/atomlist.h new file mode 100644 index 0000000000..373c481f2a --- /dev/null +++ b/lib/atomlist.h @@ -0,0 +1,347 @@ +/* + * Copyright (c) 2016-2019 David Lamparter, for NetDEF, Inc. + * + * Permission to use, copy, modify, and distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +#ifndef _FRR_ATOMLIST_H +#define _FRR_ATOMLIST_H + +#include "typesafe.h" +#include "frratomic.h" + +/* pointer with lock/deleted/invalid bit in lowest bit + * + * for atomlist/atomsort, "locked" means "this pointer can't be updated, the + * item is being deleted". it is permissible to assume the item will indeed + * be deleted (as there are no replace/etc. ops in this). + * + * in general, lowest 2/3 bits on 32/64bit architectures are available for + * uses like this; the only thing that will really break this is putting an + * atomlist_item in a struct with "packed" attribute. (it'll break + * immediately and consistently.) -- don't do that. + * + * ATOMPTR_USER is currently unused (and available for atomic hash or skiplist + * implementations.) + */ +typedef uintptr_t atomptr_t; +#define ATOMPTR_MASK (UINTPTR_MAX - 3) +#define ATOMPTR_LOCK (1) +#define ATOMPTR_USER (2) +#define ATOMPTR_NULL (0) + +static inline atomptr_t atomptr_i(void *val) +{ + atomptr_t atomval = (atomptr_t)val; + + assert(!(atomval & ATOMPTR_LOCK)); + return atomval; +} +static inline void *atomptr_p(atomptr_t val) +{ + return (void *)(val & ATOMPTR_MASK); +} +static inline bool atomptr_l(atomptr_t val) +{ + return (bool)(val & ATOMPTR_LOCK); +} +static inline bool atomptr_u(atomptr_t val) +{ + return (bool)(val & ATOMPTR_USER); +} + + +/* the problem with, find(), find_gteq() and find_lt() on atomic lists is that + * they're neither an "acquire" nor a "release" operation; the element that + * was found is still on the list and doesn't change ownership. Therefore, + * an atomic transition in ownership state can't be implemented. + * + * Contrast this with add() or pop(): both function calls atomically transfer + * ownership of an item to or from the list, which makes them "acquire" / + * "release" operations. + * + * What can be implemented atomically is a "find_pop()", i.e. try to locate an + * item and atomically try to remove it if found. It's not currently + * implemented but can be added when needed. + * + * Either way - for find(), generally speaking, if you need to use find() on + * a list then the whole thing probably isn't well-suited to atomic + * implementation and you'll need to have extra locks around to make it work + * correctly. + */ +#ifdef WNO_ATOMLIST_UNSAFE_FIND +# define atomic_find_warn +#else +# define atomic_find_warn __attribute__((_DEPRECATED( \ + "WARNING: find() on atomic lists cannot be atomic by principle; " \ + "check code to make sure usage pattern is OK and if it is, use " \ + "#define WNO_ATOMLIST_UNSAFE_FIND"))) +#endif + + +/* single-linked list, unsorted/arbitrary. + * can be used as queue with add_tail / pop + * + * all operations are lock-free, but not neccessarily wait-free. this means + * that there is no state where the system as a whole stops making process, + * but it *is* possible that a *particular* thread is delayed by some time. + * + * the only way for this to happen is for other threads to continuously make + * updates. an inactive / blocked / deadlocked other thread cannot cause such + * delays, and to cause such delays a thread must be heavily hitting the list - + * it's a rather theoretical concern. + */ + +/* don't use these structs directly */ +struct atomlist_item { + _Atomic atomptr_t next; +}; +#define atomlist_itemp(val) ((struct atomlist_item *)atomptr_p(val)) + +struct atomlist_head { + _Atomic atomptr_t first, last; + _Atomic size_t count; +}; + +/* use as: + * + * PREDECL_ATOMLIST(namelist) + * struct name { + * struct namelist_item nlitem; + * } + * DECLARE_ATOMLIST(namelist, struct name, nlitem) + */ +#define PREDECL_ATOMLIST(prefix) \ +struct prefix ## _head { struct atomlist_head ah; }; \ +struct prefix ## _item { struct atomlist_item ai; }; + +#define INIT_ATOMLIST(var) { } + +#define DECLARE_ATOMLIST(prefix, type, field) \ +macro_inline void prefix ## _add_head(struct prefix##_head *h, type *item) \ +{ atomlist_add_head(&h->ah, &item->field.ai); } \ +macro_inline void prefix ## _add_tail(struct prefix##_head *h, type *item) \ +{ atomlist_add_tail(&h->ah, &item->field.ai); } \ +macro_inline void prefix ## _del_hint(struct prefix##_head *h, type *item, \ + _Atomic atomptr_t *hint) \ +{ atomlist_del_hint(&h->ah, &item->field.ai, hint); } \ +macro_inline void prefix ## _del(struct prefix##_head *h, type *item) \ +{ atomlist_del_hint(&h->ah, &item->field.ai, NULL); } \ +macro_inline type *prefix ## _pop(struct prefix##_head *h) \ +{ char *p = (char *)atomlist_pop(&h->ah); \ + return p ? (type *)(p - offsetof(type, field)) : NULL; } \ +macro_inline type *prefix ## _first(struct prefix##_head *h) \ +{ char *p = atomptr_p(atomic_load_explicit(&h->ah.first, \ + memory_order_acquire)); \ + return p ? (type *)(p - offsetof(type, field)) : NULL; } \ +macro_inline type *prefix ## _next(struct prefix##_head *h, type *item) \ +{ char *p = atomptr_p(atomic_load_explicit(&item->field.ai.next, \ + memory_order_acquire)); \ + return p ? (type *)(p - offsetof(type, field)) : NULL; } \ +macro_inline type *prefix ## _next_safe(struct prefix##_head *h, type *item) \ +{ return item ? prefix##_next(h, item) : NULL; } \ +macro_inline size_t prefix ## _count(struct prefix##_head *h) \ +{ return atomic_load_explicit(&h->ah.count, memory_order_relaxed); } \ +/* ... */ + +/* add_head: + * - contention on ->first pointer + * - return implies completion + */ +void atomlist_add_head(struct atomlist_head *h, struct atomlist_item *item); + +/* add_tail: + * - concurrent add_tail can cause wait but has progress guarantee + * - return does NOT imply completion. completion is only guaranteed after + * all other add_tail operations that started before this add_tail have + * completed as well. + */ +void atomlist_add_tail(struct atomlist_head *h, struct atomlist_item *item); + +/* del/del_hint: + * + * OWNER MUST HOLD REFERENCE ON ITEM TO BE DELETED, ENSURING NO OTHER THREAD + * WILL TRY TO DELETE THE SAME ITEM. DELETING INCLUDES pop(). + * + * as with all deletions, threads that started reading earlier may still hold + * pointers to the deleted item. completion is however guaranteed for all + * reads starting later. + */ +void atomlist_del_hint(struct atomlist_head *h, struct atomlist_item *item, + _Atomic atomptr_t *hint); + +/* pop: + * + * as with all deletions, threads that started reading earlier may still hold + * pointers to the deleted item. completion is however guaranteed for all + * reads starting later. + */ +struct atomlist_item *atomlist_pop(struct atomlist_head *h); + + + +struct atomsort_item { + _Atomic atomptr_t next; +}; +#define atomsort_itemp(val) ((struct atomsort_item *)atomptr_p(val)) + +struct atomsort_head { + _Atomic atomptr_t first; + _Atomic size_t count; +}; + +#define _PREDECL_ATOMSORT(prefix) \ +struct prefix ## _head { struct atomsort_head ah; }; \ +struct prefix ## _item { struct atomsort_item ai; }; + +#define INIT_ATOMSORT_UNIQ(var) { } +#define INIT_ATOMSORT_NONUNIQ(var) { } + +#define _DECLARE_ATOMSORT(prefix, type, field, cmpfn_nuq, cmpfn_uq) \ +macro_inline void prefix ## _init(struct prefix##_head *h) \ +{ \ + memset(h, 0, sizeof(*h)); \ +} \ +macro_inline void prefix ## _fini(struct prefix##_head *h) \ +{ \ + assert(h->ah.count == 0); \ + memset(h, 0, sizeof(*h)); \ +} \ +macro_inline type *prefix ## _add(struct prefix##_head *h, type *item) \ +{ \ + struct atomsort_item *p; \ + p = atomsort_add(&h->ah, &item->field.ai, cmpfn_uq); \ + return container_of_null(p, type, field.ai); \ +} \ +macro_inline type *prefix ## _first(struct prefix##_head *h) \ +{ \ + struct atomsort_item *p; \ + p = atomptr_p(atomic_load_explicit(&h->ah.first, \ + memory_order_acquire)); \ + return container_of_null(p, type, field.ai); \ +} \ +macro_inline type *prefix ## _next(struct prefix##_head *h, type *item) \ +{ \ + struct atomsort_item *p; \ + p = atomptr_p(atomic_load_explicit(&item->field.ai.next, \ + memory_order_acquire)); \ + return container_of_null(p, type, field.ai); \ +} \ +macro_inline type *prefix ## _next_safe(struct prefix##_head *h, type *item) \ +{ \ + return item ? prefix##_next(h, item) : NULL; \ +} \ +atomic_find_warn \ +macro_inline type *prefix ## _find_gteq(struct prefix##_head *h, \ + const type *item) \ +{ \ + type *p = prefix ## _first(h); \ + while (p && cmpfn_nuq(&p->field.ai, &item->field.ai) < 0) \ + p = prefix ## _next(h, p); \ + return p; \ +} \ +atomic_find_warn \ +macro_inline type *prefix ## _find_lt(struct prefix##_head *h, \ + const type *item) \ +{ \ + type *p = prefix ## _first(h), *prev = NULL; \ + while (p && cmpfn_nuq(&p->field.ai, &item->field.ai) < 0) \ + p = prefix ## _next(h, (prev = p)); \ + return prev; \ +} \ +macro_inline void prefix ## _del_hint(struct prefix##_head *h, type *item, \ + _Atomic atomptr_t *hint) \ +{ \ + atomsort_del_hint(&h->ah, &item->field.ai, hint); \ +} \ +macro_inline void prefix ## _del(struct prefix##_head *h, type *item) \ +{ \ + atomsort_del_hint(&h->ah, &item->field.ai, NULL); \ +} \ +macro_inline size_t prefix ## _count(struct prefix##_head *h) \ +{ \ + return atomic_load_explicit(&h->ah.count, memory_order_relaxed); \ +} \ +macro_inline type *prefix ## _pop(struct prefix##_head *h) \ +{ \ + struct atomsort_item *p = atomsort_pop(&h->ah); \ + return p ? container_of(p, type, field.ai) : NULL; \ +} \ +/* ... */ + +#define PREDECL_ATOMSORT_UNIQ(prefix) \ + _PREDECL_ATOMSORT(prefix) +#define DECLARE_ATOMSORT_UNIQ(prefix, type, field, cmpfn) \ + \ +macro_inline int prefix ## __cmp(const struct atomsort_item *a, \ + const struct atomsort_item *b) \ +{ \ + return cmpfn(container_of(a, type, field.ai), \ + container_of(b, type, field.ai)); \ +} \ + \ +_DECLARE_ATOMSORT(prefix, type, field, \ + prefix ## __cmp, prefix ## __cmp) \ + \ +atomic_find_warn \ +macro_inline type *prefix ## _find(struct prefix##_head *h, const type *item) \ +{ \ + type *p = prefix ## _first(h); \ + int cmpval = 0; \ + while (p && (cmpval = cmpfn(p, item)) < 0) \ + p = prefix ## _next(h, p); \ + if (!p || cmpval > 0) \ + return NULL; \ + return p; \ +} \ +/* ... */ + +#define PREDECL_ATOMSORT_NONUNIQ(prefix) \ + _PREDECL_ATOMSORT(prefix) +#define DECLARE_ATOMSORT_NONUNIQ(prefix, type, field, cmpfn) \ + \ +macro_inline int prefix ## __cmp(const struct atomsort_item *a, \ + const struct atomsort_item *b) \ +{ \ + return cmpfn(container_of(a, type, field.ai), \ + container_of(b, type, field.ai)); \ +} \ +macro_inline int prefix ## __cmp_uq(const struct atomsort_item *a, \ + const struct atomsort_item *b) \ +{ \ + int cmpval = cmpfn(container_of(a, type, field.ai), \ + container_of(b, type, field.ai)); \ + if (cmpval) \ + return cmpval; \ + if (a < b) \ + return -1; \ + if (a > b) \ + return 1; \ + return 0; \ +} \ + \ +_DECLARE_ATOMSORT(prefix, type, field, \ + prefix ## __cmp, prefix ## __cmp_uq) \ +/* ... */ + +struct atomsort_item *atomsort_add(struct atomsort_head *h, + struct atomsort_item *item, int (*cmpfn)( + const struct atomsort_item *, + const struct atomsort_item *)); + +void atomsort_del_hint(struct atomsort_head *h, + struct atomsort_item *item, _Atomic atomptr_t *hint); + +struct atomsort_item *atomsort_pop(struct atomsort_head *h); + +#endif /* _FRR_ATOMLIST_H */ diff --git a/lib/compiler.h b/lib/compiler.h index 02bdbd6afd..474adc7c8b 100644 --- a/lib/compiler.h +++ b/lib/compiler.h @@ -32,6 +32,7 @@ extern "C" { # define _FALLTHROUGH __attribute__((fallthrough)); #endif # define _CONSTRUCTOR(x) constructor(x) +# define _DEPRECATED(x) deprecated(x) #elif defined(__GNUC__) #if __GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 9) # define _RET_NONNULL , returns_nonnull @@ -41,6 +42,9 @@ extern "C" { # define _DESTRUCTOR(x) destructor(x) # define _ALLOC_SIZE(x) alloc_size(x) #endif +#if __GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 5) +# define _DEPRECATED(x) deprecated(x) +#endif #if __GNUC__ >= 7 # define _FALLTHROUGH __attribute__((fallthrough)); #endif @@ -68,6 +72,9 @@ extern "C" { #ifndef _FALLTHROUGH #define _FALLTHROUGH #endif +#ifndef _DEPRECATED +#define _DEPRECATED(x) deprecated +#endif /* for helper functions defined inside macros */ #define macro_inline static inline __attribute__((unused)) diff --git a/lib/subdir.am b/lib/subdir.am index 7e9ee90785..7efd3825ef 100644 --- a/lib/subdir.am +++ b/lib/subdir.am @@ -7,6 +7,7 @@ lib_libfrr_la_LIBADD = $(LIBCAP) $(UNWIND_LIBS) $(LIBYANG_LIBS) lib_libfrr_la_SOURCES = \ lib/agg_table.c \ + lib/atomlist.c \ lib/bfd.c \ lib/buffer.c \ lib/checksum.c \ @@ -133,6 +134,7 @@ lib/northbound_cli.lo: lib/northbound_cli_clippy.c pkginclude_HEADERS += \ lib/agg_table.h \ + lib/atomlist.h \ lib/bfd.h \ lib/bitfield.h \ lib/buffer.h \ diff --git a/tests/.gitignore b/tests/.gitignore index c29a6c3820..78f70c3990 100644 --- a/tests/.gitignore +++ b/tests/.gitignore @@ -20,6 +20,7 @@ /lib/cli/test_commands_defun.c /lib/northbound/test_oper_data /lib/cxxcompat +/lib/test_atomlist /lib/test_buffer /lib/test_checksum /lib/test_graph diff --git a/tests/lib/test_atomlist.c b/tests/lib/test_atomlist.c new file mode 100644 index 0000000000..078e05e336 --- /dev/null +++ b/tests/lib/test_atomlist.c @@ -0,0 +1,404 @@ +/* + * Copyright (c) 2016-2018 David Lamparter, for NetDEF, Inc. + * + * Permission to use, copy, modify, and distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +#ifdef HAVE_CONFIG_H +#include "config.h" +#endif + +#include +#include +#include +#include +#include +#include +#include + +#include "atomlist.h" +#include "seqlock.h" +#include "monotime.h" + +/* + * maybe test: + * - alist_del_hint + * - alist_next_safe + * - asort_del_hint + * - asort_next_safe + */ + +static struct seqlock sqlo; + +PREDECL_ATOMLIST(alist) +PREDECL_ATOMSORT_UNIQ(asort) +struct item { + uint64_t val1; + struct alist_item chain; + struct asort_item sortc; + uint64_t val2; +}; +DECLARE_ATOMLIST(alist, struct item, chain) + +static int icmp(const struct item *a, const struct item *b); +DECLARE_ATOMSORT_UNIQ(asort, struct item, sortc, icmp) + +static int icmp(const struct item *a, const struct item *b) +{ + if (a->val1 > b->val1) + return 1; + if (a->val1 < b->val1) + return -1; + return 0; +} + +#define NITEM 10000 +struct item itm[NITEM]; + +static struct alist_head ahead; +static struct asort_head shead; + +#define NTHREADS 4 +static struct testthread { + pthread_t pt; + struct seqlock sqlo; + size_t counter, nullops; +} thr[NTHREADS]; + +struct testrun { + struct testrun *next; + int lineno; + const char *desc; + ssize_t prefill; + bool sorted; + void (*func)(unsigned int offset); +}; +struct testrun *runs = NULL; + +#define NOCLEAR -1 + +#define deftestrun(name, _desc, _prefill, _sorted) \ +static void trfunc_##name(unsigned int offset); \ +struct testrun tr_##name = { \ + .desc = _desc, \ + .lineno = __LINE__, \ + .prefill = _prefill, \ + .func = &trfunc_##name, \ + .sorted = _sorted }; \ +static void __attribute__((constructor)) trsetup_##name(void) \ +{ \ + struct testrun **inspos = &runs; \ + while (*inspos && (*inspos)->lineno < tr_##name.lineno) \ + inspos = &(*inspos)->next; \ + tr_##name.next = *inspos; \ + *inspos = &tr_##name; \ +} \ +static void trfunc_##name(unsigned int offset) \ +{ \ + size_t i = 0, n = 0; + +#define endtestrun \ + thr[offset].counter = i; \ + thr[offset].nullops = n; \ +} + +deftestrun(add, "add vs. add", 0, false) + for (; i < NITEM / NTHREADS; i++) + alist_add_head(&ahead, &itm[i * NTHREADS + offset]); +endtestrun + +deftestrun(del, "del vs. del", NOCLEAR, false) + for (; i < NITEM / NTHREADS / 10; i++) + alist_del(&ahead, &itm[i * NTHREADS + offset]); +endtestrun + +deftestrun(addtail, "add_tail vs. add_tail", 0, false) + for (; i < NITEM / NTHREADS; i++) + alist_add_tail(&ahead, &itm[i * NTHREADS + offset]); +endtestrun + +deftestrun(pop, "pop vs. pop", NOCLEAR, false) + for (; i < NITEM / NTHREADS; ) + if (alist_pop(&ahead)) + i++; + else + n++; +endtestrun + +deftestrun(headN_vs_pop1, "add_head(N) vs. pop(1)", 1, false); + if (offset == 0) { + struct item *dr = NULL; + + for (i = n = 0; i < NITEM; ) { + dr = alist_pop(&ahead); + if (dr) + i++; + else + n++; + } + } else { + for (i = offset; i < NITEM; i += NTHREADS) + alist_add_head(&ahead, &itm[i]); + i = 0; + } +endtestrun + +deftestrun(head1_vs_popN, "add_head(1) vs. pop(N)", 0, false); + if (offset < NTHREADS - 1) { + struct item *dr = NULL; + + for (i = n = 0; i < NITEM / NTHREADS; ) { + dr = alist_pop(&ahead); + if (dr) + i++; + else + n++; + } + } else { + for (i = 0; i < NITEM; i++) + alist_add_head(&ahead, &itm[i]); + i = 0; + } +endtestrun + +deftestrun(headN_vs_popN, "add_head(N) vs. pop(N)", NTHREADS / 2, false) + if (offset < NTHREADS / 2) { + struct item *dr = NULL; + + for (i = n = 0; i < NITEM * 2 / NTHREADS; ) { + dr = alist_pop(&ahead); + if (dr) + i++; + else + n++; + } + } else { + for (i = offset; i < NITEM; i += NTHREADS) + alist_add_head(&ahead, &itm[i]); + i = 0; + } +endtestrun + +deftestrun(tailN_vs_pop1, "add_tail(N) vs. pop(1)", 1, false) + if (offset == 0) { + struct item *dr = NULL; + + for (i = n = 0; i < NITEM - (NITEM / NTHREADS); ) { + dr = alist_pop(&ahead); + if (dr) + i++; + else + n++; + } + } else { + for (i = offset; i < NITEM; i += NTHREADS) + alist_add_tail(&ahead, &itm[i]); + i = 0; + } +endtestrun + +deftestrun(tail1_vs_popN, "add_tail(1) vs. pop(N)", 0, false) + if (offset < NTHREADS - 1) { + struct item *dr = NULL; + + for (i = n = 0; i < NITEM / NTHREADS; ) { + dr = alist_pop(&ahead); + if (dr) + i++; + else + n++; + } + } else { + for (i = 0; i < NITEM; i++) + alist_add_tail(&ahead, &itm[i]); + i = 0; + } +endtestrun + +deftestrun(sort_add, "add_sort vs. add_sort", 0, true) + for (; i < NITEM / NTHREADS / 10; i++) + asort_add(&shead, &itm[i * NTHREADS + offset]); +endtestrun + +deftestrun(sort_del, "del_sort vs. del_sort", NOCLEAR, true) + for (; i < NITEM / NTHREADS / 10; i++) + asort_del(&shead, &itm[i * NTHREADS + offset]); +endtestrun + +deftestrun(sort_add_del, "add_sort vs. del_sort", NTHREADS / 2, true) + if (offset < NTHREADS / 2) { + for (; i < NITEM / NTHREADS / 10; i++) + asort_del(&shead, &itm[i * NTHREADS + offset]); + } else { + for (; i < NITEM / NTHREADS / 10; i++) + asort_add(&shead, &itm[i * NTHREADS + offset]); + } +endtestrun + +static void *thr1func(void *arg) +{ + struct testthread *p = arg; + unsigned int offset = (unsigned int)(p - &thr[0]); + seqlock_val_t sv; + struct testrun *tr; + + for (tr = runs; tr; tr = tr->next) { + sv = seqlock_bump(&p->sqlo); + seqlock_wait(&sqlo, sv); + + tr->func(offset); + } + seqlock_bump(&p->sqlo); + + return NULL; +} + +static void clear_list(size_t prefill) +{ + size_t i; + + memset(&ahead, 0, sizeof(ahead)); + memset(&shead, 0, sizeof(shead)); + memset(itm, 0, sizeof(itm)); + for (i = 0; i < NITEM; i++) { + itm[i].val1 = itm[i].val2 = i; + if ((i % NTHREADS) < prefill) { + alist_add_tail(&ahead, &itm[i]); + asort_add(&shead, &itm[i]); + } + } +} + +static void run_tr(struct testrun *tr) +{ + const char *desc = tr->desc; + struct timeval tv; + int64_t delta; + seqlock_val_t sv; + size_t c = 0, s = 0, n = 0; + struct item *item, *prev, dummy; + + printf("[%02u] %35s %s\n", seqlock_cur(&sqlo) >> 1, "", desc); + fflush(stdout); + + if (tr->prefill != NOCLEAR) + clear_list(tr->prefill); + + monotime(&tv); + sv = seqlock_bump(&sqlo); + for (size_t i = 0; i < NTHREADS; i++) { + seqlock_wait(&thr[i].sqlo, seqlock_cur(&sqlo)); + s += thr[i].counter; + n += thr[i].nullops; + thr[i].counter = 0; + thr[i].nullops = 0; + } + + delta = monotime_since(&tv, NULL); + if (tr->sorted) { + uint64_t prevval = 0; + + for_each(asort, &shead, item) { + assert(item->val1 >= prevval); + prevval = item->val1; + c++; + } + assert(c == asort_count(&shead)); + } else { + prev = &dummy; + for_each(alist, &ahead, item) { + assert(item != prev); + prev = item; + c++; + assert(c <= NITEM); + } + assert(c == alist_count(&ahead)); + } + printf("\033[1A[%02u] %9"PRId64"us c=%5zu s=%5zu n=%5zu %s\n", + sv >> 1, delta, c, s, n, desc); +} + +#ifdef BASIC_TESTS +static void dump(const char *lbl) +{ + struct item *item, *safe; + size_t ctr = 0; + + printf("dumping %s:\n", lbl); + for_each_safe(alist, &ahead, item) { + printf("%s %3zu %p %3"PRIu64" %3"PRIu64"\n", lbl, ctr++, + (void *)item, item->val1, item->val2); + } +} + +static void basic_tests(void) +{ + size_t i; + + memset(&ahead, 0, sizeof(ahead)); + memset(itm, 0, sizeof(itm)); + for (i = 0; i < NITEM; i++) + itm[i].val1 = itm[i].val2 = i; + + assert(alist_first(&ahead) == NULL); + dump(""); + alist_add_head(&ahead, &itm[0]); + dump(""); + alist_add_head(&ahead, &itm[1]); + dump(""); + alist_add_tail(&ahead, &itm[2]); + dump(""); + alist_add_tail(&ahead, &itm[3]); + dump(""); + alist_del(&ahead, &itm[1]); + dump(""); + printf("POP: %p\n", alist_pop(&ahead)); + dump(""); + printf("POP: %p\n", alist_pop(&ahead)); + printf("POP: %p\n", alist_pop(&ahead)); + printf("POP: %p\n", alist_pop(&ahead)); + printf("POP: %p\n", alist_pop(&ahead)); + dump(""); +} +#else +#define basic_tests() do { } while (0) +#endif + +int main(int argc, char **argv) +{ + size_t i; + + basic_tests(); + + seqlock_init(&sqlo); + seqlock_acquire_val(&sqlo, 1); + + for (i = 0; i < NTHREADS; i++) { + seqlock_init(&thr[i].sqlo); + seqlock_acquire(&thr[i].sqlo, &sqlo); + thr[i].counter = 0; + thr[i].nullops = 0; + + pthread_create(&thr[i].pt, NULL, thr1func, &thr[i]); + } + + struct testrun *tr; + + for (tr = runs; tr; tr = tr->next) + run_tr(tr); + + for (i = 0; i < NTHREADS; i++) + pthread_join(thr[i].pt, NULL); + + return 0; +} diff --git a/tests/lib/test_atomlist.py b/tests/lib/test_atomlist.py new file mode 100644 index 0000000000..293d47f316 --- /dev/null +++ b/tests/lib/test_atomlist.py @@ -0,0 +1,6 @@ +import frrtest + +class TestAtomlist(frrtest.TestMultiOut): + program = './test_atomlist' + +TestAtomlist.exit_cleanly() diff --git a/tests/subdir.am b/tests/subdir.am index 167d8b43f1..fd471f757d 100644 --- a/tests/subdir.am +++ b/tests/subdir.am @@ -47,6 +47,7 @@ tests/ospf6d/test_lsdb-test_lsdb.$(OBJEXT): tests/ospf6d/test_lsdb_clippy.c check_PROGRAMS = \ tests/lib/cxxcompat \ + tests/lib/test_atomlist \ tests/lib/test_buffer \ tests/lib/test_checksum \ tests/lib/test_heavy_thread \ @@ -190,6 +191,10 @@ tests_lib_northbound_test_oper_data_CPPFLAGS = $(TESTS_CPPFLAGS) tests_lib_northbound_test_oper_data_LDADD = $(ALL_TESTS_LDADD) tests_lib_northbound_test_oper_data_SOURCES = tests/lib/northbound/test_oper_data.c nodist_tests_lib_northbound_test_oper_data_SOURCES = yang/frr-test-module.yang.c +tests_lib_test_atomlist_CFLAGS = $(TESTS_CFLAGS) +tests_lib_test_atomlist_CPPFLAGS = $(TESTS_CPPFLAGS) +tests_lib_test_atomlist_LDADD = $(ALL_TESTS_LDADD) +tests_lib_test_atomlist_SOURCES = tests/lib/test_atomlist.c tests_lib_test_buffer_CFLAGS = $(TESTS_CFLAGS) tests_lib_test_buffer_CPPFLAGS = $(TESTS_CPPFLAGS) tests_lib_test_buffer_LDADD = $(ALL_TESTS_LDADD) @@ -306,6 +311,7 @@ EXTRA_DIST += \ tests/lib/northbound/test_oper_data.in \ tests/lib/northbound/test_oper_data.py \ tests/lib/northbound/test_oper_data.refout \ + tests/lib/test_atomlist.py \ tests/lib/test_nexthop_iter.py \ tests/lib/test_ringbuf.py \ tests/lib/test_srcdest_table.py \ -- cgit v1.2.3 From 992f9967db14b18ee0eb5a4a104f17ab1dfb2d41 Mon Sep 17 00:00:00 2001 From: David Lamparter Date: Mon, 18 Feb 2019 21:17:22 +0100 Subject: tests: exercise the typesafe list wrappers Since all of these list implementations provide almost the same API, we can run and validate them against the same test code. 9 tests for the price of one! Signed-off-by: David Lamparter --- tests/.gitignore | 1 + tests/lib/test_typelist.c | 142 +++++++++++++++++++++++ tests/lib/test_typelist.h | 272 +++++++++++++++++++++++++++++++++++++++++++++ tests/lib/test_typelist.py | 14 +++ tests/subdir.am | 7 ++ 5 files changed, 436 insertions(+) create mode 100644 tests/lib/test_typelist.c create mode 100644 tests/lib/test_typelist.h create mode 100644 tests/lib/test_typelist.py (limited to 'tests') diff --git a/tests/.gitignore b/tests/.gitignore index 78f70c3990..380172487d 100644 --- a/tests/.gitignore +++ b/tests/.gitignore @@ -41,6 +41,7 @@ /lib/test_timer_correctness /lib/test_timer_performance /lib/test_ttable +/lib/test_typelist /lib/test_zlog /lib/test_zmq /ospf6d/test_lsdb diff --git a/tests/lib/test_typelist.c b/tests/lib/test_typelist.c new file mode 100644 index 0000000000..68ea82ea41 --- /dev/null +++ b/tests/lib/test_typelist.c @@ -0,0 +1,142 @@ +/* + * Copyright (c) 2016-2018 David Lamparter, for NetDEF, Inc. + * + * Permission to use, copy, modify, and distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +#ifdef HAVE_CONFIG_H +#include "config.h" +#endif + +#include +#include +#include +#include +#include +#include +#include + +#define WNO_ATOMLIST_UNSAFE_FIND + +#include "typesafe.h" +#include "atomlist.h" +#include "memory.h" +#include "monotime.h" + +#include "tests/helpers/c/prng.h" + +/* note: these macros are layered 2-deep because that makes the C + * preprocessor expand the "type" argument. Otherwise, you get + * "PREDECL_type" instead of "PREDECL_LIST" + */ +#define _concat(a, b) a ## b +#define concat(a, b) _concat(a, b) +#define _str(x) #x +#define str(x) _str(x) + +#define _PREDECL(type, ...) PREDECL_##type(__VA_ARGS__) +#define PREDECL(type, ...) _PREDECL(type, __VA_ARGS__) +#define _DECLARE(type, ...) DECLARE_##type(__VA_ARGS__) +#define DECLARE(type, ...) _DECLARE(type, __VA_ARGS__) + +#define _U_SORTLIST_UNIQ 1 +#define _U_SORTLIST_NONUNIQ 0 +#define _U_HASH 1 +#define _U_SKIPLIST_UNIQ 1 +#define _U_SKIPLIST_NONUNIQ 0 +#define _U_RBTREE_UNIQ 1 +#define _U_RBTREE_NONUNIQ 0 +#define _U_ATOMSORT_UNIQ 1 +#define _U_ATOMSORT_NONUNIQ 0 + +#define _IS_UNIQ(type) _U_##type +#define IS_UNIQ(type) _IS_UNIQ(type) + +#define _H_SORTLIST_UNIQ 0 +#define _H_SORTLIST_NONUNIQ 0 +#define _H_HASH 1 +#define _H_SKIPLIST_UNIQ 0 +#define _H_SKIPLIST_NONUNIQ 0 +#define _H_RBTREE_UNIQ 0 +#define _H_RBTREE_NONUNIQ 0 +#define _H_ATOMSORT_UNIQ 0 +#define _H_ATOMSORT_NONUNIQ 0 + +#define _IS_HASH(type) _H_##type +#define IS_HASH(type) _IS_HASH(type) + +static struct timeval ref, ref0; + +static void ts_start(void) +{ + monotime(&ref0); + monotime(&ref); +} +static void ts_ref(const char *text) +{ + int64_t us; + us = monotime_since(&ref, NULL); + printf("%7"PRId64"us %s\n", us, text); + monotime(&ref); +} +static void ts_end(void) +{ + int64_t us; + us = monotime_since(&ref0, NULL); + printf("%7"PRId64"us total\n", us); +} + +#define TYPE SORTLIST_UNIQ +#include "test_typelist.h" + +#define TYPE SORTLIST_NONUNIQ +#include "test_typelist.h" + +#define TYPE HASH +#include "test_typelist.h" + +#define TYPE SKIPLIST_UNIQ +#include "test_typelist.h" + +#define TYPE SKIPLIST_NONUNIQ +#include "test_typelist.h" + +#define TYPE RBTREE_UNIQ +#include "test_typelist.h" + +#define TYPE RBTREE_NONUNIQ +#include "test_typelist.h" + +#define TYPE ATOMSORT_UNIQ +#include "test_typelist.h" + +#define TYPE ATOMSORT_NONUNIQ +#include "test_typelist.h" + +int main(int argc, char **argv) +{ + srandom(1); + + test_SORTLIST_UNIQ(); + test_SORTLIST_NONUNIQ(); + test_HASH(); + test_SKIPLIST_UNIQ(); + test_SKIPLIST_NONUNIQ(); + test_RBTREE_UNIQ(); + test_RBTREE_NONUNIQ(); + test_ATOMSORT_UNIQ(); + test_ATOMSORT_NONUNIQ(); + + log_memstats_stderr("test: "); + return 0; +} diff --git a/tests/lib/test_typelist.h b/tests/lib/test_typelist.h new file mode 100644 index 0000000000..60a37e84ed --- /dev/null +++ b/tests/lib/test_typelist.h @@ -0,0 +1,272 @@ +/* + * Copyright (c) 2019 David Lamparter, for NetDEF, Inc. + * + * Permission to use, copy, modify, and distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +/* C++ called, they want their templates back */ +#define item concat(item_, TYPE) +#define itm concat(itm_, TYPE) +#define head concat(head_, TYPE) +#define list concat(TYPE, ) +#define list_head concat(TYPE, _head) +#define list_item concat(TYPE, _item) +#define list_cmp concat(TYPE, _cmp) +#define list_hash concat(TYPE, _hash) +#define list_init concat(TYPE, _init) +#define list_fini concat(TYPE, _fini) +#define list_first concat(TYPE, _first) +#define list_next concat(TYPE, _next) +#define list_next_safe concat(TYPE, _next_safe) +#define list_count concat(TYPE, _count) +#define list_add concat(TYPE, _add) +#define list_find concat(TYPE, _find) +#define list_find_lt concat(TYPE, _find_lt) +#define list_find_gteq concat(TYPE, _find_gteq) +#define list_del concat(TYPE, _del) +#define list_pop concat(TYPE, _pop) + +PREDECL(TYPE, list) +struct item { + uint64_t val; + struct list_item itm; + int scratchpad; +}; + +static int list_cmp(const struct item *a, const struct item *b); + +#if IS_HASH(TYPE) +static uint32_t list_hash(const struct item *a); +DECLARE(TYPE, list, struct item, itm, list_cmp, list_hash) + +static uint32_t list_hash(const struct item *a) +{ + /* crappy hash to get some hash collisions */ + return a->val ^ (a->val << 29) ^ 0x55AA0000U; +} + +#else +DECLARE(TYPE, list, struct item, itm, list_cmp) +#endif + +static int list_cmp(const struct item *a, const struct item *b) +{ + if (a->val > b->val) + return 1; + if (a->val < b->val) + return -1; + return 0; +} + +#define NITEM 10000 +struct item itm[NITEM]; +static struct list_head head = concat(INIT_, TYPE)(head); + +static void concat(test_, TYPE)(void) +{ + size_t i, j, k, l; + struct prng *prng; + struct item *item, *prev; + struct item dummy; + + memset(itm, 0, sizeof(itm)); + for (i = 0; i < NITEM; i++) + itm[i].val = i; + + printf("%s start\n", str(TYPE)); + ts_start(); + + list_init(&head); + ts_ref("init"); + + assert(list_first(&head) == NULL); + + prng = prng_new(0); + k = 0; + for (i = 0; i < NITEM; i++) { + j = prng_rand(prng) % NITEM; + if (itm[j].scratchpad == 0) { + list_add(&head, &itm[j]); + itm[j].scratchpad = 1; + k++; + } else + assert(list_add(&head, &itm[j]) == &itm[j]); + } + assert(list_count(&head) == k); + assert(list_first(&head) != NULL); + ts_ref("fill"); + + k = 0; + prev = NULL; + for_each(list, &head, item) { +#if IS_HASH(TYPE) + /* hash table doesn't give sorting */ + (void)prev; +#else + assert(!prev || prev->val < item->val); +#endif + prev = item; + k++; + } + assert(list_count(&head) == k); + ts_ref("walk"); + +#if IS_UNIQ(TYPE) + prng_free(prng); + prng = prng_new(0); + + for (i = 0; i < NITEM; i++) { + j = prng_rand(prng) % NITEM; + dummy.val = j; + assert(list_find(&head, &dummy) == &itm[j]); + } + ts_ref("find"); + + for (i = 0; i < NITEM; i++) { + j = prng_rand(prng) % NITEM; + memset(&dummy, 0, sizeof(dummy)); + dummy.val = j; + if (itm[j].scratchpad) + assert(list_add(&head, &dummy) == &itm[j]); + else { + assert(list_add(&head, &dummy) == NULL); + list_del(&head, &dummy); + } + } + ts_ref("add-dup"); +#else /* !IS_UNIQ(TYPE) */ + for (i = 0; i < NITEM; i++) { + j = prng_rand(prng) % NITEM; + memset(&dummy, 0, sizeof(dummy)); + dummy.val = j; + + list_add(&head, &dummy); + if (itm[j].scratchpad) { + struct item *lt, *gteq, dummy2; + + assert(list_next(&head, &itm[j]) == &dummy || + list_next(&head, &dummy) == &itm[j]); + + memset(&dummy2, 0, sizeof(dummy)); + dummy2.val = j; + lt = list_find_lt(&head, &dummy2); + gteq = list_find_gteq(&head, &dummy2); + + assert(gteq == &itm[j] || gteq == &dummy); + if (lt) + assert(list_next(&head, lt) == &itm[j] || + list_next(&head, lt) == &dummy); + else + assert(list_first(&head) == &itm[j] || + list_first(&head) == &dummy); + } else if (list_next(&head, &dummy)) + assert(list_next(&head, &dummy)->val > j); + list_del(&head, &dummy); + } + ts_ref("add-dup+find_{lt,gteq}"); +#endif +#if !IS_HASH(TYPE) + prng_free(prng); + prng = prng_new(123456); + + l = 0; + for (i = 0; i < NITEM; i++) { + struct item *lt, *gteq, *tmp; + + j = prng_rand(prng) % NITEM; + dummy.val = j; + + lt = list_find_lt(&head, &dummy); + gteq = list_find_gteq(&head, &dummy); + + if (lt) { + assert(lt->val < j); + tmp = list_next(&head, lt); + assert(tmp == gteq); + assert(!tmp || tmp->val >= j); + } else + assert(gteq == list_first(&head)); + + if (gteq) + assert(gteq->val >= j); + } + ts_ref("find_{lt,gteq}"); +#endif /* !IS_HASH */ + + prng_free(prng); + prng = prng_new(0); + + l = 0; + for (i = 0; i < NITEM; i++) { + (void)prng_rand(prng); + j = prng_rand(prng) % NITEM; + if (itm[j].scratchpad == 1) { + list_del(&head, &itm[j]); + itm[j].scratchpad = 0; + l++; + } + } + assert(l + list_count(&head) == k); + ts_ref("del"); + + for_each_safe(list, &head, item) { + assert(item->scratchpad != 0); + + if (item->val & 1) { + list_del(&head, item); + item->scratchpad = 0; + l++; + } + } + assert(l + list_count(&head) == k); + ts_ref("for_each_safe+del"); + + while ((item = list_pop(&head))) { + assert(item->scratchpad != 0); + + item->scratchpad = 0; + l++; + } + assert(l == k); + assert(list_count(&head) == 0); + assert(list_first(&head) == NULL); + ts_ref("pop"); + + list_fini(&head); + ts_ref("fini"); + ts_end(); + printf("%s end\n", str(TYPE)); +} + +#undef item +#undef itm +#undef head +#undef list +#undef list_head +#undef list_item +#undef list_cmp +#undef list_hash +#undef list_init +#undef list_fini +#undef list_first +#undef list_next +#undef list_next_safe +#undef list_count +#undef list_add +#undef list_find +#undef list_find_lt +#undef list_find_gteq +#undef list_del +#undef list_pop + +#undef TYPE diff --git a/tests/lib/test_typelist.py b/tests/lib/test_typelist.py new file mode 100644 index 0000000000..3b7373ceb8 --- /dev/null +++ b/tests/lib/test_typelist.py @@ -0,0 +1,14 @@ +import frrtest + +class TestTypelist(frrtest.TestMultiOut): + program = './test_typelist' + +TestTypelist.onesimple('SORTLIST_UNIQ end') +TestTypelist.onesimple('SORTLIST_NONUNIQ end') +TestTypelist.onesimple('HASH end') +TestTypelist.onesimple('SKIPLIST_UNIQ end') +TestTypelist.onesimple('SKIPLIST_NONUNIQ end') +TestTypelist.onesimple('RBTREE_UNIQ end') +TestTypelist.onesimple('RBTREE_NONUNIQ end') +TestTypelist.onesimple('ATOMSORT_UNIQ end') +TestTypelist.onesimple('ATOMSORT_NONUNIQ end') diff --git a/tests/subdir.am b/tests/subdir.am index fd471f757d..ec5fea705e 100644 --- a/tests/subdir.am +++ b/tests/subdir.am @@ -67,6 +67,7 @@ check_PROGRAMS = \ tests/lib/test_timer_correctness \ tests/lib/test_timer_performance \ tests/lib/test_ttable \ + tests/lib/test_typelist \ tests/lib/test_zlog \ tests/lib/test_graph \ tests/lib/cli/test_cli \ @@ -105,6 +106,7 @@ noinst_HEADERS += \ tests/helpers/c/prng.h \ tests/helpers/c/tests.h \ tests/lib/cli/common_cli.h \ + tests/lib/test_typelist.h \ # end # @@ -274,6 +276,10 @@ tests_lib_test_ttable_CFLAGS = $(TESTS_CFLAGS) tests_lib_test_ttable_CPPFLAGS = $(TESTS_CPPFLAGS) tests_lib_test_ttable_LDADD = $(ALL_TESTS_LDADD) tests_lib_test_ttable_SOURCES = tests/lib/test_ttable.c +tests_lib_test_typelist_CFLAGS = $(TESTS_CFLAGS) +tests_lib_test_typelist_CPPFLAGS = $(TESTS_CPPFLAGS) +tests_lib_test_typelist_LDADD = $(ALL_TESTS_LDADD) +tests_lib_test_typelist_SOURCES = tests/lib/test_typelist.c tests/helpers/c/prng.c tests_lib_test_zlog_CFLAGS = $(TESTS_CFLAGS) tests_lib_test_zlog_CPPFLAGS = $(TESTS_CPPFLAGS) tests_lib_test_zlog_LDADD = $(ALL_TESTS_LDADD) @@ -321,6 +327,7 @@ EXTRA_DIST += \ tests/lib/test_timer_correctness.py \ tests/lib/test_ttable.py \ tests/lib/test_ttable.refout \ + tests/lib/test_typelist.py \ tests/lib/test_zlog.py \ tests/lib/test_graph.py \ tests/lib/test_graph.refout \ -- cgit v1.2.3 From 798ac49d06b6619adb4c5ac765b092397bc50a6c Mon Sep 17 00:00:00 2001 From: David Lamparter Date: Thu, 31 Jan 2019 03:09:45 +0100 Subject: lib: remove pqueue_* All users of the pqueue_* implementations have been migrated to use TYPEDSKIP_* skiplists. Remove. Signed-off-by: David Lamparter --- lib/pqueue.c | 185 ------------------------------------- lib/pqueue.h | 54 ----------- lib/subdir.am | 2 - tests/lib/cxxcompat.c | 1 - tests/lib/test_timer_correctness.c | 1 - tests/lib/test_timer_performance.c | 1 - 6 files changed, 244 deletions(-) delete mode 100644 lib/pqueue.c delete mode 100644 lib/pqueue.h (limited to 'tests') diff --git a/lib/pqueue.c b/lib/pqueue.c deleted file mode 100644 index 87b54a681a..0000000000 --- a/lib/pqueue.c +++ /dev/null @@ -1,185 +0,0 @@ -/* Priority queue functions. - * Copyright (C) 2003 Yasuhiro Ohara - * - * This file is part of GNU Zebra. - * - * GNU Zebra is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published - * by the Free Software Foundation; either version 2, or (at your - * option) any later version. - * - * GNU Zebra is distributed in the hope that it will be useful, but - * WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU - * General Public License for more details. - * - * You should have received a copy of the GNU General Public License along - * with this program; see the file COPYING; if not, write to the Free Software - * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA - */ - -#include - -#include "memory.h" -#include "pqueue.h" - -DEFINE_MTYPE_STATIC(LIB, PQUEUE, "Priority queue") -DEFINE_MTYPE_STATIC(LIB, PQUEUE_DATA, "Priority queue data") - -/* priority queue using heap sort */ - -/* pqueue->cmp() controls the order of sorting (i.e, ascending or - descending). If you want the left node to move upper of the heap - binary tree, make cmp() to return less than 0. for example, if cmp - (10, 20) returns -1, the sorting is ascending order. if cmp (10, - 20) returns 1, the sorting is descending order. if cmp (10, 20) - returns 0, this library does not do sorting (which will not be what - you want). To be brief, if the contents of cmp_func (left, right) - is left - right, dequeue () returns the smallest node. Otherwise - (if the contents is right - left), dequeue () returns the largest - node. */ - -#define DATA_SIZE (sizeof (void *)) -#define PARENT_OF(x) ((x - 1) / 2) -#define LEFT_OF(x) (2 * x + 1) -#define RIGHT_OF(x) (2 * x + 2) -#define HAVE_CHILD(x,q) (x < (q)->size / 2) - -void trickle_up(int index, struct pqueue *queue) -{ - void *tmp; - - /* Save current node as tmp node. */ - tmp = queue->array[index]; - - /* Continue until the node reaches top or the place where the parent - node should be upper than the tmp node. */ - while (index > 0 - && (*queue->cmp)(tmp, queue->array[PARENT_OF(index)]) < 0) { - /* actually trickle up */ - queue->array[index] = queue->array[PARENT_OF(index)]; - if (queue->update != NULL) - (*queue->update)(queue->array[index], index); - index = PARENT_OF(index); - } - - /* Restore the tmp node to appropriate place. */ - queue->array[index] = tmp; - if (queue->update != NULL) - (*queue->update)(tmp, index); -} - -void trickle_down(int index, struct pqueue *queue) -{ - void *tmp; - int which; - - /* Save current node as tmp node. */ - tmp = queue->array[index]; - - /* Continue until the node have at least one (left) child. */ - while (HAVE_CHILD(index, queue)) { - /* If right child exists, and if the right child is more proper - to be moved upper. */ - if (RIGHT_OF(index) < queue->size - && (*queue->cmp)(queue->array[LEFT_OF(index)], - queue->array[RIGHT_OF(index)]) - > 0) - which = RIGHT_OF(index); - else - which = LEFT_OF(index); - - /* If the tmp node should be upper than the child, break. */ - if ((*queue->cmp)(queue->array[which], tmp) > 0) - break; - - /* Actually trickle down the tmp node. */ - queue->array[index] = queue->array[which]; - if (queue->update != NULL) - (*queue->update)(queue->array[index], index); - index = which; - } - - /* Restore the tmp node to appropriate place. */ - queue->array[index] = tmp; - if (queue->update != NULL) - (*queue->update)(tmp, index); -} - -struct pqueue *pqueue_create(void) -{ - struct pqueue *queue; - - queue = XCALLOC(MTYPE_PQUEUE, sizeof(struct pqueue)); - - queue->array = - XCALLOC(MTYPE_PQUEUE_DATA, DATA_SIZE * PQUEUE_INIT_ARRAYSIZE); - queue->array_size = PQUEUE_INIT_ARRAYSIZE; - - /* By default we want nothing to happen when a node changes. */ - queue->update = NULL; - return queue; -} - -void pqueue_delete(struct pqueue *queue) -{ - XFREE(MTYPE_PQUEUE_DATA, queue->array); - XFREE(MTYPE_PQUEUE, queue); -} - -static int pqueue_expand(struct pqueue *queue) -{ - void **newarray; - - newarray = - XCALLOC(MTYPE_PQUEUE_DATA, queue->array_size * DATA_SIZE * 2); - - memcpy(newarray, queue->array, queue->array_size * DATA_SIZE); - - XFREE(MTYPE_PQUEUE_DATA, queue->array); - queue->array = newarray; - queue->array_size *= 2; - - return 1; -} - -void pqueue_enqueue(void *data, struct pqueue *queue) -{ - if (queue->size + 2 >= queue->array_size && !pqueue_expand(queue)) - return; - - queue->array[queue->size] = data; - if (queue->update != NULL) - (*queue->update)(data, queue->size); - trickle_up(queue->size, queue); - queue->size++; -} - -void *pqueue_dequeue(struct pqueue *queue) -{ - void *data = queue->array[0]; - queue->array[0] = queue->array[--queue->size]; - trickle_down(0, queue); - return data; -} - -void pqueue_remove_at(int index, struct pqueue *queue) -{ - queue->array[index] = queue->array[--queue->size]; - - if (index > 0 - && (*queue->cmp)(queue->array[index], - queue->array[PARENT_OF(index)]) - < 0) { - trickle_up(index, queue); - } else { - trickle_down(index, queue); - } -} - -void pqueue_remove(void *data, struct pqueue *queue) -{ - for (int i = 0; i < queue->size; i++) - if (queue->array[i] == data) - pqueue_remove_at(i, queue); -} diff --git a/lib/pqueue.h b/lib/pqueue.h deleted file mode 100644 index 032ee9db4c..0000000000 --- a/lib/pqueue.h +++ /dev/null @@ -1,54 +0,0 @@ -/* Priority queue functions. - * Copyright (C) 2003 Yasuhiro Ohara - * - * This file is part of GNU Zebra. - * - * GNU Zebra is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published - * by the Free Software Foundation; either version 2, or (at your - * option) any later version. - * - * GNU Zebra is distributed in the hope that it will be useful, but - * WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU - * General Public License for more details. - * - * You should have received a copy of the GNU General Public License along - * with this program; see the file COPYING; if not, write to the Free Software - * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA - */ - -#ifndef _ZEBRA_PQUEUE_H -#define _ZEBRA_PQUEUE_H - -#ifdef __cplusplus -extern "C" { -#endif - -struct pqueue { - void **array; - int array_size; - int size; - - int (*cmp)(void *, void *); - void (*update)(void *node, int actual_position); -}; - -#define PQUEUE_INIT_ARRAYSIZE 32 - -extern struct pqueue *pqueue_create(void); -extern void pqueue_delete(struct pqueue *queue); - -extern void pqueue_enqueue(void *data, struct pqueue *queue); -extern void *pqueue_dequeue(struct pqueue *queue); -extern void pqueue_remove_at(int index, struct pqueue *queue); -extern void pqueue_remove(void *data, struct pqueue *queue); - -extern void trickle_down(int index, struct pqueue *queue); -extern void trickle_up(int index, struct pqueue *queue); - -#ifdef __cplusplus -} -#endif - -#endif /* _ZEBRA_PQUEUE_H */ diff --git a/lib/subdir.am b/lib/subdir.am index 7efd3825ef..9bf02be9c3 100644 --- a/lib/subdir.am +++ b/lib/subdir.am @@ -58,7 +58,6 @@ lib_libfrr_la_SOURCES = \ lib/openbsd-tree.c \ lib/pid_output.c \ lib/plist.c \ - lib/pqueue.c \ lib/prefix.c \ lib/privs.c \ lib/ptm_lib.c \ @@ -188,7 +187,6 @@ pkginclude_HEADERS += \ lib/openbsd-queue.h \ lib/openbsd-tree.h \ lib/plist.h \ - lib/pqueue.h \ lib/prefix.h \ lib/privs.h \ lib/ptm_lib.h \ diff --git a/tests/lib/cxxcompat.c b/tests/lib/cxxcompat.c index d10962993d..b71361a23d 100644 --- a/tests/lib/cxxcompat.c +++ b/tests/lib/cxxcompat.c @@ -72,7 +72,6 @@ #include "lib/openbsd-tree.h" #include "lib/pbr.h" #include "lib/plist.h" -#include "lib/pqueue.h" #include "lib/prefix.h" #include "lib/privs.h" #include "lib/ptm_lib.h" diff --git a/tests/lib/test_timer_correctness.c b/tests/lib/test_timer_correctness.c index 43e79ba9d0..cbf9b05546 100644 --- a/tests/lib/test_timer_correctness.c +++ b/tests/lib/test_timer_correctness.c @@ -28,7 +28,6 @@ #include #include "memory.h" -#include "pqueue.h" #include "prng.h" #include "thread.h" diff --git a/tests/lib/test_timer_performance.c b/tests/lib/test_timer_performance.c index d5f4badc85..2960e0d81e 100644 --- a/tests/lib/test_timer_performance.c +++ b/tests/lib/test_timer_performance.c @@ -28,7 +28,6 @@ #include #include "thread.h" -#include "pqueue.h" #include "prng.h" #define SCHEDULE_TIMERS 1000000 -- cgit v1.2.3 From 4bef0ec4fbe97c7865f1de676d22832344167bab Mon Sep 17 00:00:00 2001 From: David Lamparter Date: Mon, 4 Feb 2019 01:22:03 +0100 Subject: isisd: replace dict_* with DECLARE_RBTREE Historically, isisd has been carrying around its own red-black tree to manage its LSP DB in. This replaces that with the newly-added DECLARE_RBTREE_*. This allows completely removing the dict_* code. Signed-off-by: David Lamparter --- debian/copyright | 13 - isisd/dict.c | 1510 ----------------------------------------- isisd/dict.h | 121 ---- isisd/isis_adjacency.c | 1 - isisd/isis_bpf.c | 1 - isisd/isis_circuit.c | 10 +- isisd/isis_csm.c | 1 - isisd/isis_dlpi.c | 1 - isisd/isis_dr.c | 1 - isisd/isis_dynhn.c | 1 - isisd/isis_events.c | 1 - isisd/isis_lsp.c | 297 ++++---- isisd/isis_lsp.h | 31 +- isisd/isis_main.c | 1 - isisd/isis_misc.c | 1 - isisd/isis_northbound.c | 1 - isisd/isis_pdu.c | 40 +- isisd/isis_pfpacket.c | 1 - isisd/isis_redist.c | 1 - isisd/isis_route.c | 1 - isisd/isis_routemap.c | 1 - isisd/isis_spf.c | 13 +- isisd/isis_spf_private.h | 4 +- isisd/isis_te.c | 1 - isisd/isis_tlvs.c | 28 +- isisd/isis_tlvs.h | 5 +- isisd/isis_tx_queue.c | 1 - isisd/isis_vty_fabricd.c | 10 +- isisd/isis_zebra.c | 1 - isisd/isisd.c | 47 +- isisd/isisd.h | 6 +- isisd/subdir.am | 2 - tests/isisd/test_isis_lspdb.c | 17 +- 33 files changed, 222 insertions(+), 1949 deletions(-) delete mode 100644 isisd/dict.c delete mode 100644 isisd/dict.h (limited to 'tests') diff --git a/debian/copyright b/debian/copyright index 61d87260d8..d1f28a65a2 100644 --- a/debian/copyright +++ b/debian/copyright @@ -324,19 +324,6 @@ Copyright: Copyright (c) 2006, 2007 Pierre-Yves Ritschard Copyright (c) 2006, 2007, 2008 Reyk Floeter -Files: isisd/dict.* -Copyright: Copyright (C) 1997 Kaz Kylheku -License: custom-BSD-like - All rights are reserved by the author, with the following exceptions: - Permission is granted to freely reproduce and distribute this software, - possibly in exchange for a fee, provided that this copyright notice appears - intact. Permission is also granted to adapt this software to produce - derivative works, as long as the modified versions carry this copyright - notice and additional notices stating that the work has been modified. - This source code may be translated into executable form and incorporated - into proprietary software; there is no requirement for such software to - contain a copyright notice related to this source. - Files: qpb/qpb.proto fpm/fpm.proto License: ISC Copyright: Copyright (C) 2016 Sproute Networks, Inc. diff --git a/isisd/dict.c b/isisd/dict.c deleted file mode 100644 index d91f05d254..0000000000 --- a/isisd/dict.c +++ /dev/null @@ -1,1510 +0,0 @@ -/* - * Dictionary Abstract Data Type - * Copyright (C) 1997 Kaz Kylheku - * - * Free Software License: - * - * All rights are reserved by the author, with the following exceptions: - * Permission is granted to freely reproduce and distribute this software, - * possibly in exchange for a fee, provided that this copyright notice appears - * intact. Permission is also granted to adapt this software to produce - * derivative works, as long as the modified versions carry this copyright - * notice and additional notices stating that the work has been modified. - * This source code may be translated into executable form and incorporated - * into proprietary software; there is no requirement for such software to - * contain a copyright notice related to this source. - */ - -#include "zebra.h" -#include "zassert.h" -#include "memory.h" -#include "isis_memory.h" -#include "dict.h" - -/* - * These macros provide short convenient names for structure members, - * which are embellished with dict_ prefixes so that they are - * properly confined to the documented namespace. It's legal for a - * program which uses dict to define, for instance, a macro called ``parent''. - * Such a macro would interfere with the dnode_t struct definition. - * In general, highly portable and reusable C modules which expose their - * structures need to confine structure member names to well-defined spaces. - * The resulting identifiers aren't necessarily convenient to use, nor - * readable, in the implementation, however! - */ - -#define left dict_left -#define right dict_right -#define parent dict_parent -#define color dict_color -#define key dict_key -#define data dict_data - -#define nilnode dict_nilnode -#define nodecount dict_nodecount -#define maxcount dict_maxcount -#define compare dict_compare -#define allocnode dict_allocnode -#define freenode dict_freenode -#define context dict_context -#define dupes dict_dupes - -#define dictptr dict_dictptr - -#define dict_root(D) ((D)->nilnode.left) -#define dict_nil(D) (&(D)->nilnode) -#define DICT_DEPTH_MAX 64 - -static dnode_t *dnode_alloc(void *context); -static void dnode_free(dnode_t *node, void *context); - -/* - * Perform a ``left rotation'' adjustment on the tree. The given node P and - * its right child C are rearranged so that the P instead becomes the left - * child of C. The left subtree of C is inherited as the new right subtree - * for P. The ordering of the keys within the tree is thus preserved. - */ - -static void rotate_left(dnode_t *upper) -{ - dnode_t *lower, *lowleft, *upparent; - - lower = upper->right; - upper->right = lowleft = lower->left; - lowleft->parent = upper; - - lower->parent = upparent = upper->parent; - - /* don't need to check for root node here because root->parent is - the sentinel nil node, and root->parent->left points back to root */ - - if (upper == upparent->left) { - upparent->left = lower; - } else { - assert(upper == upparent->right); - upparent->right = lower; - } - - lower->left = upper; - upper->parent = lower; -} - -/* - * This operation is the ``mirror'' image of rotate_left. It is - * the same procedure, but with left and right interchanged. - */ - -static void rotate_right(dnode_t *upper) -{ - dnode_t *lower, *lowright, *upparent; - - lower = upper->left; - upper->left = lowright = lower->right; - lowright->parent = upper; - - lower->parent = upparent = upper->parent; - - if (upper == upparent->right) { - upparent->right = lower; - } else { - assert(upper == upparent->left); - upparent->left = lower; - } - - lower->right = upper; - upper->parent = lower; -} - -/* - * Do a postorder traversal of the tree rooted at the specified - * node and free everything under it. Used by dict_free(). - */ - -static void free_nodes(dict_t *dict, dnode_t *node, dnode_t *nil) -{ - if (node == nil) - return; - free_nodes(dict, node->left, nil); - free_nodes(dict, node->right, nil); - dict->freenode(node, dict->context); -} - -/* - * This procedure performs a verification that the given subtree is a binary - * search tree. It performs an inorder traversal of the tree using the - * dict_next() successor function, verifying that the key of each node is - * strictly lower than that of its successor, if duplicates are not allowed, - * or lower or equal if duplicates are allowed. This function is used for - * debugging purposes. - */ - -static int verify_bintree(dict_t *dict) -{ - dnode_t *first, *next; - - first = dict_first(dict); - - if (dict->dupes) { - while (first && (next = dict_next(dict, first))) { - if (dict->compare(first->key, next->key) > 0) - return 0; - first = next; - } - } else { - while (first && (next = dict_next(dict, first))) { - if (dict->compare(first->key, next->key) >= 0) - return 0; - first = next; - } - } - return 1; -} - - -/* - * This function recursively verifies that the given binary subtree satisfies - * three of the red black properties. It checks that every red node has only - * black children. It makes sure that each node is either red or black. And it - * checks that every path has the same count of black nodes from root to leaf. - * It returns the blackheight of the given subtree; this allows blackheights to - * be computed recursively and compared for left and right siblings for - * mismatches. It does not check for every nil node being black, because there - * is only one sentinel nil node. The return value of this function is the - * black height of the subtree rooted at the node ``root'', or zero if the - * subtree is not red-black. - */ - -#ifdef EXTREME_DICT_DEBUG -static unsigned int verify_redblack(dnode_t *nil, dnode_t *root) -{ - unsigned height_left, height_right; - - if (root != nil) { - height_left = verify_redblack(nil, root->left); - height_right = verify_redblack(nil, root->right); - if (height_left == 0 || height_right == 0) - return 0; - if (height_left != height_right) - return 0; - if (root->color == dnode_red) { - if (root->left->color != dnode_black) - return 0; - if (root->right->color != dnode_black) - return 0; - return height_left; - } - if (root->color != dnode_black) - return 0; - return height_left + 1; - } - return 1; -} -#endif - -/* - * Compute the actual count of nodes by traversing the tree and - * return it. This could be compared against the stored count to - * detect a mismatch. - */ - -#ifdef EXTREME_DICT_DEBUG -static dictcount_t verify_node_count(dnode_t *nil, dnode_t *root) -{ - if (root == nil) - return 0; - else - return 1 + verify_node_count(nil, root->left) - + verify_node_count(nil, root->right); -} -#endif - -/* - * Verify that the tree contains the given node. This is done by - * traversing all of the nodes and comparing their pointers to the - * given pointer. Returns 1 if the node is found, otherwise - * returns zero. It is intended for debugging purposes. - */ - -static int verify_dict_has_node(dnode_t *nil, dnode_t *root, dnode_t *node) -{ - if (root != nil) { - return root == node - || verify_dict_has_node(nil, root->left, node) - || verify_dict_has_node(nil, root->right, node); - } - return 0; -} - - -/* - * Dynamically allocate and initialize a dictionary object. - */ - -dict_t *dict_create(dictcount_t maxcount, dict_comp_t comp) -{ - dict_t *new = XCALLOC(MTYPE_ISIS_DICT, sizeof(dict_t)); - - new->compare = comp; - new->allocnode = dnode_alloc; - new->freenode = dnode_free; - new->context = NULL; - new->nodecount = 0; - new->maxcount = maxcount; - new->nilnode.left = &new->nilnode; - new->nilnode.right = &new->nilnode; - new->nilnode.parent = &new->nilnode; - new->nilnode.color = dnode_black; - new->dupes = 0; - - return new; -} - -/* - * Select a different set of node allocator routines. - */ - -void dict_set_allocator(dict_t *dict, dnode_alloc_t al, dnode_free_t fr, - void *context) -{ - assert(dict_count(dict) == 0); - assert((al == NULL && fr == NULL) || (al != NULL && fr != NULL)); - - dict->allocnode = al ? al : dnode_alloc; - dict->freenode = fr ? fr : dnode_free; - dict->context = context; -} - -/* - * Free a dynamically allocated dictionary object. Removing the nodes - * from the tree before deleting it is required. - */ - -void dict_destroy(dict_t *dict) -{ - assert(dict_isempty(dict)); - XFREE(MTYPE_ISIS_DICT, dict); -} - -/* - * Free all the nodes in the dictionary by using the dictionary's - * installed free routine. The dictionary is emptied. - */ - -void dict_free_nodes(dict_t *dict) -{ - dnode_t *nil = dict_nil(dict), *root = dict_root(dict); - free_nodes(dict, root, nil); - dict->nodecount = 0; - dict->nilnode.left = &dict->nilnode; - dict->nilnode.right = &dict->nilnode; -} - -/* - * Obsolescent function, equivalent to dict_free_nodes - */ - -void dict_free(dict_t *dict) -{ - dict_free_nodes(dict); -} - -/* - * Initialize a user-supplied dictionary object. - */ - -dict_t *dict_init(dict_t *dict, dictcount_t maxcount, dict_comp_t comp) -{ - dict->compare = comp; - dict->allocnode = dnode_alloc; - dict->freenode = dnode_free; - dict->context = NULL; - dict->nodecount = 0; - dict->maxcount = maxcount; - dict->nilnode.left = &dict->nilnode; - dict->nilnode.right = &dict->nilnode; - dict->nilnode.parent = &dict->nilnode; - dict->nilnode.color = dnode_black; - dict->dupes = 0; - return dict; -} - -/* - * Initialize a dictionary in the likeness of another dictionary - */ - -void dict_init_like(dict_t *dict, const dict_t *template) -{ - dict->compare = template->compare; - dict->allocnode = template->allocnode; - dict->freenode = template->freenode; - dict->context = template->context; - dict->nodecount = 0; - dict->maxcount = template->maxcount; - dict->nilnode.left = &dict->nilnode; - dict->nilnode.right = &dict->nilnode; - dict->nilnode.parent = &dict->nilnode; - dict->nilnode.color = dnode_black; - dict->dupes = template->dupes; - - assert(dict_similar(dict, template)); -} - -/* - * Remove all nodes from the dictionary (without freeing them in any way). - */ - -static void dict_clear(dict_t *dict) -{ - dict->nodecount = 0; - dict->nilnode.left = &dict->nilnode; - dict->nilnode.right = &dict->nilnode; - dict->nilnode.parent = &dict->nilnode; - assert(dict->nilnode.color == dnode_black); -} - - -/* - * Verify the integrity of the dictionary structure. This is provided for - * debugging purposes, and should be placed in assert statements. Just because - * this function succeeds doesn't mean that the tree is not corrupt. Certain - * corruptions in the tree may simply cause undefined behavior. - */ - -int dict_verify(dict_t *dict) -{ -#ifdef EXTREME_DICT_DEBUG - dnode_t *nil = dict_nil(dict), *root = dict_root(dict); - - /* check that the sentinel node and root node are black */ - if (root->color != dnode_black) - return 0; - if (nil->color != dnode_black) - return 0; - if (nil->right != nil) - return 0; - /* nil->left is the root node; check that its parent pointer is nil */ - if (nil->left->parent != nil) - return 0; - /* perform a weak test that the tree is a binary search tree */ - if (!verify_bintree(dict)) - return 0; - /* verify that the tree is a red-black tree */ - if (!verify_redblack(nil, root)) - return 0; - if (verify_node_count(nil, root) != dict_count(dict)) - return 0; -#endif - return 1; -} - -/* - * Determine whether two dictionaries are similar: have the same comparison and - * allocator functions, and same status as to whether duplicates are allowed. - */ - -int dict_similar(const dict_t *left, const dict_t *right) -{ - if (left->compare != right->compare) - return 0; - - if (left->allocnode != right->allocnode) - return 0; - - if (left->freenode != right->freenode) - return 0; - - if (left->context != right->context) - return 0; - - if (left->dupes != right->dupes) - return 0; - - return 1; -} - -/* - * Locate a node in the dictionary having the given key. - * If the node is not found, a null a pointer is returned (rather than - * a pointer that dictionary's nil sentinel node), otherwise a pointer to the - * located node is returned. - */ - -dnode_t *dict_lookup(dict_t *dict, const void *key) -{ - dnode_t *root = dict_root(dict); - dnode_t *nil = dict_nil(dict); - dnode_t *saved; - int result; - - /* simple binary search adapted for trees that contain duplicate keys */ - - while (root != nil) { - result = dict->compare(key, root->key); - if (result < 0) - root = root->left; - else if (result > 0) - root = root->right; - else { - if (!dict->dupes) { /* no duplicates, return match - */ - return root; - } else { /* could be dupes, find leftmost one */ - do { - saved = root; - root = root->left; - while (root != nil - && dict->compare(key, root->key)) - root = root->right; - } while (root != nil); - return saved; - } - } - } - - return NULL; -} - -/* - * Look for the node corresponding to the lowest key that is equal to or - * greater than the given key. If there is no such node, return null. - */ - -dnode_t *dict_lower_bound(dict_t *dict, const void *key) -{ - dnode_t *root = dict_root(dict); - dnode_t *nil = dict_nil(dict); - dnode_t *tentative = 0; - - while (root != nil) { - int result = dict->compare(key, root->key); - - if (result > 0) { - root = root->right; - } else if (result < 0) { - tentative = root; - root = root->left; - } else { - if (!dict->dupes) { - return root; - } else { - tentative = root; - root = root->left; - } - } - } - - return tentative; -} - -/* - * Look for the node corresponding to the greatest key that is equal to or - * lower than the given key. If there is no such node, return null. - */ - -dnode_t *dict_upper_bound(dict_t *dict, const void *key) -{ - dnode_t *root = dict_root(dict); - dnode_t *nil = dict_nil(dict); - dnode_t *tentative = 0; - - while (root != nil) { - int result = dict->compare(key, root->key); - - if (result < 0) { - root = root->left; - } else if (result > 0) { - tentative = root; - root = root->right; - } else { - if (!dict->dupes) { - return root; - } else { - tentative = root; - root = root->right; - } - } - } - - return tentative; -} - -/* - * Insert a node into the dictionary. The node should have been - * initialized with a data field. All other fields are ignored. - * The behavior is undefined if the user attempts to insert into - * a dictionary that is already full (for which the dict_isfull() - * function returns true). - */ - -void dict_insert(dict_t *dict, dnode_t *node, const void *key) -{ - dnode_t *where = dict_root(dict), *nil = dict_nil(dict); - dnode_t *parent = nil, *uncle, *grandpa; - int result = -1; - - node->key = key; - - assert(!dict_isfull(dict)); - assert(!dict_contains(dict, node)); - assert(!dnode_is_in_a_dict(node)); - - /* basic binary tree insert */ - - while (where != nil) { - parent = where; - result = dict->compare(key, where->key); - /* trap attempts at duplicate key insertion unless it's - * explicitly allowed */ - assert(dict->dupes || result != 0); - if (result < 0) - where = where->left; - else - where = where->right; - } - - assert(where == nil); - - if (result < 0) - parent->left = node; - else - parent->right = node; - - node->parent = parent; - node->left = nil; - node->right = nil; - - dict->nodecount++; - - /* red black adjustments */ - - node->color = dnode_red; - - while (parent->color == dnode_red) { - grandpa = parent->parent; - if (parent == grandpa->left) { - uncle = grandpa->right; - if (uncle->color - == dnode_red) { /* red parent, red uncle */ - parent->color = dnode_black; - uncle->color = dnode_black; - grandpa->color = dnode_red; - node = grandpa; - parent = grandpa->parent; - } else { /* red parent, black uncle */ - if (node == parent->right) { - rotate_left(parent); - parent = node; - assert(grandpa == parent->parent); - /* rotation between parent and child - * preserves grandpa */ - } - parent->color = dnode_black; - grandpa->color = dnode_red; - rotate_right(grandpa); - break; - } - } else { /* symmetric cases: parent == parent->parent->right */ - uncle = grandpa->left; - if (uncle->color == dnode_red) { - parent->color = dnode_black; - uncle->color = dnode_black; - grandpa->color = dnode_red; - node = grandpa; - parent = grandpa->parent; - } else { - if (node == parent->left) { - rotate_right(parent); - parent = node; - assert(grandpa == parent->parent); - } - parent->color = dnode_black; - grandpa->color = dnode_red; - rotate_left(grandpa); - break; - } - } - } - - dict_root(dict)->color = dnode_black; - - assert(dict_verify(dict)); -} - -/* - * Delete the given node from the dictionary. If the given node does not belong - * to the given dictionary, undefined behavior results. A pointer to the - * deleted node is returned. - */ - -dnode_t *dict_delete(dict_t *dict, dnode_t *delete) -{ - dnode_t *nil = dict_nil(dict), *child, *delparent = delete->parent; - - /* basic deletion */ - - assert(!dict_isempty(dict)); - assert(dict_contains(dict, delete)); - - /* - * If the node being deleted has two children, then we replace it with - * its - * successor (i.e. the leftmost node in the right subtree.) By doing - * this, - * we avoid the traditional algorithm under which the successor's key - * and - * value *only* move to the deleted node and the successor is spliced - * out - * from the tree. We cannot use this approach because the user may hold - * pointers to the successor, or nodes may be inextricably tied to some - * other structures by way of embedding, etc. So we must splice out the - * node we are given, not some other node, and must not move contents - * from - * one node to another behind the user's back. - */ - - if (delete->left != nil && delete->right != nil) { - dnode_t *next = dict_next(dict, delete); - assert(next); - dnode_t *nextparent = next->parent; - dnode_color_t nextcolor = next->color; - - assert(next != nil); - assert(next->parent != nil); - assert(next->left == nil); - - /* - * First, splice out the successor from the tree completely, by - * moving up its right child into its place. - */ - - child = next->right; - child->parent = nextparent; - - if (nextparent->left == next) { - nextparent->left = child; - } else { - assert(nextparent->right == next); - nextparent->right = child; - } - - /* - * Now that the successor has been extricated from the tree, - * install it - * in place of the node that we want deleted. - */ - - next->parent = delparent; - next->left = delete->left; - next->right = delete->right; - next->left->parent = next; - next->right->parent = next; - next->color = delete->color; - delete->color = nextcolor; - - if (delparent->left == delete) { - delparent->left = next; - } else { - assert(delparent->right == delete); - delparent->right = next; - } - - } else { - assert(delete != nil); - assert(delete->left == nil || delete->right == nil); - - child = (delete->left != nil) ? delete->left : delete->right; - - child->parent = delparent = delete->parent; - - if (delete == delparent->left) { - delparent->left = child; - } else { - assert(delete == delparent->right); - delparent->right = child; - } - } - - delete->parent = NULL; - delete->right = NULL; - delete->left = NULL; - - dict->nodecount--; - - assert(verify_bintree(dict)); - - /* red-black adjustments */ - - if (delete->color == dnode_black) { - dnode_t *parent, *sister; - - dict_root(dict)->color = dnode_red; - - while (child->color == dnode_black) { - parent = child->parent; - if (child == parent->left) { - sister = parent->right; - assert(sister != nil); - if (sister->color == dnode_red) { - sister->color = dnode_black; - parent->color = dnode_red; - rotate_left(parent); - sister = parent->right; - assert(sister != nil); - } - if (sister->left->color == dnode_black - && sister->right->color == dnode_black) { - sister->color = dnode_red; - child = parent; - } else { - if (sister->right->color - == dnode_black) { - assert(sister->left->color - == dnode_red); - sister->left->color = - dnode_black; - sister->color = dnode_red; - rotate_right(sister); - sister = parent->right; - assert(sister != nil); - } - sister->color = parent->color; - sister->right->color = dnode_black; - parent->color = dnode_black; - rotate_left(parent); - break; - } - } else { /* symmetric case: child == - child->parent->right */ - assert(child == parent->right); - sister = parent->left; - assert(sister != nil); - if (sister->color == dnode_red) { - sister->color = dnode_black; - parent->color = dnode_red; - rotate_right(parent); - sister = parent->left; - assert(sister != nil); - } - if (sister->right->color == dnode_black - && sister->left->color == dnode_black) { - sister->color = dnode_red; - child = parent; - } else { - if (sister->left->color - == dnode_black) { - assert(sister->right->color - == dnode_red); - sister->right->color = - dnode_black; - sister->color = dnode_red; - rotate_left(sister); - sister = parent->left; - assert(sister != nil); - } - sister->color = parent->color; - sister->left->color = dnode_black; - parent->color = dnode_black; - rotate_right(parent); - break; - } - } - } - - child->color = dnode_black; - dict_root(dict)->color = dnode_black; - } - - assert(dict_verify(dict)); - - return delete; -} - -/* - * Allocate a node using the dictionary's allocator routine, give it - * the data item. - */ - -int dict_alloc_insert(dict_t *dict, const void *key, void *data) -{ - dnode_t *node = dict->allocnode(dict->context); - - if (node) { - dnode_init(node, data); - dict_insert(dict, node, key); - return 1; - } - return 0; -} - -void dict_delete_free(dict_t *dict, dnode_t *node) -{ - dict_delete(dict, node); - dict->freenode(node, dict->context); -} - -/* - * Return the node with the lowest (leftmost) key. If the dictionary is empty - * (that is, dict_isempty(dict) returns 1) a null pointer is returned. - */ - -dnode_t *dict_first(dict_t *dict) -{ - dnode_t *nil = dict_nil(dict), *root = dict_root(dict), *left; - - if (root != nil) - while ((left = root->left) != nil) - root = left; - - return (root == nil) ? NULL : root; -} - -/* - * Return the node with the highest (rightmost) key. If the dictionary is empty - * (that is, dict_isempty(dict) returns 1) a null pointer is returned. - */ - -dnode_t *dict_last(dict_t *dict) -{ - dnode_t *nil = dict_nil(dict), *root = dict_root(dict), *right; - - if (root != nil) - while ((right = root->right) != nil) - root = right; - - return (root == nil) ? NULL : root; -} - -/* - * Return the given node's successor node---the node which has the - * next key in the the left to right ordering. If the node has - * no successor, a null pointer is returned rather than a pointer to - * the nil node. - */ - -dnode_t *dict_next(dict_t *dict, dnode_t *curr) -{ - dnode_t *nil = dict_nil(dict), *parent, *left; - - if (curr->right != nil) { - curr = curr->right; - while ((left = curr->left) != nil) - curr = left; - return curr; - } - - parent = curr->parent; - - while (parent != nil && curr == parent->right) { - curr = parent; - parent = curr->parent; - } - - return (parent == nil) ? NULL : parent; -} - -/* - * Return the given node's predecessor, in the key order. - * The nil sentinel node is returned if there is no predecessor. - */ - -dnode_t *dict_prev(dict_t *dict, dnode_t *curr) -{ - dnode_t *nil = dict_nil(dict), *parent, *right; - - if (curr->left != nil) { - curr = curr->left; - while ((right = curr->right) != nil) - curr = right; - return curr; - } - - parent = curr->parent; - - while (parent != nil && curr == parent->left) { - curr = parent; - parent = curr->parent; - } - - return (parent == nil) ? NULL : parent; -} - -void dict_allow_dupes(dict_t *dict) -{ - dict->dupes = 1; -} - -#undef dict_count -#undef dict_isempty -#undef dict_isfull -#undef dnode_get -#undef dnode_put -#undef dnode_getkey - -dictcount_t dict_count(dict_t *dict) -{ - return dict->nodecount; -} - -int dict_isempty(dict_t *dict) -{ - return dict->nodecount == 0; -} - -int dict_isfull(dict_t *dict) -{ - return dict->nodecount == dict->maxcount; -} - -int dict_contains(dict_t *dict, dnode_t *node) -{ - return verify_dict_has_node(dict_nil(dict), dict_root(dict), node); -} - -static dnode_t *dnode_alloc(void *context) -{ - return XCALLOC(MTYPE_ISIS_DICT_NODE, sizeof(dnode_t)); -} - -static void dnode_free(dnode_t *node, void *context) -{ - XFREE(MTYPE_ISIS_DICT_NODE, node); -} - -dnode_t *dnode_create(void *data) -{ - dnode_t *new = XCALLOC(MTYPE_ISIS_DICT_NODE, sizeof(dnode_t)); - - new->data = data; - new->parent = NULL; - new->left = NULL; - new->right = NULL; - - return new; -} - -dnode_t *dnode_init(dnode_t *dnode, void *data) -{ - dnode->data = data; - dnode->parent = NULL; - dnode->left = NULL; - dnode->right = NULL; - return dnode; -} - -void dnode_destroy(dnode_t *dnode) -{ - assert(!dnode_is_in_a_dict(dnode)); - XFREE(MTYPE_ISIS_DICT_NODE, dnode); -} - -void *dnode_get(dnode_t *dnode) -{ - return dnode->data; -} - -const void *dnode_getkey(dnode_t *dnode) -{ - return dnode->key; -} - -void dnode_put(dnode_t *dnode, void *data) -{ - dnode->data = data; -} - -int dnode_is_in_a_dict(dnode_t *dnode) -{ - return (dnode->parent && dnode->left && dnode->right); -} - -void dict_process(dict_t *dict, void *context, dnode_process_t function) -{ - dnode_t *node = dict_first(dict), *next; - - while (node != NULL) { - /* check for callback function deleting */ - /* the next node from under us */ - assert(dict_contains(dict, node)); - next = dict_next(dict, node); - function(dict, node, context); - node = next; - } -} - -static void load_begin_internal(dict_load_t *load, dict_t *dict) -{ - load->dictptr = dict; - load->nilnode.left = &load->nilnode; - load->nilnode.right = &load->nilnode; -} - -void dict_load_begin(dict_load_t *load, dict_t *dict) -{ - assert(dict_isempty(dict)); - load_begin_internal(load, dict); -} - -void dict_load_next(dict_load_t *load, dnode_t *newnode, const void *key) -{ - dict_t *dict = load->dictptr; - dnode_t *nil = &load->nilnode; - - assert(!dnode_is_in_a_dict(newnode)); - assert(dict->nodecount < dict->maxcount); - -#ifndef NDEBUG - if (dict->nodecount > 0) { - if (dict->dupes) - assert(dict->compare(nil->left->key, key) <= 0); - else - assert(dict->compare(nil->left->key, key) < 0); - } -#endif - - newnode->key = key; - nil->right->left = newnode; - nil->right = newnode; - newnode->left = nil; - dict->nodecount++; -} - -void dict_load_end(dict_load_t *load) -{ - dict_t *dict = load->dictptr; - dnode_t *tree[DICT_DEPTH_MAX] = {0}; - dnode_t *curr, *dictnil = dict_nil(dict), *loadnil = &load->nilnode, - *next; - dnode_t *complete = 0; - dictcount_t fullcount = DICTCOUNT_T_MAX, nodecount = dict->nodecount; - dictcount_t botrowcount; - unsigned baselevel = 0, level = 0, i; - - assert(dnode_red == 0 && dnode_black == 1); - - while (fullcount >= nodecount && fullcount) - fullcount >>= 1; - - botrowcount = nodecount - fullcount; - - for (curr = loadnil->left; curr != loadnil; curr = next) { - next = curr->left; - - if (complete == NULL && botrowcount-- == 0) { - assert(baselevel == 0); - assert(level == 0); - baselevel = level = 1; - complete = tree[0]; - - if (complete != NULL) { - tree[0] = 0; - complete->right = dictnil; - while (tree[level] != NULL) { - tree[level]->right = complete; - complete->parent = tree[level]; - complete = tree[level]; - tree[level++] = 0; - } - } - } - - if (complete == NULL) { - curr->left = dictnil; - curr->right = dictnil; - curr->color = level % 2; - complete = curr; - - assert(level == baselevel); - while (tree[level] != NULL) { - tree[level]->right = complete; - complete->parent = tree[level]; - complete = tree[level]; - tree[level++] = 0; - } - } else { - curr->left = complete; - curr->color = (level + 1) % 2; - complete->parent = curr; - tree[level] = curr; - complete = 0; - level = baselevel; - } - } - - if (complete == NULL) - complete = dictnil; - - for (i = 0; i < DICT_DEPTH_MAX; i++) { - if (tree[i] != NULL) { - tree[i]->right = complete; - complete->parent = tree[i]; - complete = tree[i]; - } - } - - dictnil->color = dnode_black; - dictnil->right = dictnil; - complete->parent = dictnil; - complete->color = dnode_black; - dict_root(dict) = complete; - - assert(dict_verify(dict)); -} - -void dict_merge(dict_t *dest, dict_t *source) -{ - dict_load_t load; - dnode_t *leftnode = dict_first(dest), *rightnode = dict_first(source); - - assert(dict_similar(dest, source)); - - if (source == dest) - return; - - dest->nodecount = 0; - load_begin_internal(&load, dest); - - for (;;) { - if (leftnode != NULL && rightnode != NULL) { - if (dest->compare(leftnode->key, rightnode->key) < 0) - goto copyleft; - else - goto copyright; - } else if (leftnode != NULL) { - goto copyleft; - } else if (rightnode != NULL) { - goto copyright; - } else { - assert(leftnode == NULL && rightnode == NULL); - break; - } - - copyleft : { - dnode_t *next = dict_next(dest, leftnode); -#ifndef NDEBUG - leftnode->left = - NULL; /* suppress assertion in dict_load_next */ -#endif - dict_load_next(&load, leftnode, leftnode->key); - leftnode = next; - continue; - } - - copyright : { - dnode_t *next = dict_next(source, rightnode); -#ifndef NDEBUG - rightnode->left = NULL; -#endif - dict_load_next(&load, rightnode, rightnode->key); - rightnode = next; - continue; - } - } - - dict_clear(source); - dict_load_end(&load); -} - -#ifdef KAZLIB_TEST_MAIN - -#include -#include -#include -#include - -typedef char input_t[256]; - -static int tokenize(char *string, ...) -{ - char **tokptr; - va_list arglist; - int tokcount = 0; - - va_start(arglist, string); - tokptr = va_arg(arglist, char **); - while (tokptr) { - while (*string && isspace((unsigned char)*string)) - string++; - if (!*string) - break; - *tokptr = string; - while (*string && !isspace((unsigned char)*string)) - string++; - tokptr = va_arg(arglist, char **); - tokcount++; - if (!*string) - break; - *string++ = 0; - } - va_end(arglist); - - return tokcount; -} - -static int comparef(const void *key1, const void *key2) -{ - return strcmp(key1, key2); -} - -static char *dupstring(char *str) -{ - int sz = strlen(str) + 1; - char *new = XCALLOC(MTYPE_ISIS_TMP, sz); - - memcpy(new, str, sz); - return new; -} - -static dnode_t *new_node(void *c) -{ - static dnode_t few[5]; - static int count; - - if (count < 5) - return few + count++; - - return NULL; -} - -static void del_node(dnode_t *n, void *c) -{ -} - -static int prompt = 0; - -static void construct(dict_t *d) -{ - input_t in; - int done = 0; - dict_load_t dl; - dnode_t *dn; - char *tok1, *tok2, *val; - const char *key; - char *help = - "p turn prompt on\n" - "q finish construction\n" - "a add new entry\n"; - - if (!dict_isempty(d)) - puts("warning: dictionary not empty!"); - - dict_load_begin(&dl, d); - - while (!done) { - if (prompt) - putchar('>'); - fflush(stdout); - - if (!fgets(in, sizeof(input_t), stdin)) - break; - - switch (in[0]) { - case '?': - puts(help); - break; - case 'p': - prompt = 1; - break; - case 'q': - done = 1; - break; - case 'a': - if (tokenize(in + 1, &tok1, &tok2, (char **)0) != 2) { - puts("what?"); - break; - } - key = dupstring(tok1); - val = dupstring(tok2); - dn = dnode_create(val); - - if (!key || !val || !dn) { - puts("out of memory"); - free((void *)key); - free(val); - if (dn) - dnode_destroy(dn); - } else - dict_load_next(&dl, dn, key); - break; - default: - putchar('?'); - putchar('\n'); - break; - } - } - - dict_load_end(&dl); -} - -int main(void) -{ - input_t in; - dict_t darray[10]; - dict_t *d = &darray[0]; - dnode_t *dn; - int i; - char *tok1, *tok2, *val; - const char *key; - - char *help = - "a add value to dictionary\n" - "d delete value from dictionary\n" - "l lookup value in dictionary\n" - "( lookup lower bound\n" - ") lookup upper bound\n" - "# switch to alternate dictionary (0-9)\n" - "j merge two dictionaries\n" - "f free the whole dictionary\n" - "k allow duplicate keys\n" - "c show number of entries\n" - "t dump whole dictionary in sort order\n" - "m make dictionary out of sorted items\n" - "p turn prompt on\n" - "s switch to non-functioning allocator\n" - "q quit"; - - for (i = 0; i < 10; i++) - dict_init(&darray[i], DICTCOUNT_T_MAX, comparef); - - for (;;) { - if (prompt) - putchar('>'); - fflush(stdout); - - if (!fgets(in, sizeof(input_t), stdin)) - break; - - switch (in[0]) { - case '?': - puts(help); - break; - case 'a': - if (tokenize(in + 1, &tok1, &tok2, (char **)0) != 2) { - puts("what?"); - break; - } - key = dupstring(tok1); - val = dupstring(tok2); - - if (!key || !val) { - puts("out of memory"); - free((void *)key); - free(val); - } - - if (!dict_alloc_insert(d, key, val)) { - puts("dict_alloc_insert failed"); - free((void *)key); - free(val); - break; - } - break; - case 'd': - if (tokenize(in + 1, &tok1, (char **)0) != 1) { - puts("what?"); - break; - } - dn = dict_lookup(d, tok1); - if (!dn) { - puts("dict_lookup failed"); - break; - } - val = dnode_get(dn); - key = dnode_getkey(dn); - dict_delete_free(d, dn); - - free(val); - free((void *)key); - break; - case 'f': - dict_free(d); - break; - case 'l': - case '(': - case ')': - if (tokenize(in + 1, &tok1, (char **)0) != 1) { - puts("what?"); - break; - } - dn = 0; - switch (in[0]) { - case 'l': - dn = dict_lookup(d, tok1); - break; - case '(': - dn = dict_lower_bound(d, tok1); - break; - case ')': - dn = dict_upper_bound(d, tok1); - break; - } - if (!dn) { - puts("lookup failed"); - break; - } - val = dnode_get(dn); - puts(val); - break; - case 'm': - construct(d); - break; - case 'k': - dict_allow_dupes(d); - break; - case 'c': - printf("%lu\n", (unsigned long)dict_count(d)); - break; - case 't': - for (dn = dict_first(d); dn; dn = dict_next(d, dn)) { - printf("%s\t%s\n", (char *)dnode_getkey(dn), - (char *)dnode_get(dn)); - } - break; - case 'q': - exit(0); - break; - case '\0': - break; - case 'p': - prompt = 1; - break; - case 's': - dict_set_allocator(d, new_node, del_node, NULL); - break; - case '#': - if (tokenize(in + 1, &tok1, (char **)0) != 1) { - puts("what?"); - break; - } else { - int dictnum = atoi(tok1); - if (dictnum < 0 || dictnum > 9) { - puts("invalid number"); - break; - } - d = &darray[dictnum]; - } - break; - case 'j': - if (tokenize(in + 1, &tok1, &tok2, (char **)0) != 2) { - puts("what?"); - break; - } else { - int dict1 = atoi(tok1), dict2 = atoi(tok2); - if (dict1 < 0 || dict1 > 9 || dict2 < 0 - || dict2 > 9) { - puts("invalid number"); - break; - } - dict_merge(&darray[dict1], &darray[dict2]); - } - break; - default: - putchar('?'); - putchar('\n'); - break; - } - } - - return 0; -} - -#endif diff --git a/isisd/dict.h b/isisd/dict.h deleted file mode 100644 index 32683c57d5..0000000000 --- a/isisd/dict.h +++ /dev/null @@ -1,121 +0,0 @@ -/* - * Dictionary Abstract Data Type - * Copyright (C) 1997 Kaz Kylheku - * - * Free Software License: - * - * All rights are reserved by the author, with the following exceptions: - * Permission is granted to freely reproduce and distribute this software, - * possibly in exchange for a fee, provided that this copyright notice appears - * intact. Permission is also granted to adapt this software to produce - * derivative works, as long as the modified versions carry this copyright - * notice and additional notices stating that the work has been modified. - * This source code may be translated into executable form and incorporated - * into proprietary software; there is no requirement for such software to - * contain a copyright notice related to this source. - * - */ - -#ifndef DICT_H -#define DICT_H - -#include - -/* - * Blurb for inclusion into C++ translation units - */ - -#ifdef __cplusplus -extern "C" { -#endif - -typedef unsigned long dictcount_t; -#define DICTCOUNT_T_MAX ULONG_MAX - -/* - * The dictionary is implemented as a red-black tree - */ - -typedef enum { dnode_red, dnode_black } dnode_color_t; - -typedef struct dnode_t { - struct dnode_t *dict_left; - struct dnode_t *dict_right; - struct dnode_t *dict_parent; - dnode_color_t dict_color; - const void *dict_key; - void *dict_data; -} dnode_t; - -typedef int (*dict_comp_t)(const void *, const void *); -typedef dnode_t *(*dnode_alloc_t)(void *); -typedef void (*dnode_free_t)(dnode_t *, void *); - -typedef struct dict_t { - dnode_t dict_nilnode; - dictcount_t dict_nodecount; - dictcount_t dict_maxcount; - dict_comp_t dict_compare; - dnode_alloc_t dict_allocnode; - dnode_free_t dict_freenode; - void *dict_context; - int dict_dupes; -} dict_t; - -typedef void (*dnode_process_t)(dict_t *, dnode_t *, void *); - -typedef struct dict_load_t { - dict_t *dict_dictptr; - dnode_t dict_nilnode; -} dict_load_t; - -extern dict_t *dict_create(dictcount_t, dict_comp_t); -extern void dict_set_allocator(dict_t *, dnode_alloc_t, dnode_free_t, void *); -extern void dict_destroy(dict_t *); -extern void dict_free_nodes(dict_t *); -extern void dict_free(dict_t *); -extern dict_t *dict_init(dict_t *, dictcount_t, dict_comp_t); -extern void dict_init_like(dict_t *, const dict_t *); -extern int dict_verify(dict_t *); -extern int dict_similar(const dict_t *, const dict_t *); -extern dnode_t *dict_lookup(dict_t *, const void *); -extern dnode_t *dict_lower_bound(dict_t *, const void *); -extern dnode_t *dict_upper_bound(dict_t *, const void *); -extern void dict_insert(dict_t *, dnode_t *, const void *); -extern dnode_t *dict_delete(dict_t *, dnode_t *); -extern int dict_alloc_insert(dict_t *, const void *, void *); -extern void dict_delete_free(dict_t *, dnode_t *); -extern dnode_t *dict_first(dict_t *); -extern dnode_t *dict_last(dict_t *); -extern dnode_t *dict_next(dict_t *, dnode_t *); -extern dnode_t *dict_prev(dict_t *, dnode_t *); -extern dictcount_t dict_count(dict_t *); -extern int dict_isempty(dict_t *); -extern int dict_isfull(dict_t *); -extern int dict_contains(dict_t *, dnode_t *); -extern void dict_allow_dupes(dict_t *); -extern int dnode_is_in_a_dict(dnode_t *); -extern dnode_t *dnode_create(void *); -extern dnode_t *dnode_init(dnode_t *, void *); -extern void dnode_destroy(dnode_t *); -extern void *dnode_get(dnode_t *); -extern const void *dnode_getkey(dnode_t *); -extern void dnode_put(dnode_t *, void *); -extern void dict_process(dict_t *, void *, dnode_process_t); -extern void dict_load_begin(dict_load_t *, dict_t *); -extern void dict_load_next(dict_load_t *, dnode_t *, const void *); -extern void dict_load_end(dict_load_t *); -extern void dict_merge(dict_t *, dict_t *); - -#define dict_isfull(D) ((D)->dict_nodecount == (D)->dict_maxcount) -#define dict_count(D) ((D)->dict_nodecount) -#define dict_isempty(D) ((D)->dict_nodecount == 0) -#define dnode_get(N) ((N)->dict_data) -#define dnode_getkey(N) ((N)->dict_key) -#define dnode_put(N, X) ((N)->dict_data = (X)) - -#ifdef __cplusplus -} -#endif - -#endif diff --git a/isisd/isis_adjacency.c b/isisd/isis_adjacency.c index 62814329ea..9b368cc404 100644 --- a/isisd/isis_adjacency.c +++ b/isisd/isis_adjacency.c @@ -32,7 +32,6 @@ #include "if.h" #include "stream.h" -#include "isisd/dict.h" #include "isisd/isis_constants.h" #include "isisd/isis_common.h" #include "isisd/isis_flags.h" diff --git a/isisd/isis_bpf.c b/isisd/isis_bpf.c index 28750278b0..4e9aef47ad 100644 --- a/isisd/isis_bpf.c +++ b/isisd/isis_bpf.c @@ -34,7 +34,6 @@ #include "if.h" #include "lib_errors.h" -#include "isisd/dict.h" #include "isisd/isis_constants.h" #include "isisd/isis_common.h" #include "isisd/isis_circuit.h" diff --git a/isisd/isis_circuit.c b/isisd/isis_circuit.c index 8377638b92..f9a0285872 100644 --- a/isisd/isis_circuit.c +++ b/isisd/isis_circuit.c @@ -40,7 +40,6 @@ #include "qobj.h" #include "lib/northbound_cli.h" -#include "isisd/dict.h" #include "isisd/isis_constants.h" #include "isisd/isis_common.h" #include "isisd/isis_flags.h" @@ -540,7 +539,6 @@ static void isis_circuit_update_all_srmflags(struct isis_circuit *circuit, { struct isis_area *area; struct isis_lsp *lsp; - dnode_t *dnode; int level; assert(circuit); @@ -550,14 +548,10 @@ static void isis_circuit_update_all_srmflags(struct isis_circuit *circuit, if (!(level & circuit->is_type)) continue; - if (!area->lspdb[level - 1] - || !dict_count(area->lspdb[level - 1])) + if (!lspdb_count(&area->lspdb[level - 1])) continue; - for (dnode = dict_first(area->lspdb[level - 1]); - dnode != NULL; - dnode = dict_next(area->lspdb[level - 1], dnode)) { - lsp = dnode_get(dnode); + for_each (lspdb, &area->lspdb[level - 1], lsp) { if (is_set) { isis_tx_queue_add(circuit->tx_queue, lsp, TX_LSP_NORMAL); diff --git a/isisd/isis_csm.c b/isisd/isis_csm.c index e50f57ae1d..88676dd990 100644 --- a/isisd/isis_csm.c +++ b/isisd/isis_csm.c @@ -32,7 +32,6 @@ #include "prefix.h" #include "stream.h" -#include "isisd/dict.h" #include "isisd/isis_constants.h" #include "isisd/isis_common.h" #include "isisd/isis_flags.h" diff --git a/isisd/isis_dlpi.c b/isisd/isis_dlpi.c index 148b438661..a96dd93804 100644 --- a/isisd/isis_dlpi.c +++ b/isisd/isis_dlpi.c @@ -38,7 +38,6 @@ #include "if.h" #include "lib_errors.h" -#include "isisd/dict.h" #include "isisd/isis_constants.h" #include "isisd/isis_common.h" #include "isisd/isis_circuit.h" diff --git a/isisd/isis_dr.c b/isisd/isis_dr.c index 449648656a..7be5307500 100644 --- a/isisd/isis_dr.c +++ b/isisd/isis_dr.c @@ -32,7 +32,6 @@ #include "stream.h" #include "if.h" -#include "isisd/dict.h" #include "isisd/isis_constants.h" #include "isisd/isis_common.h" #include "isisd/isis_misc.h" diff --git a/isisd/isis_dynhn.c b/isisd/isis_dynhn.c index 1d29d1086d..921e23d33a 100644 --- a/isisd/isis_dynhn.c +++ b/isisd/isis_dynhn.c @@ -31,7 +31,6 @@ #include "if.h" #include "thread.h" -#include "isisd/dict.h" #include "isisd/isis_constants.h" #include "isisd/isis_common.h" #include "isisd/isis_flags.h" diff --git a/isisd/isis_events.c b/isisd/isis_events.c index 4da23c5912..6a5dcfb075 100644 --- a/isisd/isis_events.c +++ b/isisd/isis_events.c @@ -32,7 +32,6 @@ #include "stream.h" #include "table.h" -#include "isisd/dict.h" #include "isisd/isis_constants.h" #include "isisd/isis_common.h" #include "isisd/isis_flags.h" diff --git a/isisd/isis_lsp.c b/isisd/isis_lsp.c index b56a56fa3f..a0be2d82f2 100644 --- a/isisd/isis_lsp.c +++ b/isisd/isis_lsp.c @@ -40,7 +40,6 @@ #include "srcdest_table.h" #include "lib_errors.h" -#include "isisd/dict.h" #include "isisd/isis_constants.h" #include "isisd/isis_common.h" #include "isisd/isis_flags.h" @@ -63,41 +62,38 @@ static int lsp_refresh(struct thread *thread); static int lsp_l1_refresh_pseudo(struct thread *thread); static int lsp_l2_refresh_pseudo(struct thread *thread); +static void lsp_destroy(struct isis_lsp *lsp); + int lsp_id_cmp(uint8_t *id1, uint8_t *id2) { return memcmp(id1, id2, ISIS_SYS_ID_LEN + 2); } -dict_t *lsp_db_init(void) +int lspdb_compare(const struct isis_lsp *a, const struct isis_lsp *b) { - dict_t *dict; - - dict = dict_create(DICTCOUNT_T_MAX, (dict_comp_t)lsp_id_cmp); - - return dict; + return memcmp(a->hdr.lsp_id, b->hdr.lsp_id, sizeof(a->hdr.lsp_id)); } -struct isis_lsp *lsp_search(uint8_t *id, dict_t *lspdb) +void lsp_db_init(struct lspdb_head *head) { - dnode_t *node; - -#ifdef EXTREME_DEBUG - dnode_t *dn; + lspdb_init(head); +} - zlog_debug("searching db"); - for (dn = dict_first(lspdb); dn; dn = dict_next(lspdb, dn)) { - zlog_debug("%s\t%pX", - rawlspid_print((uint8_t *)dnode_getkey(dn)), - dnode_get(dn)); - } -#endif /* EXTREME DEBUG */ +void lsp_db_fini(struct lspdb_head *head) +{ + struct isis_lsp *lsp; - node = dict_lookup(lspdb, id); + while ((lsp = lspdb_pop(head))) + lsp_destroy(lsp); + lspdb_fini(head); +} - if (node) - return (struct isis_lsp *)dnode_get(node); +struct isis_lsp *lsp_search(struct lspdb_head *head, const uint8_t *id) +{ + struct isis_lsp searchfor; + memcpy(searchfor.hdr.lsp_id, id, sizeof(searchfor.hdr.lsp_id)); - return NULL; + return lspdb_find(head, &searchfor); } static void lsp_clear_data(struct isis_lsp *lsp) @@ -109,7 +105,7 @@ static void lsp_clear_data(struct isis_lsp *lsp) lsp->tlvs = NULL; } -static void lsp_remove_frags(struct list *frags, dict_t *lspdb); +static void lsp_remove_frags(struct lspdb_head *head, struct list *frags); static void lsp_destroy(struct isis_lsp *lsp) { @@ -128,8 +124,8 @@ static void lsp_destroy(struct isis_lsp *lsp) if (!LSP_FRAGMENT(lsp->hdr.lsp_id)) { if (lsp->lspu.frags) { - lsp_remove_frags(lsp->lspu.frags, - lsp->area->lspdb[lsp->level - 1]); + lsp_remove_frags(&lsp->area->lspdb[lsp->level - 1], + lsp->lspu.frags); list_delete(&lsp->lspu.frags); } } else { @@ -148,56 +144,34 @@ static void lsp_destroy(struct isis_lsp *lsp) XFREE(MTYPE_ISIS_LSP, lsp); } -void lsp_db_destroy(dict_t *lspdb) -{ - dnode_t *dnode, *next; - struct isis_lsp *lsp; - - dnode = dict_first(lspdb); - while (dnode) { - next = dict_next(lspdb, dnode); - lsp = dnode_get(dnode); - lsp_destroy(lsp); - dict_delete_free(lspdb, dnode); - dnode = next; - } - - dict_free(lspdb); - - return; -} - /* * Remove all the frags belonging to the given lsp */ -static void lsp_remove_frags(struct list *frags, dict_t *lspdb) +static void lsp_remove_frags(struct lspdb_head *head, struct list *frags) { - dnode_t *dnode; struct listnode *lnode, *lnnode; struct isis_lsp *lsp; for (ALL_LIST_ELEMENTS(frags, lnode, lnnode, lsp)) { - dnode = dict_lookup(lspdb, lsp->hdr.lsp_id); + lsp = lsp_search(head, lsp->hdr.lsp_id); + lspdb_del(head, lsp); lsp_destroy(lsp); - dnode_destroy(dict_delete(lspdb, dnode)); } } -void lsp_search_and_destroy(uint8_t *id, dict_t *lspdb) +void lsp_search_and_destroy(struct lspdb_head *head, const uint8_t *id) { - dnode_t *node; struct isis_lsp *lsp; - node = dict_lookup(lspdb, id); - if (node) { - node = dict_delete(lspdb, node); - lsp = dnode_get(node); + lsp = lsp_search(head, id); + if (lsp) { + lspdb_del(head, lsp); /* * If this is a zero lsp, remove all the frags now */ if (LSP_FRAGMENT(lsp->hdr.lsp_id) == 0) { if (lsp->lspu.frags) - lsp_remove_frags(lsp->lspu.frags, lspdb); + lsp_remove_frags(head, lsp->lspu.frags); } else { /* * else just remove this frag, from the zero lsps' frag @@ -209,7 +183,6 @@ void lsp_search_and_destroy(uint8_t *id, dict_t *lspdb) lsp); } lsp_destroy(lsp); - dnode_destroy(node); } } @@ -514,7 +487,7 @@ void lsp_update(struct isis_lsp *lsp, struct isis_lsp_hdr *hdr, memcpy(lspid, lsp->hdr.lsp_id, ISIS_SYS_ID_LEN + 1); LSP_FRAGMENT(lspid) = 0; - lsp0 = lsp_search(lspid, area->lspdb[level - 1]); + lsp0 = lsp_search(&area->lspdb[level - 1], lspid); if (lsp0) lsp_link_fragment(lsp, lsp0); } @@ -582,9 +555,9 @@ struct isis_lsp *lsp_new(struct isis_area *area, uint8_t *lsp_id, return lsp; } -void lsp_insert(struct isis_lsp *lsp, dict_t *lspdb) +void lsp_insert(struct lspdb_head *head, struct isis_lsp *lsp) { - dict_alloc_insert(lspdb, lsp->hdr.lsp_id, lsp); + lspdb_add(head, lsp); if (lsp->hdr.seqno) isis_spf_schedule(lsp->area, lsp->level); } @@ -592,13 +565,16 @@ void lsp_insert(struct isis_lsp *lsp, dict_t *lspdb) /* * Build a list of LSPs with non-zero ht bounded by start and stop ids */ -void lsp_build_list_nonzero_ht(uint8_t *start_id, uint8_t *stop_id, - struct list *list, dict_t *lspdb) +void lsp_build_list_nonzero_ht(struct lspdb_head *head, const uint8_t *start_id, + const uint8_t *stop_id, struct list *list) { - for (dnode_t *curr = dict_lower_bound(lspdb, start_id); - curr; curr = dict_next(lspdb, curr)) { - struct isis_lsp *lsp = curr->dict_data; + struct isis_lsp searchfor; + struct isis_lsp *lsp, *start; + + memcpy(&searchfor.hdr.lsp_id, start_id, sizeof(searchfor.hdr.lsp_id)); + start = lspdb_find_gteq(head, &searchfor); + for_each_from (lspdb, head, lsp, start) { if (memcmp(lsp->hdr.lsp_id, stop_id, ISIS_SYS_ID_LEN + 2) > 0) break; @@ -699,26 +675,20 @@ void lsp_print_detail(struct isis_lsp *lsp, struct vty *vty, char dynhost) } /* print all the lsps info in the local lspdb */ -int lsp_print_all(struct vty *vty, dict_t *lspdb, char detail, char dynhost) +int lsp_print_all(struct vty *vty, struct lspdb_head *head, char detail, + char dynhost) { - - dnode_t *node = dict_first(lspdb), *next; + struct isis_lsp *lsp; int lsp_count = 0; if (detail == ISIS_UI_LEVEL_BRIEF) { - while (node != NULL) { - /* I think it is unnecessary, so I comment it out */ - /* dict_contains (lspdb, node); */ - next = dict_next(lspdb, node); - lsp_print(dnode_get(node), vty, dynhost); - node = next; + for_each (lspdb, head, lsp) { + lsp_print(lsp, vty, dynhost); lsp_count++; } } else if (detail == ISIS_UI_LEVEL_DETAIL) { - while (node != NULL) { - next = dict_next(lspdb, node); - lsp_print_detail(dnode_get(node), vty, dynhost); - node = next; + for_each (lspdb, head, lsp) { + lsp_print_detail(lsp, vty, dynhost); lsp_count++; } } @@ -847,7 +817,7 @@ static struct isis_lsp *lsp_next_frag(uint8_t frag_num, struct isis_lsp *lsp0, memcpy(frag_id, lsp0->hdr.lsp_id, ISIS_SYS_ID_LEN + 1); LSP_FRAGMENT(frag_id) = frag_num; - lsp = lsp_search(frag_id, area->lspdb[level - 1]); + lsp = lsp_search(&area->lspdb[level - 1], frag_id); if (lsp) { lsp_clear_data(lsp); if (!lsp->lspu.zero_lsp) @@ -860,7 +830,7 @@ static struct isis_lsp *lsp_next_frag(uint8_t frag_num, struct isis_lsp *lsp0, area->attached_bit), 0, lsp0, level); lsp->own_lsp = 1; - lsp_insert(lsp, area->lspdb[level - 1]); + lsp_insert(&area->lspdb[level - 1], lsp); return lsp; } @@ -1228,12 +1198,12 @@ int lsp_generate(struct isis_area *area, int level) memcpy(&lspid, isis->sysid, ISIS_SYS_ID_LEN); /* only builds the lsp if the area shares the level */ - oldlsp = lsp_search(lspid, area->lspdb[level - 1]); + oldlsp = lsp_search(&area->lspdb[level - 1], lspid); if (oldlsp) { /* FIXME: we should actually initiate a purge */ seq_num = oldlsp->hdr.seqno; - lsp_search_and_destroy(oldlsp->hdr.lsp_id, - area->lspdb[level - 1]); + lsp_search_and_destroy(&area->lspdb[level - 1], + oldlsp->hdr.lsp_id); } rem_lifetime = lsp_rem_lifetime(area, level); newlsp = @@ -1243,7 +1213,7 @@ int lsp_generate(struct isis_area *area, int level) newlsp->area = area; newlsp->own_lsp = 1; - lsp_insert(newlsp, area->lspdb[level - 1]); + lsp_insert(&area->lspdb[level - 1], newlsp); /* build_lsp_data (newlsp, area); */ lsp_build(newlsp, area); /* time to calculate our checksum */ @@ -1288,7 +1258,7 @@ int lsp_generate(struct isis_area *area, int level) */ static int lsp_regenerate(struct isis_area *area, int level) { - dict_t *lspdb; + struct lspdb_head *head; struct isis_lsp *lsp, *frag; struct listnode *node; uint8_t lspid[ISIS_SYS_ID_LEN + 2]; @@ -1297,12 +1267,12 @@ static int lsp_regenerate(struct isis_area *area, int level) if ((area == NULL) || (area->is_type & level) != level) return ISIS_ERROR; - lspdb = area->lspdb[level - 1]; + head = &area->lspdb[level - 1]; memset(lspid, 0, ISIS_SYS_ID_LEN + 2); memcpy(lspid, isis->sysid, ISIS_SYS_ID_LEN); - lsp = lsp_search(lspid, lspdb); + lsp = lsp_search(head, lspid); if (!lsp) { flog_err(EC_LIB_DEVELOPMENT, @@ -1445,7 +1415,7 @@ int _lsp_regenerate_schedule(struct isis_area *area, int level, continue; } - lsp = lsp_search(id, area->lspdb[lvl - 1]); + lsp = lsp_search(&area->lspdb[lvl - 1], id); if (!lsp) { sched_debug( "ISIS (%s): We do not have any LSPs to regenerate, nothing todo.", @@ -1597,7 +1567,7 @@ static void lsp_build_pseudo(struct isis_lsp *lsp, struct isis_circuit *circuit, int lsp_generate_pseudo(struct isis_circuit *circuit, int level) { - dict_t *lspdb = circuit->area->lspdb[level - 1]; + struct lspdb_head *head = &circuit->area->lspdb[level - 1]; struct isis_lsp *lsp; uint8_t lsp_id[ISIS_SYS_ID_LEN + 2]; uint16_t rem_lifetime, refresh_time; @@ -1615,7 +1585,7 @@ int lsp_generate_pseudo(struct isis_circuit *circuit, int level) /* * If for some reason have a pseudo LSP in the db already -> regenerate */ - if (lsp_search(lsp_id, lspdb)) + if (lsp_search(head, lsp_id)) return lsp_regenerate_schedule_pseudo(circuit, level); rem_lifetime = lsp_rem_lifetime(circuit->area, level); @@ -1628,7 +1598,7 @@ int lsp_generate_pseudo(struct isis_circuit *circuit, int level) lsp_build_pseudo(lsp, circuit, level); lsp_pack_pdu(lsp); lsp->own_lsp = 1; - lsp_insert(lsp, lspdb); + lsp_insert(head, lsp); lsp_flood(lsp, NULL); refresh_time = lsp_refresh_time(lsp, rem_lifetime); @@ -1659,7 +1629,7 @@ int lsp_generate_pseudo(struct isis_circuit *circuit, int level) static int lsp_regenerate_pseudo(struct isis_circuit *circuit, int level) { - dict_t *lspdb = circuit->area->lspdb[level - 1]; + struct lspdb_head *head = &circuit->area->lspdb[level - 1]; struct isis_lsp *lsp; uint8_t lsp_id[ISIS_SYS_ID_LEN + 2]; uint16_t rem_lifetime, refresh_time; @@ -1674,7 +1644,7 @@ static int lsp_regenerate_pseudo(struct isis_circuit *circuit, int level) LSP_PSEUDO_ID(lsp_id) = circuit->circuit_id; LSP_FRAGMENT(lsp_id) = 0; - lsp = lsp_search(lsp_id, lspdb); + lsp = lsp_search(head, lsp_id); if (!lsp) { flog_err(EC_LIB_DEVELOPMENT, @@ -1813,7 +1783,7 @@ int lsp_regenerate_schedule_pseudo(struct isis_circuit *circuit, int level) continue; } - lsp = lsp_search(lsp_id, circuit->area->lspdb[lvl - 1]); + lsp = lsp_search(&circuit->area->lspdb[lvl - 1], lsp_id); if (!lsp) { sched_debug( "ISIS (%s): Pseudonode LSP does not exist yet, nothing to regenerate.", @@ -1869,7 +1839,6 @@ int lsp_tick(struct thread *thread) { struct isis_area *area; struct isis_lsp *lsp; - dnode_t *dnode, *dnode_next; int level; uint16_t rem_lifetime; bool fabricd_sync_incomplete = false; @@ -1885,83 +1854,69 @@ int lsp_tick(struct thread *thread) * Remove LSPs which have aged out */ for (level = 0; level < ISIS_LEVELS; level++) { - if (area->lspdb[level] && dict_count(area->lspdb[level]) > 0) { - for (dnode = dict_first(area->lspdb[level]); - dnode != NULL; dnode = dnode_next) { - dnode_next = - dict_next(area->lspdb[level], dnode); - lsp = dnode_get(dnode); - - /* - * The lsp rem_lifetime is kept at 0 for MaxAge - * or - * ZeroAgeLifetime depending on explicit purge - * or - * natural age out. So schedule spf only once - * when - * the first time rem_lifetime becomes 0. - */ - rem_lifetime = lsp->hdr.rem_lifetime; - lsp_set_time(lsp); - - /* - * Schedule may run spf which should be done - * only after - * the lsp rem_lifetime becomes 0 for the first - * time. - * ISO 10589 - 7.3.16.4 first paragraph. - */ - if (rem_lifetime == 1 && lsp->hdr.seqno != 0) { - /* 7.3.16.4 a) set SRM flags on all */ - /* 7.3.16.4 b) retain only the header */ - if (lsp->area->purge_originator) - lsp_purge(lsp, lsp->level, NULL); - else - lsp_flood(lsp, NULL); - /* 7.3.16.4 c) record the time to purge - * FIXME */ - isis_spf_schedule(lsp->area, lsp->level); - } + struct isis_lsp *next = lspdb_first(&area->lspdb[level]); + for_each_from (lspdb, &area->lspdb[level], lsp, next) { + /* + * The lsp rem_lifetime is kept at 0 for MaxAge + * or + * ZeroAgeLifetime depending on explicit purge + * or + * natural age out. So schedule spf only once + * when + * the first time rem_lifetime becomes 0. + */ + rem_lifetime = lsp->hdr.rem_lifetime; + lsp_set_time(lsp); - if (lsp->age_out == 0) { - zlog_debug( - "ISIS-Upd (%s): L%u LSP %s seq " - "0x%08" PRIx32 " aged out", - area->area_tag, lsp->level, - rawlspid_print(lsp->hdr.lsp_id), - lsp->hdr.seqno); - - /* if we're aging out fragment 0, - * lsp_destroy() below will delete all - * other fragments too, so we need to - * skip over those - */ - while (!LSP_FRAGMENT(lsp->hdr.lsp_id) - && dnode_next) { - struct isis_lsp *nextlsp; - - nextlsp = dnode_get(dnode_next); - if (memcmp(nextlsp->hdr.lsp_id, - lsp->hdr.lsp_id, - ISIS_SYS_ID_LEN + 1)) - break; - - dnode_next = dict_next( - area->lspdb[level], - dnode_next); - } + /* + * Schedule may run spf which should be done + * only after + * the lsp rem_lifetime becomes 0 for the first + * time. + * ISO 10589 - 7.3.16.4 first paragraph. + */ + if (rem_lifetime == 1 && lsp->hdr.seqno != 0) { + /* 7.3.16.4 a) set SRM flags on all */ + /* 7.3.16.4 b) retain only the header */ + if (lsp->area->purge_originator) + lsp_purge(lsp, lsp->level, NULL); + else + lsp_flood(lsp, NULL); + /* 7.3.16.4 c) record the time to purge + * FIXME */ + isis_spf_schedule(lsp->area, lsp->level); + } - lsp_destroy(lsp); - lsp = NULL; - dict_delete_free(area->lspdb[level], - dnode); - } + if (lsp->age_out == 0) { + zlog_debug( + "ISIS-Upd (%s): L%u LSP %s seq " + "0x%08" PRIx32 " aged out", + area->area_tag, lsp->level, + rawlspid_print(lsp->hdr.lsp_id), + lsp->hdr.seqno); + + /* if we're aging out fragment 0, lsp_destroy() + * below will delete all other fragments too, + * so we need to skip over those + */ + if (!LSP_FRAGMENT(lsp->hdr.lsp_id)) + while (next && + !memcmp(next->hdr.lsp_id, + lsp->hdr.lsp_id, + ISIS_SYS_ID_LEN + 1)) + next = lspdb_next( + &area->lspdb[level], + next); + + lspdb_del(&area->lspdb[level], lsp); + lsp_destroy(lsp); + lsp = NULL; + } - if (fabricd_init_c && lsp) { - fabricd_sync_incomplete |= - ISIS_CHECK_FLAG(lsp->SSNflags, - fabricd_init_c); - } + if (fabricd_init_c && lsp) { + fabricd_sync_incomplete |= + ISIS_CHECK_FLAG(lsp->SSNflags, + fabricd_init_c); } } } @@ -1979,7 +1934,7 @@ void lsp_purge_pseudo(uint8_t *id, struct isis_circuit *circuit, int level) { struct isis_lsp *lsp; - lsp = lsp_search(id, circuit->area->lspdb[level - 1]); + lsp = lsp_search(&circuit->area->lspdb[level - 1], id); if (!lsp) return; @@ -2012,7 +1967,7 @@ void lsp_purge_non_exist(int level, struct isis_lsp_hdr *hdr, lsp_pack_pdu(lsp); - lsp_insert(lsp, area->lspdb[lsp->level - 1]); + lsp_insert(&area->lspdb[lsp->level - 1], lsp); lsp_flood(lsp, NULL); return; diff --git a/isisd/isis_lsp.h b/isisd/isis_lsp.h index e6ea0b4eda..4cbca5d517 100644 --- a/isisd/isis_lsp.h +++ b/isisd/isis_lsp.h @@ -24,13 +24,18 @@ #ifndef _ZEBRA_ISIS_LSP_H #define _ZEBRA_ISIS_LSP_H +#include "lib/typesafe.h" #include "isisd/isis_pdu.h" +PREDECL_RBTREE_UNIQ(lspdb) + /* Structure for isis_lsp, this structure will only support the fixed * System ID (Currently 6) (atleast for now). In order to support more * We will have to split the header into two parts, and for readability * sake it should better be avoided */ struct isis_lsp { + struct lspdb_item dbe; + struct isis_lsp_hdr hdr; struct stream *pdu; /* full pdu lsp */ union { @@ -54,8 +59,11 @@ struct isis_lsp { bool flooding_circuit_scoped; }; -dict_t *lsp_db_init(void); -void lsp_db_destroy(dict_t *lspdb); +extern int lspdb_compare(const struct isis_lsp *a, const struct isis_lsp *b); +DECLARE_RBTREE_UNIQ(lspdb, struct isis_lsp, dbe, lspdb_compare) + +void lsp_db_init(struct lspdb_head *head); +void lsp_db_fini(struct lspdb_head *head); int lsp_tick(struct thread *thread); int lsp_generate(struct isis_area *area, int level); @@ -76,14 +84,16 @@ struct isis_lsp *lsp_new_from_recv(struct isis_lsp_hdr *hdr, struct isis_tlvs *tlvs, struct stream *stream, struct isis_lsp *lsp0, struct isis_area *area, int level); -void lsp_insert(struct isis_lsp *lsp, dict_t *lspdb); -struct isis_lsp *lsp_search(uint8_t *id, dict_t *lspdb); +void lsp_insert(struct lspdb_head *head, struct isis_lsp *lsp); +struct isis_lsp *lsp_search(struct lspdb_head *head, const uint8_t *id); -void lsp_build_list(uint8_t *start_id, uint8_t *stop_id, uint8_t num_lsps, - struct list *list, dict_t *lspdb); -void lsp_build_list_nonzero_ht(uint8_t *start_id, uint8_t *stop_id, - struct list *list, dict_t *lspdb); -void lsp_search_and_destroy(uint8_t *id, dict_t *lspdb); +void lsp_build_list(struct lspdb_head *head, const uint8_t *start_id, + const uint8_t *stop_id, uint8_t num_lsps, + struct list *list); +void lsp_build_list_nonzero_ht(struct lspdb_head *head, + const uint8_t *start_id, + const uint8_t *stop_id, struct list *list); +void lsp_search_and_destroy(struct lspdb_head *head, const uint8_t *id); void lsp_purge_pseudo(uint8_t *id, struct isis_circuit *circuit, int level); void lsp_purge_non_exist(int level, struct isis_lsp_hdr *hdr, struct isis_area *area); @@ -108,7 +118,8 @@ void lsp_inc_seqno(struct isis_lsp *lsp, uint32_t seqno); void lspid_print(uint8_t *lsp_id, char *dest, char dynhost, char frag); void lsp_print(struct isis_lsp *lsp, struct vty *vty, char dynhost); void lsp_print_detail(struct isis_lsp *lsp, struct vty *vty, char dynhost); -int lsp_print_all(struct vty *vty, dict_t *lspdb, char detail, char dynhost); +int lsp_print_all(struct vty *vty, struct lspdb_head *head, char detail, + char dynhost); /* sets SRMflags for all active circuits of an lsp */ void lsp_set_all_srmflags(struct isis_lsp *lsp, bool set); diff --git a/isisd/isis_main.c b/isisd/isis_main.c index e74a9baadd..48ae760173 100644 --- a/isisd/isis_main.c +++ b/isisd/isis_main.c @@ -41,7 +41,6 @@ #include "qobj.h" #include "libfrr.h" -#include "isisd/dict.h" #include "isisd/isis_constants.h" #include "isisd/isis_common.h" #include "isisd/isis_flags.h" diff --git a/isisd/isis_misc.c b/isisd/isis_misc.c index c24917454a..ef0d77d6c5 100644 --- a/isisd/isis_misc.c +++ b/isisd/isis_misc.c @@ -30,7 +30,6 @@ #include "command.h" #include "log_int.h" -#include "isisd/dict.h" #include "isisd/isis_constants.h" #include "isisd/isis_common.h" #include "isisd/isis_flags.h" diff --git a/isisd/isis_northbound.c b/isisd/isis_northbound.c index 8b26a73975..cbe5ba7861 100644 --- a/isisd/isis_northbound.c +++ b/isisd/isis_northbound.c @@ -25,7 +25,6 @@ #include "libfrr.h" #include "linklist.h" #include "log.h" -#include "isisd/dict.h" #include "isisd/isis_constants.h" #include "isisd/isis_common.h" #include "isisd/isis_flags.h" diff --git a/isisd/isis_pdu.c b/isisd/isis_pdu.c index 8e9302963d..afd5e2bf84 100644 --- a/isisd/isis_pdu.c +++ b/isisd/isis_pdu.c @@ -36,7 +36,6 @@ #include "md5.h" #include "lib_errors.h" -#include "isisd/dict.h" #include "isisd/isis_constants.h" #include "isisd/isis_common.h" #include "isisd/isis_flags.h" @@ -959,7 +958,7 @@ static int process_lsp(uint8_t pdu_type, struct isis_circuit *circuit, /* Find the LSP in our database and compare it to this Link State header */ struct isis_lsp *lsp = - lsp_search(hdr.lsp_id, circuit->area->lspdb[level - 1]); + lsp_search(&circuit->area->lspdb[level - 1], hdr.lsp_id); int comp = 0; if (lsp) comp = lsp_compare(circuit->area->area_tag, lsp, hdr.seqno, @@ -1186,7 +1185,7 @@ dontcheckadj: memcpy(lspid, hdr.lsp_id, ISIS_SYS_ID_LEN + 1); LSP_FRAGMENT(lspid) = 0; lsp0 = lsp_search( - lspid, circuit->area->lspdb[level - 1]); + &circuit->area->lspdb[level - 1], lspid); if (!lsp0) { zlog_debug( "Got lsp frag, while zero lsp not in database"); @@ -1199,8 +1198,8 @@ dontcheckadj: &hdr, tlvs, circuit->rcv_stream, lsp0, circuit->area, level); tlvs = NULL; - lsp_insert(lsp, - circuit->area->lspdb[level - 1]); + lsp_insert(&circuit->area->lspdb[level - 1], + lsp); } else /* exists, so we overwrite */ { lsp_update(lsp, &hdr, tlvs, circuit->rcv_stream, @@ -1416,7 +1415,7 @@ static int process_snp(uint8_t pdu_type, struct isis_circuit *circuit, for (struct isis_lsp_entry *entry = entry_head; entry; entry = entry->next) { struct isis_lsp *lsp = - lsp_search(entry->id, circuit->area->lspdb[level - 1]); + lsp_search(&circuit->area->lspdb[level - 1], entry->id); bool own_lsp = !memcmp(entry->id, isis->sysid, ISIS_SYS_ID_LEN); if (lsp) { /* 7.3.15.2 b) 1) is this LSP newer */ @@ -1467,8 +1466,8 @@ static int process_snp(uint8_t pdu_type, struct isis_circuit *circuit, ISIS_SYS_ID_LEN + 1); LSP_FRAGMENT(lspid) = 0; lsp0 = lsp_search( - lspid, - circuit->area->lspdb[level - 1]); + &circuit->area->lspdb[level - 1], + lspid); if (!lsp0) { zlog_debug("Got lsp frag in snp, while zero not in database"); continue; @@ -1477,8 +1476,8 @@ static int process_snp(uint8_t pdu_type, struct isis_circuit *circuit, lsp = lsp_new(circuit->area, entry->id, entry->rem_lifetime, 0, 0, entry->checksum, lsp0, level); - lsp_insert(lsp, - circuit->area->lspdb[level - 1]); + lsp_insert(&circuit->area->lspdb[level - 1], + lsp); lsp_set_all_srmflags(lsp, false); ISIS_SET_FLAG(lsp->SSNflags, circuit); @@ -1495,8 +1494,8 @@ static int process_snp(uint8_t pdu_type, struct isis_circuit *circuit, * start_lsp_id and stop_lsp_id */ struct list *lsp_list = list_new(); - lsp_build_list_nonzero_ht(start_lsp_id, stop_lsp_id, lsp_list, - circuit->area->lspdb[level - 1]); + lsp_build_list_nonzero_ht(&circuit->area->lspdb[level - 1], + start_lsp_id, stop_lsp_id, lsp_list); /* Fixme: Find a better solution */ struct listnode *node, *nnode; @@ -2040,8 +2039,7 @@ static uint16_t get_max_lsp_count(uint16_t size) int send_csnp(struct isis_circuit *circuit, int level) { - if (circuit->area->lspdb[level - 1] == NULL - || dict_count(circuit->area->lspdb[level - 1]) == 0) + if (lspdb_count(&circuit->area->lspdb[level - 1]) == 0) return ISIS_OK; uint8_t pdu_type = (level == ISIS_LEVEL1) ? L1_COMPLETE_SEQ_NUM @@ -2094,7 +2092,7 @@ int send_csnp(struct isis_circuit *circuit, int level) struct isis_lsp *last_lsp; isis_tlvs_add_csnp_entries(tlvs, start, stop, num_lsps, - circuit->area->lspdb[level - 1], + &circuit->area->lspdb[level - 1], &last_lsp); /* * Update the stop lsp_id before encoding this CSNP. @@ -2215,8 +2213,7 @@ static int send_psnp(int level, struct isis_circuit *circuit) && circuit->u.bc.is_dr[level - 1]) return ISIS_OK; - if (circuit->area->lspdb[level - 1] == NULL - || dict_count(circuit->area->lspdb[level - 1]) == 0) + if (lspdb_count(&circuit->area->lspdb[level - 1]) == 0) return ISIS_OK; if (!circuit->snd_stream) @@ -2254,16 +2251,13 @@ static int send_psnp(int level, struct isis_circuit *circuit) get_max_lsp_count(STREAM_WRITEABLE(circuit->snd_stream)); while (1) { + struct isis_lsp *lsp; + tlvs = isis_alloc_tlvs(); if (CHECK_FLAG(passwd->snp_auth, SNP_AUTH_SEND)) isis_tlvs_add_auth(tlvs, passwd); - for (dnode_t *dnode = - dict_first(circuit->area->lspdb[level - 1]); - dnode; dnode = dict_next(circuit->area->lspdb[level - 1], - dnode)) { - struct isis_lsp *lsp = dnode_get(dnode); - + for_each (lspdb, &circuit->area->lspdb[level - 1], lsp) { if (ISIS_CHECK_FLAG(lsp->SSNflags, circuit)) isis_tlvs_add_lsp_entry(tlvs, lsp); diff --git a/isisd/isis_pfpacket.c b/isisd/isis_pfpacket.c index 2f6526bc5e..824acd0ff8 100644 --- a/isisd/isis_pfpacket.c +++ b/isisd/isis_pfpacket.c @@ -33,7 +33,6 @@ #include "if.h" #include "lib_errors.h" -#include "isisd/dict.h" #include "isisd/isis_constants.h" #include "isisd/isis_common.h" #include "isisd/isis_circuit.h" diff --git a/isisd/isis_redist.c b/isisd/isis_redist.c index 9047707bf0..dc23e8ea49 100644 --- a/isisd/isis_redist.c +++ b/isisd/isis_redist.c @@ -32,7 +32,6 @@ #include "vty.h" #include "srcdest_table.h" -#include "isisd/dict.h" #include "isisd/isis_constants.h" #include "isisd/isis_common.h" #include "isisd/isis_flags.h" diff --git a/isisd/isis_route.c b/isisd/isis_route.c index 1439a4229a..82005c911e 100644 --- a/isisd/isis_route.c +++ b/isisd/isis_route.c @@ -38,7 +38,6 @@ #include "isis_constants.h" #include "isis_common.h" #include "isis_flags.h" -#include "dict.h" #include "isisd.h" #include "isis_misc.h" #include "isis_adjacency.h" diff --git a/isisd/isis_routemap.c b/isisd/isis_routemap.c index 3c2cf7b3fc..d63676256b 100644 --- a/isisd/isis_routemap.c +++ b/isisd/isis_routemap.c @@ -37,7 +37,6 @@ #include "isis_constants.h" #include "isis_common.h" #include "isis_flags.h" -#include "dict.h" #include "isisd.h" #include "isis_misc.h" #include "isis_adjacency.h" diff --git a/isisd/isis_spf.c b/isisd/isis_spf.c index 18eb857ec9..a28220eb26 100644 --- a/isisd/isis_spf.c +++ b/isisd/isis_spf.c @@ -39,7 +39,6 @@ #include "isis_constants.h" #include "isis_common.h" #include "isis_flags.h" -#include "dict.h" #include "isisd.h" #include "isis_misc.h" #include "isis_adjacency.h" @@ -313,7 +312,7 @@ static struct isis_lsp *isis_root_system_lsp(struct isis_area *area, int level, memcpy(lspid, sysid, ISIS_SYS_ID_LEN); LSP_PSEUDO_ID(lspid) = 0; LSP_FRAGMENT(lspid) = 0; - lsp = lsp_search(lspid, area->lspdb[level - 1]); + lsp = lsp_search(&area->lspdb[level - 1], lspid); if (lsp && lsp->hdr.rem_lifetime != 0) return lsp; return NULL; @@ -870,10 +869,8 @@ static int isis_spf_preload_tent(struct isis_spftree *spftree, [spftree->level - 1], parent); lsp = lsp_search( - lsp_id, - spftree->area - ->lspdb[spftree->level - - 1]); + &spftree->area->lspdb[spftree->level- 1], + lsp_id); if (lsp == NULL || lsp->hdr.rem_lifetime == 0) zlog_warn( @@ -923,8 +920,8 @@ static int isis_spf_preload_tent(struct isis_spftree *spftree, continue; } lsp = lsp_search( - lsp_id, - spftree->area->lspdb[spftree->level - 1]); + &spftree->area->lspdb[spftree->level - 1], + lsp_id); if (lsp == NULL || lsp->hdr.rem_lifetime == 0) { zlog_warn( "ISIS-Spf: No lsp (%p) found from root " diff --git a/isisd/isis_spf_private.h b/isisd/isis_spf_private.h index 3a05df3f14..3a2a52afac 100644 --- a/isisd/isis_spf_private.h +++ b/isisd/isis_spf_private.h @@ -347,8 +347,8 @@ static struct isis_lsp *lsp_for_vertex(struct isis_spftree *spftree, memcpy(lsp_id, vertex->N.id, ISIS_SYS_ID_LEN + 1); LSP_FRAGMENT(lsp_id) = 0; - dict_t *lspdb = spftree->area->lspdb[spftree->level - 1]; - struct isis_lsp *lsp = lsp_search(lsp_id, lspdb); + struct lspdb_head *lspdb = &spftree->area->lspdb[spftree->level - 1]; + struct isis_lsp *lsp = lsp_search(lspdb, lsp_id); if (lsp && lsp->hdr.rem_lifetime != 0) return lsp; diff --git a/isisd/isis_te.c b/isisd/isis_te.c index 23a1f10a18..a9937b9551 100644 --- a/isisd/isis_te.c +++ b/isisd/isis_te.c @@ -43,7 +43,6 @@ #include "network.h" #include "sbuf.h" -#include "isisd/dict.h" #include "isisd/isis_constants.h" #include "isisd/isis_common.h" #include "isisd/isis_flags.h" diff --git a/isisd/isis_tlvs.c b/isisd/isis_tlvs.c index fbb1e5714c..bc9b514736 100644 --- a/isisd/isis_tlvs.c +++ b/isisd/isis_tlvs.c @@ -3522,26 +3522,24 @@ void isis_tlvs_add_lsp_entry(struct isis_tlvs *tlvs, struct isis_lsp *lsp) void isis_tlvs_add_csnp_entries(struct isis_tlvs *tlvs, uint8_t *start_id, uint8_t *stop_id, uint16_t num_lsps, - dict_t *lspdb, struct isis_lsp **last_lsp) + struct lspdb_head *head, + struct isis_lsp **last_lsp) { - dnode_t *first = dict_lower_bound(lspdb, start_id); + struct isis_lsp searchfor; + struct isis_lsp *first, *lsp; + + memcpy(&searchfor.hdr.lsp_id, start_id, sizeof(searchfor.hdr.lsp_id)); + first = lspdb_find_gteq(head, &searchfor); if (!first) return; - dnode_t *last = dict_upper_bound(lspdb, stop_id); - dnode_t *curr = first; - - isis_tlvs_add_lsp_entry(tlvs, first->dict_data); - *last_lsp = first->dict_data; - - while (curr) { - curr = dict_next(lspdb, curr); - if (curr) { - isis_tlvs_add_lsp_entry(tlvs, curr->dict_data); - *last_lsp = curr->dict_data; - } - if (curr == last || tlvs->lsp_entries.count == num_lsps) + for_each_from (lspdb, head, lsp, first) { + if (memcmp(lsp->hdr.lsp_id, stop_id, sizeof(lsp->hdr.lsp_id)) + > 0 || tlvs->lsp_entries.count == num_lsps) break; + + isis_tlvs_add_lsp_entry(tlvs, lsp); + *last_lsp = lsp; } } diff --git a/isisd/isis_tlvs.h b/isisd/isis_tlvs.h index fce30d4ee7..4954d791d8 100644 --- a/isisd/isis_tlvs.h +++ b/isisd/isis_tlvs.h @@ -25,8 +25,8 @@ #include "openbsd-tree.h" #include "prefix.h" -#include "isisd/dict.h" +struct lspdb_head; struct isis_subtlvs; struct isis_area_address; @@ -355,7 +355,8 @@ bool isis_tlvs_own_snpa_found(struct isis_tlvs *tlvs, uint8_t *snpa); void isis_tlvs_add_lsp_entry(struct isis_tlvs *tlvs, struct isis_lsp *lsp); void isis_tlvs_add_csnp_entries(struct isis_tlvs *tlvs, uint8_t *start_id, uint8_t *stop_id, uint16_t num_lsps, - dict_t *lspdb, struct isis_lsp **last_lsp); + struct lspdb_head *lspdb, + struct isis_lsp **last_lsp); void isis_tlvs_set_dynamic_hostname(struct isis_tlvs *tlvs, const char *hostname); void isis_tlvs_set_te_router_id(struct isis_tlvs *tlvs, diff --git a/isisd/isis_tx_queue.c b/isisd/isis_tx_queue.c index 270dcae7d0..6f46e6bec0 100644 --- a/isisd/isis_tx_queue.c +++ b/isisd/isis_tx_queue.c @@ -27,7 +27,6 @@ #include "isisd/isisd.h" #include "isisd/isis_memory.h" #include "isisd/isis_flags.h" -#include "dict.h" #include "isisd/isis_circuit.h" #include "isisd/isis_lsp.h" #include "isisd/isis_misc.h" diff --git a/isisd/isis_vty_fabricd.c b/isisd/isis_vty_fabricd.c index b2c0440de6..7f2061692f 100644 --- a/isisd/isis_vty_fabricd.c +++ b/isisd/isis_vty_fabricd.c @@ -161,13 +161,14 @@ DEFUN (show_lsp_flooding, struct isis_area *area; for (ALL_LIST_ELEMENTS_RO(isis->area_list, node, area)) { - dict_t *lspdb = area->lspdb[ISIS_LEVEL2 - 1]; + struct lspdb_head *head = &area->lspdb[ISIS_LEVEL2 - 1]; + struct isis_lsp *lsp; vty_out(vty, "Area %s:\n", area->area_tag ? area->area_tag : "null"); if (lspid) { - struct isis_lsp *lsp = lsp_for_arg(lspid, lspdb); + struct isis_lsp *lsp = lsp_for_arg(head, lspid); if (lsp) lsp_print_flooding(vty, lsp); @@ -175,9 +176,8 @@ DEFUN (show_lsp_flooding, continue; } - for (dnode_t *dnode = dict_first(lspdb); dnode; - dnode = dict_next(lspdb, dnode)) { - lsp_print_flooding(vty, dnode_get(dnode)); + for_each (lspdb, head, lsp) { + lsp_print_flooding(vty, lsp); vty_out(vty, "\n"); } } diff --git a/isisd/isis_zebra.c b/isisd/isis_zebra.c index 79d79f8911..ad2cfe82dc 100644 --- a/isisd/isis_zebra.c +++ b/isisd/isis_zebra.c @@ -37,7 +37,6 @@ #include "vrf.h" #include "libfrr.h" -#include "isisd/dict.h" #include "isisd/isis_constants.h" #include "isisd/isis_common.h" #include "isisd/isis_flags.h" diff --git a/isisd/isisd.c b/isisd/isisd.c index ad02220438..172c00e268 100644 --- a/isisd/isisd.c +++ b/isisd/isisd.c @@ -38,7 +38,6 @@ #include "spf_backoff.h" #include "lib/northbound_cli.h" -#include "isisd/dict.h" #include "isisd/isis_constants.h" #include "isisd/isis_common.h" #include "isisd/isis_flags.h" @@ -122,12 +121,10 @@ struct isis_area *isis_area_create(const char *area_tag) /* * intialize the databases */ - if (area->is_type & IS_LEVEL_1) { - area->lspdb[0] = lsp_db_init(); - } - if (area->is_type & IS_LEVEL_2) { - area->lspdb[1] = lsp_db_init(); - } + if (area->is_type & IS_LEVEL_1) + lsp_db_init(&area->lspdb[0]); + if (area->is_type & IS_LEVEL_2) + lsp_db_init(&area->lspdb[1]); spftree_area_init(area); @@ -268,14 +265,8 @@ int isis_area_destroy(const char *area_tag) list_delete(&area->circuit_list); } - if (area->lspdb[0] != NULL) { - lsp_db_destroy(area->lspdb[0]); - area->lspdb[0] = NULL; - } - if (area->lspdb[1] != NULL) { - lsp_db_destroy(area->lspdb[1]); - area->lspdb[1] = NULL; - } + lsp_db_fini(&area->lspdb[0]); + lsp_db_fini(&area->lspdb[1]); /* invalidate and verify to delete all routes from zebra */ isis_area_invalidate_routes(area, ISIS_LEVEL1 & ISIS_LEVEL2); @@ -1341,7 +1332,7 @@ DEFUN (show_isis_summary, return CMD_SUCCESS; } -struct isis_lsp *lsp_for_arg(const char *argv, dict_t *lspdb) +struct isis_lsp *lsp_for_arg(struct lspdb_head *head, const char *argv) { char sysid[255] = {0}; uint8_t number[3]; @@ -1389,13 +1380,13 @@ struct isis_lsp *lsp_for_arg(const char *argv, dict_t *lspdb) * hostname.- */ if (sysid2buff(lspid, sysid)) { - lsp = lsp_search(lspid, lspdb); + lsp = lsp_search(head, lspid); } else if ((dynhn = dynhn_find_by_name(sysid))) { memcpy(lspid, dynhn->id, ISIS_SYS_ID_LEN); - lsp = lsp_search(lspid, lspdb); + lsp = lsp_search(head, lspid); } else if (strncmp(cmd_hostname_get(), sysid, 15) == 0) { memcpy(lspid, isis->sysid, ISIS_SYS_ID_LEN); - lsp = lsp_search(lspid, lspdb); + lsp = lsp_search(head, lspid); } return lsp; @@ -1432,9 +1423,8 @@ static int show_isis_database(struct vty *vty, const char *argv, int ui_level) area->area_tag ? area->area_tag : "null"); for (level = 0; level < ISIS_LEVELS; level++) { - if (area->lspdb[level] - && dict_count(area->lspdb[level]) > 0) { - lsp = lsp_for_arg(argv, area->lspdb[level]); + if (lspdb_count(&area->lspdb[level]) > 0) { + lsp = lsp_for_arg(&area->lspdb[level], argv); if (lsp != NULL || argv == NULL) { vty_out(vty, @@ -1456,7 +1446,7 @@ static int show_isis_database(struct vty *vty, const char *argv, int ui_level) area->dynhostname); } else if (argv == NULL) { lsp_count = lsp_print_all( - vty, area->lspdb[level], + vty, &area->lspdb[level], ui_level, area->dynhostname); vty_out(vty, " %u LSPs\n\n", @@ -1696,10 +1686,7 @@ static void area_resign_level(struct isis_area *area, int level) isis_area_invalidate_routes(area, level); isis_area_verify_routes(area); - if (area->lspdb[level - 1]) { - lsp_db_destroy(area->lspdb[level - 1]); - area->lspdb[level - 1] = NULL; - } + lsp_db_fini(&area->lspdb[level - 1]); for (int tree = SPFTREE_IPV4; tree < SPFTREE_COUNT; tree++) { if (area->spftree[tree][level - 1]) { @@ -1735,8 +1722,7 @@ void isis_area_is_type_set(struct isis_area *area, int is_type) if (is_type == IS_LEVEL_2) area_resign_level(area, IS_LEVEL_1); - if (area->lspdb[1] == NULL) - area->lspdb[1] = lsp_db_init(); + lsp_db_init(&area->lspdb[1]); break; case IS_LEVEL_1_AND_2: @@ -1750,8 +1736,7 @@ void isis_area_is_type_set(struct isis_area *area, int is_type) if (is_type == IS_LEVEL_1) area_resign_level(area, IS_LEVEL_2); - if (area->lspdb[0] == NULL) - area->lspdb[0] = lsp_db_init(); + lsp_db_init(&area->lspdb[0]); break; default: diff --git a/isisd/isisd.h b/isisd/isisd.h index fb879395c1..0237384137 100644 --- a/isisd/isisd.h +++ b/isisd/isisd.h @@ -31,7 +31,7 @@ #include "isisd/isis_pdu_counter.h" #include "isisd/isis_circuit.h" #include "isis_flags.h" -#include "dict.h" +#include "isis_lsp.h" #include "isis_memory.h" #include "qobj.h" @@ -107,7 +107,7 @@ enum isis_metric_style { struct isis_area { struct isis *isis; /* back pointer */ - dict_t *lspdb[ISIS_LEVELS]; /* link-state dbs */ + struct lspdb_head lspdb[ISIS_LEVELS]; /* link-state dbs */ struct isis_spftree *spftree[SPFTREE_COUNT][ISIS_LEVELS]; #define DEFAULT_LSP_MTU 1497 unsigned int lsp_mtu; /* Size of LSPs to generate */ @@ -195,7 +195,7 @@ struct isis_area *isis_area_lookup(const char *); int isis_area_get(struct vty *vty, const char *area_tag); int isis_area_destroy(const char *area_tag); void print_debug(struct vty *, int, int); -struct isis_lsp *lsp_for_arg(const char *argv, dict_t *lspdb); +struct isis_lsp *lsp_for_arg(struct lspdb_head *head, const char *argv); void isis_area_invalidate_routes(struct isis_area *area, int levels); void isis_area_verify_routes(struct isis_area *area); diff --git a/isisd/subdir.am b/isisd/subdir.am index 4371d5993a..bae56309cf 100644 --- a/isisd/subdir.am +++ b/isisd/subdir.am @@ -25,7 +25,6 @@ dist_examples_DATA += isisd/fabricd.conf.sample endif noinst_HEADERS += \ - isisd/dict.h \ isisd/isis_adjacency.h \ isisd/isis_bfd.h \ isisd/isis_circuit.h \ @@ -61,7 +60,6 @@ noinst_HEADERS += \ # end LIBISIS_SOURCES = \ - isisd/dict.c \ isisd/isis_adjacency.c \ isisd/isis_bfd.c \ isisd/isis_circuit.c \ diff --git a/tests/isisd/test_isis_lspdb.c b/tests/isisd/test_isis_lspdb.c index b9c6f2bbb2..f0baa482c7 100644 --- a/tests/isisd/test_isis_lspdb.c +++ b/tests/isisd/test_isis_lspdb.c @@ -28,21 +28,22 @@ static void test_lsp_build_list_nonzero_ht(void) area->lsp_mtu = 1500; - dict_t *lspdb = lsp_db_init(); + struct lspdb_head _lspdb, *lspdb = &_lspdb; + lsp_db_init(&_lspdb); struct isis_lsp *lsp1 = lsp_new(area, lsp_id1, 6000, 0, 0, 0, NULL, ISIS_LEVEL2); - lsp_insert(lsp1, lspdb); + lsp_insert(lspdb, lsp1); struct isis_lsp *lsp2 = lsp_new(area, lsp_id2, 6000, 0, 0, 0, NULL, ISIS_LEVEL2); - lsp_insert(lsp2, lspdb); + lsp_insert(lspdb, lsp2); struct list *list = list_new(); - lsp_build_list_nonzero_ht(lsp_id1, lsp_id_end, list, lspdb); + lsp_build_list_nonzero_ht(lspdb, lsp_id1, lsp_id_end, list); assert(list->count == 1); assert(listgetdata(listhead(list)) == lsp1); list_delete_all_node(list); @@ -50,7 +51,7 @@ static void test_lsp_build_list_nonzero_ht(void) lsp_id_end[5] = 0x03; lsp_id_end[6] = 0x00; - lsp_build_list_nonzero_ht(lsp_id1, lsp_id_end, list, lspdb); + lsp_build_list_nonzero_ht(lspdb, lsp_id1, lsp_id_end, list); assert(list->count == 2); assert(listgetdata(listhead(list)) == lsp1); assert(listgetdata(listtail(list)) == lsp2); @@ -58,7 +59,7 @@ static void test_lsp_build_list_nonzero_ht(void) memcpy(lsp_id1, lsp_id2, sizeof(lsp_id1)); - lsp_build_list_nonzero_ht(lsp_id1, lsp_id_end, list, lspdb); + lsp_build_list_nonzero_ht(lspdb, lsp_id1, lsp_id_end, list); assert(list->count == 1); assert(listgetdata(listhead(list)) == lsp2); list_delete_all_node(list); @@ -66,13 +67,13 @@ static void test_lsp_build_list_nonzero_ht(void) lsp_id1[5] = 0x03; lsp_id_end[5] = 0x04; - lsp_build_list_nonzero_ht(lsp_id1, lsp_id_end, list, lspdb); + lsp_build_list_nonzero_ht(lspdb, lsp_id1, lsp_id_end, list); assert(list->count == 0); list_delete_all_node(list); lsp_id1[5] = 0x00; - lsp_build_list_nonzero_ht(lsp_id1, lsp_id_end, list, lspdb); + lsp_build_list_nonzero_ht(lspdb, lsp_id1, lsp_id_end, list); assert(list->count == 2); assert(listgetdata(listhead(list)) == lsp1); assert(listgetdata(listtail(list)) == lsp2); -- cgit v1.2.3 From a297301e89f49fd36f7651ff4c262923e731a46e Mon Sep 17 00:00:00 2001 From: David Lamparter Date: Sun, 21 Apr 2019 18:28:01 +0200 Subject: lib: remove fifo implementation --- lib/fifo.h | 66 --------------------------------------------------- lib/subdir.am | 1 - tests/lib/cxxcompat.c | 1 - 3 files changed, 68 deletions(-) delete mode 100644 lib/fifo.h (limited to 'tests') diff --git a/lib/fifo.h b/lib/fifo.h deleted file mode 100644 index 6f9c59b5c1..0000000000 --- a/lib/fifo.h +++ /dev/null @@ -1,66 +0,0 @@ -/* FIFO common header. - * Copyright (C) 2015 Kunihiro Ishiguro - * - * This file is part of Quagga. - * - * Quagga is free software; you can redistribute it and/or modify it - * under the terms of the GNU General Public License as published by the - * Free Software Foundation; either version 2, or (at your option) any - * later version. - * - * Quagga is distributed in the hope that it will be useful, but - * WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU - * General Public License for more details. - * - * You should have received a copy of the GNU General Public License along - * with this program; see the file COPYING; if not, write to the Free Software - * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA - */ -#ifndef __LIB_FIFO_H__ -#define __LIB_FIFO_H__ - -#ifdef __cplusplus -extern "C" { -#endif - -/* FIFO -- first in first out structure and macros. */ -struct fifo { - struct fifo *next; - struct fifo *prev; -}; - -#define FIFO_INIT(F) \ - do { \ - struct fifo *Xfifo = (struct fifo *)(F); \ - Xfifo->next = Xfifo->prev = Xfifo; \ - } while (0) - -#define FIFO_ADD(F, N) \ - do { \ - struct fifo *Xfifo = (struct fifo *)(F); \ - struct fifo *Xnode = (struct fifo *)(N); \ - Xnode->next = Xfifo; \ - Xnode->prev = Xfifo->prev; \ - Xfifo->prev = Xfifo->prev->next = Xnode; \ - } while (0) - -#define FIFO_DEL(N) \ - do { \ - struct fifo *Xnode = (struct fifo *)(N); \ - Xnode->prev->next = Xnode->next; \ - Xnode->next->prev = Xnode->prev; \ - } while (0) - -#define FIFO_HEAD(F) \ - ((((struct fifo *)(F))->next == (struct fifo *)(F)) ? NULL : (F)->next) - -#define FIFO_EMPTY(F) (((struct fifo *)(F))->next == (struct fifo *)(F)) - -#define FIFO_TOP(F) (FIFO_EMPTY(F) ? NULL : ((struct fifo *)(F))->next) - -#ifdef __cplusplus -} -#endif - -#endif /* __LIB_FIFO_H__ */ diff --git a/lib/subdir.am b/lib/subdir.am index 9bf02be9c3..38688a2470 100644 --- a/lib/subdir.am +++ b/lib/subdir.am @@ -148,7 +148,6 @@ pkginclude_HEADERS += \ lib/debug.h \ lib/distribute.h \ lib/ferr.h \ - lib/fifo.h \ lib/filter.h \ lib/freebsd-queue.h \ lib/frr_pthread.h \ diff --git a/tests/lib/cxxcompat.c b/tests/lib/cxxcompat.c index b71361a23d..d1278cef22 100644 --- a/tests/lib/cxxcompat.c +++ b/tests/lib/cxxcompat.c @@ -32,7 +32,6 @@ #include "lib/debug.h" #include "lib/distribute.h" #include "lib/ferr.h" -#include "lib/fifo.h" #include "lib/filter.h" #include "lib/frr_pthread.h" #include "lib/frratomic.h" -- cgit v1.2.3 From 7629b6b79c7a2de2e83633b87ec420b30ed4173b Mon Sep 17 00:00:00 2001 From: David Lamparter Date: Mon, 29 Apr 2019 21:18:48 +0200 Subject: Revert "lib: remove pqueue_*" This reverts commit 798ac49d06b6619adb4c5ac765b092397bc50a6c. --- lib/pqueue.c | 185 +++++++++++++++++++++++++++++++++++++ lib/pqueue.h | 54 +++++++++++ lib/subdir.am | 2 + tests/lib/cxxcompat.c | 1 + tests/lib/test_timer_correctness.c | 1 + tests/lib/test_timer_performance.c | 1 + 6 files changed, 244 insertions(+) create mode 100644 lib/pqueue.c create mode 100644 lib/pqueue.h (limited to 'tests') diff --git a/lib/pqueue.c b/lib/pqueue.c new file mode 100644 index 0000000000..87b54a681a --- /dev/null +++ b/lib/pqueue.c @@ -0,0 +1,185 @@ +/* Priority queue functions. + * Copyright (C) 2003 Yasuhiro Ohara + * + * This file is part of GNU Zebra. + * + * GNU Zebra is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published + * by the Free Software Foundation; either version 2, or (at your + * option) any later version. + * + * GNU Zebra is distributed in the hope that it will be useful, but + * WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * General Public License for more details. + * + * You should have received a copy of the GNU General Public License along + * with this program; see the file COPYING; if not, write to the Free Software + * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA + */ + +#include + +#include "memory.h" +#include "pqueue.h" + +DEFINE_MTYPE_STATIC(LIB, PQUEUE, "Priority queue") +DEFINE_MTYPE_STATIC(LIB, PQUEUE_DATA, "Priority queue data") + +/* priority queue using heap sort */ + +/* pqueue->cmp() controls the order of sorting (i.e, ascending or + descending). If you want the left node to move upper of the heap + binary tree, make cmp() to return less than 0. for example, if cmp + (10, 20) returns -1, the sorting is ascending order. if cmp (10, + 20) returns 1, the sorting is descending order. if cmp (10, 20) + returns 0, this library does not do sorting (which will not be what + you want). To be brief, if the contents of cmp_func (left, right) + is left - right, dequeue () returns the smallest node. Otherwise + (if the contents is right - left), dequeue () returns the largest + node. */ + +#define DATA_SIZE (sizeof (void *)) +#define PARENT_OF(x) ((x - 1) / 2) +#define LEFT_OF(x) (2 * x + 1) +#define RIGHT_OF(x) (2 * x + 2) +#define HAVE_CHILD(x,q) (x < (q)->size / 2) + +void trickle_up(int index, struct pqueue *queue) +{ + void *tmp; + + /* Save current node as tmp node. */ + tmp = queue->array[index]; + + /* Continue until the node reaches top or the place where the parent + node should be upper than the tmp node. */ + while (index > 0 + && (*queue->cmp)(tmp, queue->array[PARENT_OF(index)]) < 0) { + /* actually trickle up */ + queue->array[index] = queue->array[PARENT_OF(index)]; + if (queue->update != NULL) + (*queue->update)(queue->array[index], index); + index = PARENT_OF(index); + } + + /* Restore the tmp node to appropriate place. */ + queue->array[index] = tmp; + if (queue->update != NULL) + (*queue->update)(tmp, index); +} + +void trickle_down(int index, struct pqueue *queue) +{ + void *tmp; + int which; + + /* Save current node as tmp node. */ + tmp = queue->array[index]; + + /* Continue until the node have at least one (left) child. */ + while (HAVE_CHILD(index, queue)) { + /* If right child exists, and if the right child is more proper + to be moved upper. */ + if (RIGHT_OF(index) < queue->size + && (*queue->cmp)(queue->array[LEFT_OF(index)], + queue->array[RIGHT_OF(index)]) + > 0) + which = RIGHT_OF(index); + else + which = LEFT_OF(index); + + /* If the tmp node should be upper than the child, break. */ + if ((*queue->cmp)(queue->array[which], tmp) > 0) + break; + + /* Actually trickle down the tmp node. */ + queue->array[index] = queue->array[which]; + if (queue->update != NULL) + (*queue->update)(queue->array[index], index); + index = which; + } + + /* Restore the tmp node to appropriate place. */ + queue->array[index] = tmp; + if (queue->update != NULL) + (*queue->update)(tmp, index); +} + +struct pqueue *pqueue_create(void) +{ + struct pqueue *queue; + + queue = XCALLOC(MTYPE_PQUEUE, sizeof(struct pqueue)); + + queue->array = + XCALLOC(MTYPE_PQUEUE_DATA, DATA_SIZE * PQUEUE_INIT_ARRAYSIZE); + queue->array_size = PQUEUE_INIT_ARRAYSIZE; + + /* By default we want nothing to happen when a node changes. */ + queue->update = NULL; + return queue; +} + +void pqueue_delete(struct pqueue *queue) +{ + XFREE(MTYPE_PQUEUE_DATA, queue->array); + XFREE(MTYPE_PQUEUE, queue); +} + +static int pqueue_expand(struct pqueue *queue) +{ + void **newarray; + + newarray = + XCALLOC(MTYPE_PQUEUE_DATA, queue->array_size * DATA_SIZE * 2); + + memcpy(newarray, queue->array, queue->array_size * DATA_SIZE); + + XFREE(MTYPE_PQUEUE_DATA, queue->array); + queue->array = newarray; + queue->array_size *= 2; + + return 1; +} + +void pqueue_enqueue(void *data, struct pqueue *queue) +{ + if (queue->size + 2 >= queue->array_size && !pqueue_expand(queue)) + return; + + queue->array[queue->size] = data; + if (queue->update != NULL) + (*queue->update)(data, queue->size); + trickle_up(queue->size, queue); + queue->size++; +} + +void *pqueue_dequeue(struct pqueue *queue) +{ + void *data = queue->array[0]; + queue->array[0] = queue->array[--queue->size]; + trickle_down(0, queue); + return data; +} + +void pqueue_remove_at(int index, struct pqueue *queue) +{ + queue->array[index] = queue->array[--queue->size]; + + if (index > 0 + && (*queue->cmp)(queue->array[index], + queue->array[PARENT_OF(index)]) + < 0) { + trickle_up(index, queue); + } else { + trickle_down(index, queue); + } +} + +void pqueue_remove(void *data, struct pqueue *queue) +{ + for (int i = 0; i < queue->size; i++) + if (queue->array[i] == data) + pqueue_remove_at(i, queue); +} diff --git a/lib/pqueue.h b/lib/pqueue.h new file mode 100644 index 0000000000..032ee9db4c --- /dev/null +++ b/lib/pqueue.h @@ -0,0 +1,54 @@ +/* Priority queue functions. + * Copyright (C) 2003 Yasuhiro Ohara + * + * This file is part of GNU Zebra. + * + * GNU Zebra is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published + * by the Free Software Foundation; either version 2, or (at your + * option) any later version. + * + * GNU Zebra is distributed in the hope that it will be useful, but + * WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * General Public License for more details. + * + * You should have received a copy of the GNU General Public License along + * with this program; see the file COPYING; if not, write to the Free Software + * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA + */ + +#ifndef _ZEBRA_PQUEUE_H +#define _ZEBRA_PQUEUE_H + +#ifdef __cplusplus +extern "C" { +#endif + +struct pqueue { + void **array; + int array_size; + int size; + + int (*cmp)(void *, void *); + void (*update)(void *node, int actual_position); +}; + +#define PQUEUE_INIT_ARRAYSIZE 32 + +extern struct pqueue *pqueue_create(void); +extern void pqueue_delete(struct pqueue *queue); + +extern void pqueue_enqueue(void *data, struct pqueue *queue); +extern void *pqueue_dequeue(struct pqueue *queue); +extern void pqueue_remove_at(int index, struct pqueue *queue); +extern void pqueue_remove(void *data, struct pqueue *queue); + +extern void trickle_down(int index, struct pqueue *queue); +extern void trickle_up(int index, struct pqueue *queue); + +#ifdef __cplusplus +} +#endif + +#endif /* _ZEBRA_PQUEUE_H */ diff --git a/lib/subdir.am b/lib/subdir.am index 38688a2470..7027f3f0da 100644 --- a/lib/subdir.am +++ b/lib/subdir.am @@ -58,6 +58,7 @@ lib_libfrr_la_SOURCES = \ lib/openbsd-tree.c \ lib/pid_output.c \ lib/plist.c \ + lib/pqueue.c \ lib/prefix.c \ lib/privs.c \ lib/ptm_lib.c \ @@ -186,6 +187,7 @@ pkginclude_HEADERS += \ lib/openbsd-queue.h \ lib/openbsd-tree.h \ lib/plist.h \ + lib/pqueue.h \ lib/prefix.h \ lib/privs.h \ lib/ptm_lib.h \ diff --git a/tests/lib/cxxcompat.c b/tests/lib/cxxcompat.c index d1278cef22..12c333c8b6 100644 --- a/tests/lib/cxxcompat.c +++ b/tests/lib/cxxcompat.c @@ -71,6 +71,7 @@ #include "lib/openbsd-tree.h" #include "lib/pbr.h" #include "lib/plist.h" +#include "lib/pqueue.h" #include "lib/prefix.h" #include "lib/privs.h" #include "lib/ptm_lib.h" diff --git a/tests/lib/test_timer_correctness.c b/tests/lib/test_timer_correctness.c index cbf9b05546..43e79ba9d0 100644 --- a/tests/lib/test_timer_correctness.c +++ b/tests/lib/test_timer_correctness.c @@ -28,6 +28,7 @@ #include #include "memory.h" +#include "pqueue.h" #include "prng.h" #include "thread.h" diff --git a/tests/lib/test_timer_performance.c b/tests/lib/test_timer_performance.c index 2960e0d81e..d5f4badc85 100644 --- a/tests/lib/test_timer_performance.c +++ b/tests/lib/test_timer_performance.c @@ -28,6 +28,7 @@ #include #include "thread.h" +#include "pqueue.h" #include "prng.h" #define SCHEDULE_TIMERS 1000000 -- cgit v1.2.3