// Copyright 2016 The Fuchsia Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#ifndef ZIRCON_LISTNODE_H_
#define ZIRCON_LISTNODE_H_

#include <stdbool.h>
#include <stddef.h>
#include <zircon/compiler.h>

__BEGIN_CDECLS

#define containerof(ptr, type, member) ((type*)((uintptr_t)(ptr)-offsetof(type, member)))

typedef struct list_node list_node_t;

struct list_node {
  list_node_t* prev;
  list_node_t* next;
};

#define LIST_INITIAL_VALUE(list) \
  { &(list), &(list) }
#define LIST_INITIAL_CLEARED_VALUE \
  { NULL, NULL }

static inline void list_initialize(list_node_t* list) { list->prev = list->next = list; }

static inline void list_clear_node(list_node_t* item) { item->prev = item->next = 0; }

static inline bool list_in_list(const list_node_t* item) {
  if (item->prev == 0 && item->next == 0)
    return false;
  else
    return true;
}

static inline void list_add_head(list_node_t* list, list_node_t* item) {
  item->next = list->next;
  item->prev = list;
  list->next->prev = item;
  list->next = item;
}

#define list_add_after(entry, new_entry) list_add_head(entry, new_entry)

static inline void list_add_tail(list_node_t* list, list_node_t* item) {
  item->prev = list->prev;
  item->next = list;
  list->prev->next = item;
  list->prev = item;
}

#define list_add_before(entry, new_entry) list_add_tail(entry, new_entry)

static inline void list_delete(list_node_t* item) {
  item->next->prev = item->prev;
  item->prev->next = item->next;
  item->prev = item->next = 0;
}

static inline void list_replace_node(list_node_t* old_node, list_node_t* new_node) {
  // replace a spot in a list with a new node
  // assumes old_node is part of a list and new_node is not
  new_node->next = old_node->next;
  new_node->prev = old_node->prev;
  old_node->prev = old_node->next = 0;

  new_node->next->prev = new_node;
  new_node->prev->next = new_node;
}

static inline list_node_t* list_remove_head(list_node_t* list) {
  if (list->next != list) {
    list_node_t* item = list->next;
    list_delete(item);
    return item;
  } else {
    return NULL;
  }
}

#define list_remove_head_type(list, type, element) \
  ({                                               \
    list_node_t* __nod = list_remove_head(list);   \
    type* __t;                                     \
    if (__nod)                                     \
      __t = containerof(__nod, type, element);     \
    else                                           \
      __t = (type*)0;                              \
    __t;                                           \
  })

static inline list_node_t* list_remove_tail(list_node_t* list) {
  if (list->prev != list) {
    list_node_t* item = list->prev;
    list_delete(item);
    return item;
  } else {
    return NULL;
  }
}

#define list_remove_tail_type(list, type, element) \
  ({                                               \
    list_node_t* __nod = list_remove_tail(list);   \
    type* __t;                                     \
    if (__nod)                                     \
      __t = containerof(__nod, type, element);     \
    else                                           \
      __t = (type*)0;                              \
    __t;                                           \
  })

static inline list_node_t* list_peek_head(const list_node_t* list) {
  if (list->next != list) {
    return list->next;
  } else {
    return NULL;
  }
}

#define list_peek_head_type(list, type, element) \
  ({                                             \
    list_node_t* __nod = list_peek_head(list);   \
    type* __t;                                   \
    if (__nod)                                   \
      __t = containerof(__nod, type, element);   \
    else                                         \
      __t = (type*)0;                            \
    __t;                                         \
  })

static inline list_node_t* list_peek_tail(const list_node_t* list) {
  if (list->prev != list) {
    return list->prev;
  } else {
    return NULL;
  }
}

#define list_peek_tail_type(list, type, element) \
  ({                                             \
    list_node_t* __nod = list_peek_tail(list);   \
    type* __t;                                   \
    if (__nod)                                   \
      __t = containerof(__nod, type, element);   \
    else                                         \
      __t = (type*)0;                            \
    __t;                                         \
  })

static inline list_node_t* list_prev(list_node_t* list, list_node_t* item) {
  if (item->prev != list)
    return item->prev;
  else
    return NULL;
}

