summaryrefslogtreecommitdiffstats
path: root/clib/list.h
diff options
context:
space:
mode:
Diffstat (limited to 'clib/list.h')
-rw-r--r--clib/list.h537
1 files changed, 537 insertions, 0 deletions
diff --git a/clib/list.h b/clib/list.h
new file mode 100644
index 0000000..db8ef59
--- /dev/null
+++ b/clib/list.h
@@ -0,0 +1,537 @@
+/*
+ * Copyright (c) International Business Machines Corp., 2014
+ *
+ * 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
+ */
+
+/*!
+ * @file list.h
+ * @brief List container
+ * @details
+ * A List is a data structure (container) used for collecting a sequence of elements.
+ * List allow for efficient insertion, removal and retreival of elements.
+ *
+ * @details For example,
+ * @code
+ * #include <clib/list.h>
+ * #include <clib/list_iter.h>
+ *
+ * int main(const int argc, const char * argv[]) {
+ * typedef struct {
+ * list_node_t node;
+ * int i;
+ * float f;
+ * } data_t;
+ *
+ * slab_t s;
+ * slab_init(&s, sizeof(data_t), 0);
+ *
+ * list_t a;
+ * list_init(&a);
+ *
+ * int i;
+ * for (i=0; i<10; i++) {
+ * data_t * d = (data_t *)slab_alloc(&s);
+ *
+ * d->i = i;
+ * d->f = (float)i;
+ *
+ * list_add_tail(&l, &d->node);
+ * }
+ *
+ * data_t * d;
+ * list_for_each(&l, d, node) {
+ * printf("i: %d f: %f\n", d->i, d->f);
+ * }
+ *
+ * list_dump(&l, stdout);
+ * slab_delete(&s);
+ *
+ * return 0;
+ * }
+ * @endcode
+ * @date 2010-2011
+ */
+
+#ifndef __LIST_H__
+#define __LIST_H__
+
+#include <stdint.h>
+#include <stdbool.h>
+#include <stdio.h>
+
+#include "builtin.h"
+#include "assert.h"
+#include "type.h"
+
+/* ==================================================================== */
+
+#define INIT_LIST_NODE {NULL,NULL}
+#define INIT_LIST {INIT_LIST_NODE}
+
+typedef struct list_node list_node_t; //!< Alias for the @em list_node class
+typedef struct list list_t; //!< Alias for the @em list class
+
+/*!
+ * @brief list node
+ * @details Primitive types cannot be stored in the @em list container, instead the user must
+ * embed a @em list_node object within the stored object.
+ */
+struct list_node {
+ list_node_t *prev; //!< Reference the previous list_node
+ list_node_t *next; //!< Reference the next list_node
+};
+
+/*!
+ * @brief list container
+ */
+struct list {
+ list_node_t node;
+};
+
+/* ==================================================================== */
+
+/*!
+ * @brief Return a pointer to the node's next node
+ * @details For example,
+ * @code
+ * ...
+ * list_node_t * node = list_head(&l);
+ * list_node_t * next = list_node_next(node);
+ * ...
+ * @endcode
+ * @memberof list
+ * @param self [in] list node object @em self pointer
+ * @return None
+ * @throws UNEXPECTED if @em self pointer is NULL
+ */
+static inline list_node_t *list_node_next(list_node_t * self)
+/*! @cond */ __nonnull((1)) /*! @endcond */ ;
+
+/*!
+ * @brief Return a pointer to the node's previous node
+ * @details For example,
+ * @code
+ * ...
+ * list_node_t * node = list_head(&l);
+ * list_node_t * next = list_node_prev(node);
+ * ...
+ * @endcode
+ * @memberof list
+ * @param self [in] list node object @em self pointer
+ * @return None
+ * @throws UNEXPECTED if @em self pointer is NULL
+ */
+static inline list_node_t *list_node_prev(list_node_t * self)
+/*! @cond */ __nonnull((1)) /*! @endcond */ ;
+
+/*!
+ * @brief Constructs an @em list container object
+ * @details For example,
+ * @code
+ * ...
+ * list_t l;
+ * list_init(&l);
+ * ...
+ * @endcode
+ * @memberof list
+ * @param self [in] list object @em self pointer
+ * @return None
+ * @throws UNEXPECTED if @em self pointer is NULL
+ */
+static inline void list_init(list_t * self)
+/*! @cond */ __nonnull((1)) /*! @endcond */ ;
+
+/*!
+ * @brief Inserts a node at the head of the @em list container
+ * @details For example,
+ * @code
+ * ...
+ * typedef struct {
+ * ...
+ * list_node_t node;
+ * ...
+ * } data_t;
+ * ...
+ * list_t l;
+ * list_init(&l);
+ *
+ * data_t * d = (data_t *) MALLOC(sizeof(*d));
+ * list_add_head(&l, &d->node);
+ * ...
+ * @endcode
+ * @memberof list
+ * @param self [in] list object @em self pointer
+ * @param node [in] list_node object to insert
+ * @return None
+ * @throws UNEXPECTED if @em self pointer is NULL
+ */
+static inline void list_add_head(list_t * self, list_node_t * node)
+/*! @cond */ __nonnull((1, 2)) /*! @endcond */ ;
+
+/*!
+ * @brief Inserts a node at the tail of the @em list container
+ * @details For example,
+ * @code
+ * ...
+ * typedef struct {
+ * ...
+ * list_node_t node;
+ * ...
+ * } data_t;
+ * ...
+ * list_t l;
+ * list_init(&l);
+ *
+ * data_t * d = (data_t *) MALLOC(sizeof(*d));
+ * list_add_tail(&l, &d->node);
+ * ...
+ * @endcode
+ * @memberof list
+ * @param self [in] list object @em self pointer
+ * @param node [in] list_node object to insert
+ * @return None
+ * @throws UNEXPECTED if @em self pointer is NULL
+ */
+static inline void list_add_tail(list_t * self, list_node_t * node)
+/*! @cond */ __nonnull((1, 2)) /*! @endcond */ ;
+
+/*!
+ * @brief Remove a node at the head of the @em list container
+ * @details For example,
+ * @code
+ * ...
+ * typedef struct {
+ * ...
+ * list_node_t node;
+ * ...
+ * } data_t;
+ * ...
+ * list_t l;
+ * list_init(&l);
+ * ...
+ * data_t * d = (data_t *)list_remove_head(&l);
+ * ...
+ * @endcode
+ * @memberof list
+ * @param self [in] list object @em self pointer
+ * @return non-NULL on success, NULL otherwise
+ * @throws UNEXPECTED if @em self pointer is NULL
+ */
+static inline list_node_t *list_remove_head(list_t * self)
+/*! @cond */ __nonnull((1)) /*! @endcond */ ;
+
+/*!
+ * @brief Remove a node at the tail of the @em list container
+ * @details For example,
+ * @code
+ * ...
+ * typedef struct {
+ * ...
+ * list_node_t node;
+ * ...
+ * } data_t;
+ * ...
+ * list_t l;
+ * list_init(&l);
+ * ...
+ * data_t * d = (data_t *)list_remove_tail(&l);
+ * ...
+ * @endcode
+ * @memberof list
+ * @param self [in] list object @em self pointer
+ * @return non-NULL on success, NULL otherwise
+ * @throws UNEXPECTED if @em self pointer is NULL
+ */
+static inline list_node_t *list_remove_tail(list_t * self)
+/*! @cond */ __nonnull((1)) /*! @endcond */ ;
+
+/*!
+ * @brief Remove the list_node referenced by @em node from the @em list container
+ * @details For example,
+ * @code
+ * ...
+ * typedef struct {
+ * ...
+ * list_node_t node;
+ * ...
+ * } data_t;
+ * ...
+ * list_t l;
+ * list_init(&l);
+ * ...
+ * data_t * d = (data_t *) MALLOC(sizeof(*d));
+ * list_add_tail(&l, &d->node);
+ * list_remove_node(&l, &d->node);
+ * ...
+ * @endcode
+ * @memberof list
+ * @param self [in] list object @em self pointer
+ * @return non-NULL on success, NULL otherwise
+ * @throws UNEXPECTED if @em self pointer is NULL
+ */
+static inline list_node_t *list_remove_node(list_t * self, list_node_t * node)
+/*! @cond */ __nonnull((1, 2)) /*! @endcond */ ;
+
+/*!
+ * @brief Test whether a @em list container is empty
+ * @details For example,
+ * @code
+ * ...
+ * typedef struct {
+ * ...
+ * list_node_t node;
+ * ...
+ * } data_t;
+ * ...
+ * list_t l;
+ * list_init(&l);
+ * ...
+ * if (list_empty(&l)) {
+ * ...
+ * }
+ * ...
+ * @endcode
+ * @memberof list
+ * @param self [in] list object @em self pointer
+ * @return true if empty, false otherwise
+ * @throws UNEXPECTED if @em self pointer is NULL
+ */
+static inline bool list_empty(const list_t * self)
+/*! @cond */ __nonnull((1)) /*! @endcond */ ;
+
+/*!
+ * @brief Return the head list_node from the @em list container
+ * @details For example,
+ * @code
+ * ...
+ * typedef struct {
+ * ...
+ * list_node_t node;
+ * ...
+ * } data_t;
+ * ...
+ * list_t l;
+ * list_init(&l);
+ * ...
+ * list_node_t * node = list_head(&l);
+ * ...
+ * @endcode
+ * @memberof list
+ * @param self [in] list object @em self pointer
+ * @return non-NULL on success, NULL otherwise
+ * @throws UNEXPECTED if @em self pointer is NULL
+ */
+static inline list_node_t *list_head(list_t * self)
+/*! @cond */ __nonnull((1)) /*! @endcond */ ;
+
+/*!
+ * @brief Return the tail list_node from the @em list container
+ * @details For example,
+ * @code
+ * ...
+ * typedef struct {
+ * ...
+ * list_node_t node;
+ * ...
+ * } data_t;
+ * ...
+ * list_t l;
+ * list_init(&l);
+ * ...
+ * list_node_t * node = list_tail(&l);
+ * ...
+ * @endcode
+ * @memberof list
+ * @param self [in] list object @em self pointer
+ * @return non-NULL on success, NULL otherwise
+ * @throws UNEXPECTED if @em self pointer is NULL
+ */
+static inline list_node_t *list_tail(list_t * self)
+/*! @cond */ __nonnull((1)) /*! @endcond */ ;
+
+/*!
+ * @brief Pretty print and dump the contents of the @em list to output stream @em out
+ * @details For example,
+ * @code
+ * ...
+ * typedef struct {
+ * ...
+ * list_node_t node;
+ * ...
+ * } data_t;
+ * ...
+ * list_t l;
+ * list_init(&l);
+ * ...
+ * list_dump(&l, stdout) {
+ * ...
+ * }
+ * ...
+ * @endcode
+ * @memberof list
+ * @param self [in] list object @em self pointer
+ * @param out [in] output stream
+ * @return None
+ * @throws UNEXPECTED if @em self pointer is NULL
+ */
+extern void list_dump(list_t * self, FILE *)
+/*! @cond */ __nonnull((1)) /*! @endcond */ ;
+
+/*!
+ * @def list_entry(node_pointer, containing_type, member)
+ * @hideinitializer
+ * @brief Returns a pointer to the containing structure of a node
+ * @param n [in] Pointer to a list_node object
+ * @param T [in] Type of the containing structure
+ * @param m [in] Name of the list_node member
+ */
+#define list_entry(n, T, m) container_of(n, T, m)
+
+#if 0
+/*!
+ * @def list_head(list_pointer, containing_type, member)
+ * @hideinitializer
+ * @brief Returns a pointer to the head element in the @em list
+ * @param n [in] Pointer to a list_node object
+ * @param T [in] Type of the containing structure
+ * @param m [in] Name of the list_node member
+ */
+#define list_head(l, T, m) ({ \
+ list_node_t * __h = (list_empty(l) ? NULL : list_entry((l)->node.next, T, m)) \
+ __h; \
+ })
+
+/*!
+ * @def list_tail(list_pointer, containing_type, member)
+ * @hideinitializer
+ * @brief Returns a pointer to the tail element in the @em list
+ * @param n [in] Pointer to a list_node object
+ * @param T [in] Type of the containing structure
+ * @param m [in] Name of the list_node member
+ */
+#define list_tail(h, T, m) ({ \
+ list_node_t * __t = (list_empty(l) ? NULL : list_entry((l)->node.prev, T, m)) \
+ __t; \
+ })
+#endif
+
+/* ==================================================================== */
+
+/*! @cond */
+static inline list_node_t *list_node_next(list_node_t * self)
+{
+ assert(self != NULL);
+ return self->next;
+}
+
+static inline list_node_t *list_node_prev(list_node_t * self)
+{
+ assert(self != NULL);
+ return self->prev;
+}
+
+static inline void list_init(list_t * self)
+{
+ assert(self != NULL);
+ self->node.prev = self->node.next = &self->node;
+}
+
+static inline void list_add_head(list_t * self, list_node_t * node)
+{
+ assert(self != NULL);
+ assert(node != NULL);
+
+ node->next = self->node.next;
+ node->prev = &self->node;
+ self->node.next->prev = node;
+ self->node.next = node;
+}
+
+static inline void list_add_tail(list_t * self, list_node_t * node)
+{
+ assert(self != NULL);
+ assert(node != NULL);
+
+ node->next = &self->node;
+ node->prev = self->node.prev;
+ self->node.prev->next = node;
+ self->node.prev = node;
+}
+
+static inline list_node_t *list_remove_head(list_t * self)
+{
+ assert(self != NULL);
+
+ list_node_t *node = self->node.next;
+
+ if (node != NULL) {
+ self->node.next = self->node.next->next;
+ self->node.next->prev = node->prev;
+ node->next = node->prev = NULL;
+ }
+
+ return node;
+}
+
+static inline list_node_t *list_remove_tail(list_t * self)
+{
+ assert(self != NULL);
+
+ list_node_t *node = self->node.prev;
+
+ if (node != NULL) {
+ self->node.prev = self->node.prev->prev;
+ self->node.prev->next = node->next;
+ node->prev = node->next = NULL;
+ }
+
+ return node;
+}
+
+static inline list_node_t *list_remove_node(list_t * self, list_node_t * node)
+{
+ assert(self != NULL);
+ assert(node != NULL);
+
+ node->next->prev = node->prev;
+ node->prev->next = node->next;
+ node->next = node->prev = NULL;
+
+ return node;
+}
+
+static inline bool list_empty(const list_t * self)
+{
+ return self->node.next == &self->node;
+}
+
+static inline list_node_t *list_head(list_t * self)
+{
+ assert(self != NULL);
+ return self->node.next;
+}
+
+static inline list_node_t *list_tail(list_t * self)
+{
+ assert(self != NULL);
+ return self->node.prev;
+}
+
+/*! @endcond */
+
+/* ==================================================================== */
+
+#endif /* __LIST_H__ */
OpenPOWER on IntegriCloud