graphene/Pal/include/lib/list.h

/* Copyright (C) 2017 University of North Carolina at Chapel Hill and
   Fortanix, Inc.
   This file is part of Graphene Library OS.

   Graphene Library OS is free software: you can redistribute it and/or
   modify it under the terms of the GNU Lesser General Public License
   as published by the Free Software Foundation, either version 3 of the
   License, or (at your option) any later version.

   Graphene Library OS 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 Lesser General Public License for more details.

   You should have received a copy of the GNU Lesser General Public License
   along with this program.  If not, see <http://www.gnu.org/licenses/>.  */

/*
 * list.h
 *
 * This file defines the list API for the PAL and Library OS.
 */

#ifndef LIST_H
#define LIST_H

// Use a new list implementation

/* This list implementation stores a pointer to the next object and casts to
 * the object, rather than using offsetof().  We try to encapsulate this
 * change in a macro for declarations, which generates a type declaration for
 * each list object (giving marginally more help from the compiler
 * in detecting bugs.
 *
 * In particular, there is a small trade-off in that the association between
 * list heads and nodes is more explicit and a few more casting errors can be
 * caught by the compiler, but we add a parameter to some functions (well,
 * macros) to pass the field of the struct.
 */

/* How-to:
 *
 * Each list has a pointer (listp) type, and a node (list)type.  We assume
 * list nodes are embedded in a larger structure; the name of this structure
 * is used as part of the list type.
 *
 * To define a listp/list pair for a struct foo:
 *
 * DEFINE_LIST(foo);
 * struct foo {
 *   int x;
 *   LIST_TYPE(foo) list; // The list node
 * };
 *
 * DEFINE_LISTP(foo);
 * static LISTP_TYPE(foo) the_list = LISTP_INIT;
 *
 * -----
 *
 * From here, you can use LISTP_ADD variants to add an object from the list:
 *
 * struct foo *f = malloc(sizeof(struct foo));
 * f->x = 1;
 * INIT_LIST_HEAD(f, list); // The second parameter is the structure member
 * LISTP_ADD(f, &the_list, list);
 *
 * -----
 *
 * There are a number of add variants, some that add in a given position,
 * others that add to the head or the tail.
 *
 * You can search for an object using a variant of listp_for_each_entry. The
 * safe variants are safe against deletion.
 *
 * You can remove an object from a list using LISTP_DEL.
 *
 * In this example, we delete everything with a key bigger than 5.
 *
 * LIST_TYPE(foo) *f, *n; // n is not used, just for scratch space
 * LISTP_FOR_EACH_ENTRY_SAFE(f, n, &the_list, list) {
 *    if (f->x > 4) {
 *         LISTP_DEL(f, &the_list, list);
 *         free(f);
 *    }
 * }
 *
 *
 * LISTP_SPLICE moves an entire listp onto another, and list_move_tail takes
 * an element off of one list and places it on another.
 *
 * static LISTP_TYPE(foo) other_list; // Assume it is full of goodies
 *  // Move everything on other_list to the_list
 * LISTP_SPLICE_TAIL(&other_list, &the_list, list, foo); // the third argument
 *                                                       // is the field; the
 *                                                       // fourth is the type
 *                                                       // of the nodes (not
 *                                                       // the head pointer).
 *
 * // Use LISTP_EMPTY to test for emptiness of the list
 * assert(LISTP_EMPTY(&other_ist));
 *
 *  // Now move back anythign less than 6 back to other_list
 * LISTP_FOR_EACH_ENTRY_SAFE(f, n, &the_list, list) {
 *    if (f->x < 6)
 *         LISTP_MOVE_TAIL(f, &other_list, &the_list, list);
 * }
 *
 */

// Maybe TODO?
//
// Change the order of (node, head, field) -> (head, node, field)
// drop the listp type to reduce code changes?
// Cleaner way to express types
// Add assertion to delete (in debugging mode) that item is on list
// There are a few places where knowing the listp for deletion is cumbersome;
//    maybe drop this requirement?