#define list_prev_type(list, item, type, element) \
  ({                                              \
    list_node_t* __nod = list_prev(list, item);   \
    type* __t;                                    \
    if (__nod)                                    \
      __t = containerof(__nod, type, element);    \
    else                                          \
      __t = (type*)0;                             \
    __t;                                          \
  })

static inline list_node_t* list_prev_wrap(list_node_t* list, list_node_t* item) {
  if (item->prev != list)
    return item->prev;
  else if (item->prev->prev != list)
    return item->prev->prev;
  else
    return NULL;
}

#define list_prev_wrap_type(list, item, type, element) \
  ({                                                   \
    list_node_t* __nod = list_prev_wrap(list, item);   \
    type* __t;                                         \
    if (__nod)                                         \
      __t = containerof(__nod, type, element);         \
    else                                               \
      __t = (type*)0;                                  \
    __t;                                               \
  })

static inline list_node_t* list_next(list_node_t* list, list_node_t* item) {
  if (item->next != list)
    return item->next;
  else
    return NULL;
}

#define list_next_type(list, item, type, element) \
  ({                                              \
    list_node_t* __nod = list_next(list, item);   \
    type* __t;                                    \
    if (__nod)                                    \
      __t = containerof(__nod, type, element);    \
    else                                          \
      __t = (type*)0;                             \
    __t;                                          \
  })

static inline list_node_t* list_next_wrap(list_node_t* list, list_node_t* item) {
  if (item->next != list)
    return item->next;
  else if (item->next->next != list)
    return item->next->next;
  else
    return NULL;
}

#define list_next_wrap_type(list, item, type, element) \
  ({                                                   \
    list_node_t* __nod = list_next_wrap(list, item);   \
    type* __t;                                         \
    if (__nod)                                         \
      __t = containerof(__nod, type, element);         \
    else                                               \
      __t = (type*)0;                                  \
    __t;                                               \
  })

// iterates over the list, node should be list_node_t*
#define list_for_every(list, node) for (node = (list)->next; node != (list); node = node->next)

// iterates over the list in a safe way for deletion of current node
// node and temp_node should be list_node_t*
#define list_for_every_safe(list, node, temp_node)                    \
  for (node = (list)->next, temp_node = (node)->next; node != (list); \
       node = temp_node, temp_node = (node)->next)

// iterates over the list, entry should be the container structure type *
#define list_for_every_entry(list, entry, type, member)                               \
  for ((entry) = containerof((list)->next, type, member); &(entry)->member != (list); \
       (entry) = containerof((entry)->member.next, type, member))

// iterates over the list in a safe way for deletion of current node
// entry and temp_entry should be the container structure type *
#define list_for_every_entry_safe(list, entry, temp_entry, type, member) \
  for (entry = containerof((list)->next, type, member),                  \
      temp_entry = containerof((entry)->member.next, type, member);      \
       &(entry)->member != (list);                                       \
       entry = temp_entry, temp_entry = containerof((temp_entry)->member.next, type, member))

static inline bool list_is_empty(const list_node_t* list) {
  return (list->next == list) ? true : false;
}

static inline size_t list_length(const list_node_t* list) {
  size_t cnt = 0;
  const list_node_t* node = list;
  list_for_every(list, node) { cnt++; }

  return cnt;
}

// Splice the contents of splice_from into the list immediately following pos.
static inline void list_splice_after(list_node_t* splice_from, list_node_t* pos) {
  if (list_is_empty(splice_from)) {
    return;
  }
  splice_from->next->prev = pos;
  splice_from->prev->next = pos->next;
  pos->next->prev = splice_from->prev;
  pos->next = splice_from->next;
  list_initialize(splice_from);
}

// Split the contents of list after (but not including) pos, into split_to
// (which should be empty).
static inline void list_split_after(list_node_t* list, list_node_t* pos, list_node_t* split_to) {
  if (pos->next == list) {
    list_initialize(split_to);
    return;
  }
  split_to->prev = list->prev;
  split_to->prev->next = split_to;
  split_to->next = pos->next;
  split_to->next->prev = split_to;
  pos->next = list;
  list->prev = pos;
}

// Moves all the contents of old_list (which may or may not be empty)
// to new_list (which should be empty).
static inline void list_move(list_node_t* old_list, list_node_t* new_list) {
  list_initialize(new_list);
  list_splice_after(old_list, new_list);
}

__END_CDECLS

#endif  // ZIRCON_LISTNODE_H_