From 0e1b907215b7f3cdd5eb6cc643ef09bdb3839817 Mon Sep 17 00:00:00 2001 From: Eugene Syromyatnikov Date: Sun, 11 Sep 2016 12:11:45 +0300 Subject: [PATCH] Add a generic list implementation Similar to the one used in the Linux kernel. * macros.h (cast_ptr, containerof): New macros. * list.h: New file. * Makefile.am (strace_SOURCES): Add it. --- Makefile.am | 1 + list.h | 300 ++++++++++++++++++++++++++++++++++++++++++++++++++++ macros.h | 19 ++++ 3 files changed, 320 insertions(+) create mode 100644 list.h diff --git a/Makefile.am b/Makefile.am index de994b1c..f1344e8d 100644 --- a/Makefile.am +++ b/Makefile.am @@ -168,6 +168,7 @@ strace_SOURCES = \ linux/asm_stat.h \ linux/x32/asm_stat.h \ linux/x86_64/asm_stat.h \ + list.h \ listen.c \ lookup_dcookie.c \ loop.c \ diff --git a/list.h b/list.h new file mode 100644 index 00000000..cf68fa78 --- /dev/null +++ b/list.h @@ -0,0 +1,300 @@ +/* + * Some simple implementation of lists similar to the one used in the kernel. + * + * Copyright (c) 2016-2019 The strace developers. + * All rights reserved. + * + * SPDX-License-Identifier: LGPL-2.1-or-later + */ + +#ifndef STRACE_LIST_H +#define STRACE_LIST_H + +/* + * struct list_item and related macros and functions provide an interface + * for manipulating and iterating linked lists. In order to have list + * associated with its payload, struct list_item has to be embedded into + * a structure type representing payload, and (optionally) an additional + * struct list_item should be added somewhere as a starting point for list + * iteration (creating a list with a designated head). A situation where + * no designated head exists, and each embedded struct list_head is considered + * a head (i.e. starting point for list iteration), is also possible. + * + * List head has to be initialised with list_init() call. Statically allocated + * list heads can also be defined with an EMPTY_LIST() macro. + * + * In order to get a pointer to list item from a struct list_item, list_elem + * macro is used. + * + * When a designated head is used, list_head() and list_tail() can be used + * for getting pointer to the first and the last list item, respectively. + * + * list_next() and list_prev() macros can be used for obtaining pointers + * to the next and the previous items in the list, respectively. Note that + * they do not perform additional checks for the validity of these pointers, + * so they have to be guarded with respective list_head/list_tail checks in case + * of lists with designated heads (where the list's head is not embedded withing + * a list item. + * + * list_{insert,append,remove,remove_tail,remove_head,replace} provide some + * basic means of list manipulation. + * + * list_foreach() and list_foreach_safe() are wrapper macros for simplifying + * iteration over a list, with the latter having an additional argument + * for storing temporary pointer, thus allowing list manipulations during + * its iteration. + * + * A simple example: + * + * struct my_struct { + * int a; + * struct list_item l1; + * struct list_item l2; + * }; + * + * EMPTY_LIST(list_1); <--- Defining a designated head for list + * + * struct my_struct *item = + * calloc(1, sizeof(*item)); + * list_init(&item->l2); <--- Initialising structure field that + * is used for lists without designated + * head. + * list_insert(&list_1, &item->l1); <--- Inserting an item into the list + * + * item = calloc(1, sizeof(*item)); + * list_init(&item->l2); + * + * list_append(&(list_head(list_1, struct my_struct, l1)->l2), &item->l2); + * + * struct my_struct *cur = item; <--- Iteration over a headless list + * do { + * printf("%d\n", cur->a); + * } while ((cur = list_next(&cur, l2)) != item); + * + * struct my_struct *i; + * list_foreach(i, list_1, l1) { <--- Iteration over list_1 without list + * printf("%d\n", i->a); modification + * } + * + * struct my_struct *tmp; <--- Iteration with modification + * list_foreach_safe(i, list_1, l1, tmp) { + * list_remove(&i->l1); + * free(i); + * } + * + * See also: + * "Linux kernel design patterns - part 2", section "Linked Lists" + * https://lwn.net/Articles/336255/ + */ + +#include "macros.h" + +struct list_item { + struct list_item *prev; + struct list_item *next; +}; + +/** + * Define an empty list head. + * + * @param l_ List head variable name. + */ +#define EMPTY_LIST(l_) struct list_item l_ = { &l_, &l_ } + +/** Initialise an empty list. */ +static inline void +list_init(struct list_item *l) +{ + l->prev = l; + l->next = l; +} + +/** Check whether list is empty. */ +static inline bool +list_is_empty(const struct list_item *l) +{ + return ((l->next == l) && (l->prev == l)) + /* + * XXX This could be the case when struct list_item hasn't been + * initialised at all; we should probably also call some + * errror_func_msg() in that case, as it looks like sloppy + * programming. + */ + || (!l->next && !l->prev); +} + +/** + * Convert a pointer to a struct list_item to a pointer to a list item. + * + * @param var Pointer to struct list_item. + * @param type Type of the list's item. + * @param field Name of the field that holds the respective struct list_item. + */ +#define list_elem(var, type, field) containerof((var), type, field) + +/** + * Get the first element in a list. + * + * @param head Pointer to the list's head. + * @param type Type of the list's item. + * @param field Name of the field that holds the respective struct list_item. + */ +#define list_head(head, type, field) \ + (list_is_empty(head) ? NULL : list_elem((head)->next, type, field)) +/** + * Get the last element in a list. + * + * @param head Pointer to the list's head. + * @param type Type of the list's item. + * @param field Name of the field that holds the respective struct list_item. + */ +#define list_tail(head, type, field) \ + (list_is_empty(head) ? NULL : list_elem((head)->prev, type, field)) + +/** + * Get the next element in a list. + * + * @param var Pointer to a list item. + * @param field Name of the field that holds the respective struct list_item. + */ +#define list_next(var, field) \ + list_elem((var)->field.next, typeof(*(var)), field) +/** + * Get the previous element in a list. + * + * @param var Pointer to a list item. + * @param field Name of the field that holds the respective struct list_item. + */ +#define list_prev(var, field) \ + list_elem((var)->field.prev, typeof(*(var)), field) + +/** + * Insert an item into a list. The item is placed as the next list item + * to the head. + */ +static inline void +list_insert(struct list_item *head, struct list_item *item) +{ + item->next = head->next; + item->prev = head; + head->next->prev = item; + head->next = item; +} + +/** + * Insert an item into a list. The item is placed as the previous list item + * to the head. + */ +static inline void +list_append(struct list_item *head, struct list_item *item) +{ + item->next = head; + item->prev = head->prev; + head->prev->next = item; + head->prev = item; +} + +/** + * Remove an item from a list. + * + * @param item Pointer to struct list_item of the item to be removed. + * @return Whether the action has been performed. + */ +static inline bool +list_remove(struct list_item *item) +{ + if (!item->next || !item->prev || list_is_empty(item)) + return false; + + item->prev->next = item->next; + item->next->prev = item->prev; + item->next = item->prev = item; + + return true; +} + +/** + * Remove the last element of a list. + * + * @param head Pointer to the list's head. + * @return Pointer to struct list_item removed from the list; + * or NULL, if the list is empty. + */ +static inline struct list_item * +list_remove_tail(struct list_item *head) +{ + struct list_item *t = list_is_empty(head) ? NULL : head->prev; + + if (t) + list_remove(t); + + return t; +} + +/** + * Remove the first element of a list. + * + * @param head Pointer to the list's head. + * @return Pointer to struct list_item removed from the list; + * or NULL, if the list is empty. + */ +static inline struct list_item * +list_remove_head(struct list_item *head) +{ + struct list_item *h = list_is_empty(head) ? NULL : head->next; + + if (h) + list_remove(h); + + return h; +} + +/** + * Replace an old struct list_item in a list with the new one. + * + * @param old Pointer to struct list_item of the item to be replaced. + * @param new Pointer to struct list_item of the item to be replaced with. + * @return Whether the replacement has been performed. + */ +static inline bool +list_replace(struct list_item *old, struct list_item *new) +{ + if (!old->next || !old->prev || list_is_empty(old)) + return false; + + new->next = old->next; + new->prev = old->prev; + old->prev->next = new; + old->next->prev = new; + old->next = old->prev = old; + + return true; +} + +/** + * List iteration wrapper for non-destructive operations. + * + * @param var_ Variable holding pointer to a current list item. + * @param head_ Pointer to the list's head. + * @param field_ Name of the field containing the respective struct list_item + * inside list items. + */ +#define list_foreach(var_, head_, field_) \ + for (var_ = list_elem((head_)->next, typeof(*var_), field_); \ + &(var_->field_) != (head_); var_ = list_next(var_, field_)) + +/** + * List iteration wrapper for destructive operations. + * + * @param var_ Variable holding pointer to a current list item. + * @param head_ Pointer to the list's head. + * @param field_ Name of the field containing the respective struct list_item + * inside list items. + * @param _tmp Temporary variable for storing pointer to the next item. + */ +#define list_foreach_safe(var_, head_, field_, _tmp) \ + for (var_ = list_elem((head_)->next, typeof(*var_), field_), \ + _tmp = list_elem((var_)->field_.next, typeof(*var_), field_); \ + &var_->field_ != head_; var_ = _tmp, _tmp = list_next(_tmp, field_)) + +#endif /* !STRACE_LIST_H */ diff --git a/macros.h b/macros.h index 61abf826..11fef3b3 100644 --- a/macros.h +++ b/macros.h @@ -41,6 +41,25 @@ (offsetof(type_, member_) + sizeof(((type_ *)0)->member_)) # endif +#ifndef cast_ptr +# define cast_ptr(type_, var_) \ + ((type_) (uintptr_t) (const volatile void *) (var_)) +#endif + +#ifndef containerof +/** + * Return a pointer to a structure that contains the provided variable. + * + * @param ptr_ Pointer to data that is a field of the container structure. + * @param struct_ Type of the container structure. + * @param member_ Name of the member field. + * @return Pointer to the container structure. + */ +# define containerof(ptr_, struct_, member_) \ + cast_ptr(struct_ *, \ + (const volatile char *) (ptr_) - offsetof(struct_, member_)) +#endif + static inline bool is_filled(const char *ptr, char fill, size_t size) { -- 2.40.0