#include <stdbool.h>

#ifdef DEBUG
#include <assert.h>
#define LIST_ASSERT(COND) assert(COND)
#else
#define LIST_ASSERT(COND)
#endif

#define LIST_TYPE(STRUCT_NAME)  struct list_head##_##STRUCT_NAME
#define LISTP_TYPE(STRUCT_NAME) struct listp##_##STRUCT_NAME

/* Declare the enclosing struct for convenience, on
 * the assumption that this is primarily used in structure
 * definitions, and harmless if duplicated. */
#define DEFINE_LIST(STRUCT_NAME)  \
    struct STRUCT_NAME;           \
    LIST_TYPE(STRUCT_NAME) {      \
        struct STRUCT_NAME* next; \
        struct STRUCT_NAME* prev; \
    }

/* We use LISTP for pointers to a list.  This project only really needs
 * doubly-linked lists.  We used hlists to get a single pointer for more
 * efficient hash tables, but they were still effectively doubly-linked
 * lists. */
#define DEFINE_LISTP(STRUCT)  \
    LISTP_TYPE(STRUCT) {      \
        struct STRUCT* first; \
    }

#define LISTP_INIT {NULL}

/* A node not on a list uses NULL; on a list, you
 * store self pointers */
#define INIT_LIST_HEAD(OBJECT, FIELD) \
    do {                              \
        (OBJECT)->FIELD.next = NULL;  \
        (OBJECT)->FIELD.prev = NULL;  \
    } while (0)

#define INIT_LISTP(OBJECT)      \
    do {                        \
        (OBJECT)->first = NULL; \
    } while (0)

#define LISTP_EMPTY(HEAD) ((HEAD)->first == NULL)

#define LIST_EMPTY(NODE, FIELD) ((NODE)->FIELD.next == NULL)

/* This helper takes 3 arguments - all should be containing structures,
 * and the field to use for the offset to the list node */
#define __LIST_ADD(NEW, NEXT, PREV, FIELD)       \
    do {                                         \
        __typeof__(NEW) __tmp_next = (NEXT);     \
        __typeof__(NEW) __tmp_prev = (PREV);     \
        __tmp_prev->FIELD.next     = (NEW);      \
        __tmp_next->FIELD.prev     = (NEW);      \
        (NEW)->FIELD.next          = __tmp_next; \
        (NEW)->FIELD.prev          = __tmp_prev; \
    } while (0)

#define LIST_ADD(NEW, HEAD, FIELD) __LIST_ADD(NEW, (HEAD)->FIELD.next, HEAD, FIELD)

#define LISTP_ADD(NEW, HEAD, FIELD)                                           \
    do {                                                                      \
        if ((HEAD)->first == NULL) {                                          \
            (HEAD)->first     = (NEW);                                        \
            (NEW)->FIELD.next = (NEW);                                        \
            (NEW)->FIELD.prev = (NEW);                                        \
        } else {                                                              \
            __LIST_ADD(NEW, (HEAD)->first, (HEAD)->first->FIELD.prev, FIELD); \
            (HEAD)->first = (NEW);                                            \
        }                                                                     \
    } while (0)

/* If NODE is defined, add NEW after NODE; if not,
 * put NEW at the front of the list */
#define LISTP_ADD_AFTER(NEW, NODE, HEAD, FIELD) \
    do {                                        \
        if (NODE)                               \
            LIST_ADD(NEW, NODE, FIELD);         \
        else                                    \
            LISTP_ADD(NEW, HEAD, FIELD);        \
    } while (0)

#define LIST_ADD_TAIL(NEW, HEAD, FIELD) __LIST_ADD(NEW, HEAD, (HEAD)->FIELD.prev, FIELD)

