diff options
Diffstat (limited to 'src/vppinfra/llist.h')
| -rw-r--r-- | src/vppinfra/llist.h | 254 |
1 files changed, 254 insertions, 0 deletions
diff --git a/src/vppinfra/llist.h b/src/vppinfra/llist.h new file mode 100644 index 00000000000..1648021681f --- /dev/null +++ b/src/vppinfra/llist.h @@ -0,0 +1,254 @@ +/* + * Copyright (c) 2019 Cisco and/or its affiliates. + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + * + * @file + * @brief Circular doubly linked list with head sentinel. + * List entries are allocated out of a "supporting" pool and all pool entries + * must contain a list anchor struct for each list they pertain to. + */ + +#ifndef SRC_VPPINFRA_CLIB_LLIST_H_ +#define SRC_VPPINFRA_CLIB_LLIST_H_ + +#include <vppinfra/types.h> +#include <vppinfra/pool.h> + +typedef u32 clib_llist_index_t; + +typedef struct clib_llist_anchor +{ + clib_llist_index_t prev; + clib_llist_index_t next; +} clib_llist_anchor_t; + +#define CLIB_LLIST_INVALID_INDEX ((u32)~0) + +/** + * Local variable naming macro. + */ +#define _ll_var(v) _llist_##v +/** + * Local macros to grab llist anchor next and prev from pool entry + */ +#define _lnext(E,name) ((E)->name).next +#define _lprev(E,name) ((E)->name).prev +/** + * Get list entry index + * + * @param LP linked list pool + * @param E pool entry + * @return pool entry index + */ +#define clib_llist_entry_index(LP,E) ((E) - (LP)) +/** + * Get next pool entry + * + * @param LP linked list pool + * @param name list anchor name + * @param E pool entry + * @return next pool entry + */ +#define clib_llist_next(LP,name,E) pool_elt_at_index((LP),_lnext((E),name)) +/** + * Get previous pool entry + * + * @param LP linked list pool + * @param name list anchor name + * @param E pool entry + * @return previous pool entry + */ +#define clib_llist_prev(LP,name,E) pool_elt_at_index((LP),_lprev((E),name)) +/** + * Initialize element in llist for entry + * + * @param LP linked list pool + * @param name list anchor name + * @param E entry whose ll anchor is to be initialized + */ +#define clib_llist_anchor_init(LP,name,E) \ +do { \ + _lprev ((E),name) = clib_llist_entry_index ((LP), (E)); \ + _lnext ((E),name) = _lprev ((E),name); \ +} while (0) +/** + * Initialize llist head + * + * @param LP linked list pool + * @param name list anchor name + */ +#define clib_llist_make_head(LP,name) \ +({ \ + typeof (LP) _ll_var (head); \ + pool_get_zero ((LP), _ll_var (head)); \ + clib_llist_anchor_init ((LP),name,_ll_var (head)); \ + clib_llist_entry_index ((LP), _ll_var (head)); \ +}) +/** + * Check is list is empty + * + * @param LP linked list pool + * @param name list anchor name + * @param H list head + * @return 1 if sentinel is the only node part of the list, 0 otherwise + */ +#define clib_llist_is_empty(LP,name,H) ((H) == clib_llist_next((LP),name,(H))) +/** + * Insert entry between previous and next + * + * Internal use. + * + * @param LP linked list pool + * @param name list anchor name + * @param E new entry + * @param P previous in list + * @param N next in list + */ +#define _llist_insert(LP,name,E,P,N) \ +do { \ + _lprev (E,name) = _lprev(N,name); \ + _lnext (E,name) = _lnext(P,name); \ + _lprev ((N),name) = clib_llist_entry_index ((LP),(E)); \ + _lnext ((P),name) = clib_llist_entry_index ((LP),(E)); \ +} while (0) +/** + * Insert entry after previous + * + * @param LP linked list pool + * @param name list anchor name + * @param E new entry + * @param P previous in list + */ +#define clib_llist_insert(LP,name,E,P) \ +do { \ + typeof (LP) _ll_var (N) = clib_llist_next (LP,name,P); \ + _llist_insert ((LP),name,(E),(P), _ll_var (N)); \ +} while (0) + +/** + * Add entry after head + * + * @param LP linked list pool + * @param name list anchor name + * @param E new entry + * @param H list head + */ +#define clib_llist_add(LP,name,E,H) clib_llist_insert ((LP),name,(E),(H)) +/** + * Add entry after tail + * + * @param LP linked list pool + * @param name list anchor name + * @param E new entry + * @param H list head + */ +#define clib_llist_add_tail(LP,name,E,H) \ +do { \ + typeof (LP) _ll_var (P) = clib_llist_prev ((LP),name,(H)); \ + _llist_insert ((LP),name,(E),_ll_var (P),(H)); \ +} while (0) +/** + * Remove entry from list + * + * @param LP linked list pool + * @param name list anchor name + * @param E entry to be removed + */ +#define clib_llist_remove(LP,name,E) \ +do { \ + ASSERT ((E) != clib_llist_next (LP,name,E));/* don't remove sentinel */\ + ASSERT (_lnext (E,name) != CLIB_LLIST_INVALID_INDEX); \ + ASSERT (_lprev (E,name) != CLIB_LLIST_INVALID_INDEX); \ + typeof (LP) _ll_var (P) = clib_llist_prev ((LP),name,E); \ + typeof (LP) _ll_var (N) = clib_llist_next ((LP),name,E); \ + _lnext (_ll_var (P),name) = _lnext (E,name); \ + _lprev (_ll_var (N),name) = _lprev (E,name); \ + _lnext (E,name) = _lprev (E,name) = CLIB_LLIST_INVALID_INDEX; \ +}while (0) + +/** + * Splice two lists at a given position + * + * List spliced into destination list is left with 0 entries, i.e., head + * is made to point to itself. + * + * @param LP linked list pool + * @param name list anchor name + * @param P position in destination where source list is spliced + * @param H head of source list that will be spliced into destination + */ +#define clib_llist_splice(LP,name,P,H) \ +do { \ + typeof (LP) _ll_var (fe) = clib_llist_next (LP,name,H); \ + if (_ll_var (fe) != (H)) \ + { \ + typeof (LP) _ll_var (le) = clib_llist_prev (LP,name,H); \ + typeof (LP) _ll_var (ne) = clib_llist_next (LP,name,P); \ + _lprev (_ll_var (fe),name) = clib_llist_entry_index(LP,P); \ + _lnext (_ll_var (le),name) = clib_llist_entry_index(LP,_ll_var (ne));\ + _lnext (P,name) = clib_llist_entry_index (LP,_ll_var (fe)); \ + _lprev (_ll_var (ne),name) = clib_llist_entry_index(LP,_ll_var (le));\ + _lnext (H,name) = clib_llist_entry_index(LP,H); \ + _lprev (H,name) = _lnext (H,name); \ + } \ +} while (0) +/** + * Walk list starting at head + * + * @param LP linked list pool + * @param name list anchor name + * @param H head entry + * @param E entry iterator + * @param body code to be executed + */ +#define clib_llist_foreach(LP,name,H,E,body) \ +do { \ + typeof (LP) _ll_var (n); \ + (E) = clib_llist_next (LP,name,H); \ + while (E != H) \ + { \ + _ll_var (n) = clib_llist_next (LP,name,E); \ + do { body; } while (0); \ + (E) = _ll_var (n); \ + } \ +} while (0) +/** + * Walk list starting at head in reverse order + * + * @param LP linked list pool + * @param name list anchor name + * @param H head entry + * @param E entry iterator + * @param body code to be executed + */ +#define clib_llist_foreach_reverse(LP,name,H,E,body) \ +do { \ + typeof (LP) _ll_var (p); \ + (E) = clib_llist_prev (LP,name,H); \ + while (E != H) \ + { \ + _ll_var (p) = clib_llist_prev (LP,name,E); \ + do { body; } while (0); \ + (E) = _ll_var (p); \ + } \ +} while (0) + +#endif /* SRC_VPPINFRA_CLIB_LLIST_H_ */ + +/* + * fd.io coding-style-patch-verification: ON + * + * Local Variables: + * eval: (c-set-style "gnu") + * End: + */ |