#define LISTP_ADD_TAIL(NEW, HEAD, FIELD)              \
    do {                                              \
        if ((HEAD)->first == NULL) {                  \
            (HEAD)->first     = (NEW);                \
            (NEW)->FIELD.next = (NEW);                \
            (NEW)->FIELD.prev = (NEW);                \
        } else                                        \
            LIST_ADD_TAIL(NEW, (HEAD)->first, FIELD); \
    } while (0)

/* Or deletion needs to know the list root */
#define LISTP_DEL(NODE, HEAD, FIELD)                           \
    do {                                                       \
        if ((HEAD)->first == (NODE)) {                         \
            if ((NODE)->FIELD.next == (NODE)) {                \
                (HEAD)->first = NULL;                          \
            } else {                                           \
                (HEAD)->first = (NODE)->FIELD.next;            \
            }                                                  \
        }                                                      \
        LIST_ASSERT((NODE)->FIELD.prev->FIELD.next == (NODE)); \
        LIST_ASSERT((NODE)->FIELD.next->FIELD.prev == (NODE)); \
        (NODE)->FIELD.prev->FIELD.next = (NODE)->FIELD.next;   \
        (NODE)->FIELD.next->FIELD.prev = (NODE)->FIELD.prev;   \
    } while (0)

#define LISTP_DEL_INIT(NODE, HEAD, FIELD) \
    do {                                  \
        LISTP_DEL(NODE, HEAD, FIELD);     \
        INIT_LIST_HEAD(NODE, FIELD);      \
    } while (0)

/* Keep vestigial TYPE and FIELD parameters to minimize disruption
 * when switching from Linux list implementation */
#define LISTP_FIRST_ENTRY(LISTP, TYPE, FIELD) ((LISTP)->first)

/* New API: return last entry in list */
#define LISTP_LAST_ENTRY(LISTP, TYPE, FIELD) ((LISTP)->first->FIELD.prev)

/* New API: return next entry in list */
#define LISTP_NEXT_ENTRY(NODE, LISTP, FIELD) \
    ((NODE) == (LISTP)->first->FIELD.prev ? NULL : (NODE)->FIELD.next)

/* New API: return previous entry in list */
#define LISTP_PREV_ENTRY(NODE, LISTP, FIELD) ((NODE) == (LISTP)->first ? NULL : (NODE)->FIELD.prev)

/* Vestigial - for compat with Linux list code; rename to listp?
 */
#define LIST_ENTRY(LISTP, TYPE, FIELD) (LISTP)

#define LISTP_FOR_EACH_ENTRY(CURSOR, HEAD, FIELD)                       \
    for (bool first_iter = ((CURSOR) = (HEAD)->first, !!(HEAD)->first); \
         first_iter || (CURSOR) != (HEAD)->first;                       \
         (CURSOR) = (CURSOR)->FIELD.next, first_iter = false)

#define LISTP_FOR_EACH_ENTRY_REVERSE(CURSOR, HEAD, FIELD)                             \
    for (bool first_iter =                                                            \
             ((CURSOR) = ((HEAD)->first ? (HEAD)->first->FIELD.prev : (HEAD)->first), \
             !!(HEAD)->first);                                                        \
         first_iter || ((CURSOR) && (CURSOR)->FIELD.next != (HEAD)->first);           \
         (CURSOR) = (CURSOR)->FIELD.prev, first_iter = false)

#define LISTP_FOR_EACH_ENTRY_SAFE(CURSOR, TMP, HEAD, FIELD)                                        \
    for (bool first_iter = ((CURSOR) = (HEAD)->first,                                              \
                           (TMP) = ((CURSOR) ? (CURSOR)->FIELD.next : (CURSOR)), !!(HEAD)->first); \
         (HEAD)->first &&                                                                          \
         (first_iter || (CURSOR) != (HEAD)->first);                                                \
         /* Handle the case where the first element was removed. */                                \
         first_iter = first_iter && (TMP) != (CURSOR) && (HEAD)->first == (TMP), (CURSOR) = (TMP), \
              (TMP) = (TMP)->FIELD.next)

/* Continue safe iteration with CURSOR->next */
#define LISTP_FOR_EACH_ENTRY_SAFE_CONTINUE(CURSOR, TMP, HEAD, FIELD)    \
    for ((CURSOR) = (CURSOR)->FIELD.next, (TMP) = (CURSOR)->FIELD.next; \
         (CURSOR) != (HEAD)->first && (HEAD)->first; (CURSOR) = (TMP), (TMP) = (TMP)->FIELD.next)

/* Assertion code written in Graphene project */
#define CHECK_LIST_HEAD(TYPE, HEAD, FIELD)                               \
    do {                                                                 \
        TYPE pos;                                                        \
        LISTP_FOR_EACH_ENTRY(pos, HEAD, FIELD) {                         \
            assert((pos->FIELD.prev != pos && pos->FIELD.next != pos) || \
                   (pos->FIELD.prev == pos && pos->FIELD.next == pos));  \
            assert(pos->FIELD.prev->FIELD.next == pos);                  \
            assert(pos->FIELD.next->FIELD.prev == pos);                  \
        }                                                                \
    } while (0)

// Add NEW to OLD at position first (assuming first is all we need for now)
// Can probably drop TYPE with some preprocessor smarts
#define LISTP_SPLICE(NEW, OLD, FIELD, TYPE)                                      \
    do {                                                                         \
        if (!LISTP_EMPTY(NEW)) {                                                 \
            if (LISTP_EMPTY(OLD)) {                                              \
                (OLD)->first = (NEW)->first;                                     \
            } else {                                                             \
                struct TYPE* last_old                = (OLD)->first->FIELD.prev; \
                (OLD)->first->FIELD.prev->FIELD.next = (NEW)->first;             \
                (OLD)->first->FIELD.prev             = (NEW)->first->FIELD.prev; \
                (NEW)->first->FIELD.prev->FIELD.next = (OLD)->first;             \
                (NEW)->first->FIELD.prev             = last_old;                 \
                (OLD)->first                         = (NEW)->first;             \
            }                                                                    \
        }                                                                        \
    } while (0)

// Add NEW to OLD at last position
// Can probably drop TYPE with some preprocessor smarts
#define LISTP_SPLICE_TAIL(NEW, OLD, FIELD, TYPE)                                 \
    do {                                                                         \
        if (!LISTP_EMPTY(NEW)) {                                                 \
            if (LISTP_EMPTY(OLD)) {                                              \
                (OLD)->first = (NEW)->first;                                     \
            } else {                                                             \
                struct TYPE* last_old                = (OLD)->first->FIELD.prev; \
                last_old->FIELD.next                 = (NEW)->first;             \
                (OLD)->first->FIELD.prev             = (NEW)->first->FIELD.prev; \
                (NEW)->first->FIELD.prev->FIELD.next = (OLD)->first;             \
                (NEW)->first->FIELD.prev             = last_old;                 \
            }                                                                    \
        }                                                                        \
    } while (0)

#define LISTP_SPLICE_INIT(NEW, OLD, FIELD, TYPE) \
    do {                                         \
        LISTP_SPLICE(NEW, OLD, FIELD, TYPE);     \
        INIT_LISTP(NEW);                         \
    } while (0);

#define LISTP_SPLICE_TAIL_INIT(NEW, OLD, FIELD, TYPE) \
    do {                                              \
        LISTP_SPLICE_TAIL(NEW, OLD, FIELD, TYPE);     \
        INIT_LISTP(NEW);                              \
    } while (0);

// list_move_tail - delete from OLD, make tail of NEW
#define LISTP_MOVE_TAIL(NODE, NEW, OLD, FIELD) \
    do {                                       \
        LISTP_DEL_INIT(NODE, OLD, FIELD);      \
        LISTP_ADD_TAIL(NODE, NEW, FIELD);      \
    } while (0)

#endif  // LIST_H