lunaix-os/includes/lunaix/ds/llist.h

   1 /**
   2  * @file llist.h
   3  * @author Lunaixsky
   4  * @brief This doubly linked cyclic list is adopted from Linux kernel
   5  * <linux/list.h>
   6  * @version 0.1
   7  * @date 2022-03-12
   8  *
   9  * @copyright Copyright (c) 2022
  10  *
  11  */
  12 #ifndef __LUNAIX_LLIST_H
  13 #define __LUNAIX_LLIST_H
  14
  15 #include <lunaix/types.h>
  16
  17 struct llist_header
  18 {
  19     struct llist_header* prev;
  20     struct llist_header* next;
  21 };
  22
  23 static inline void
  24 __llist_add(struct llist_header* elem,
  25             struct llist_header* prev,
  26             struct llist_header* next)
  27 {
  28     next->prev = elem;
  29     elem->next = next;
  30     elem->prev = prev;
  31     prev->next = elem;
  32 }
  33
  34 static inline void
  35 llist_init_head(struct llist_header* head)
  36 {
  37     head->next = head;
  38     head->prev = head;
  39 }
  40
  41 static inline void
  42 llist_append(struct llist_header* head, struct llist_header* elem)
  43 {
  44     __llist_add(elem, head->prev, head);
  45 }
  46
  47 static inline void
  48 llist_prepend(struct llist_header* head, struct llist_header* elem)
  49 {
  50     __llist_add(elem, head, head->next);
  51 }
  52
  53 static inline void
  54 llist_insert_after(struct llist_header* head, struct llist_header* elem)
  55 {
  56     __llist_add(elem, head, head->next);
  57 }
  58
  59 static inline void
  60 llist_delete(struct llist_header* elem)
  61 {
  62     elem->prev->next = elem->next;
  63     elem->next->prev = elem->prev;
  64
  65     // make elem orphaned
  66     elem->prev = elem;
  67     elem->next = elem;
  68 }
  69
  70 static inline int
  71 llist_empty(struct llist_header* elem)
  72 {
  73     return elem->next == elem && elem->prev == elem;
  74 }
  75
  76 #define DEFINE_LLIST(name)                                                     \
  77     struct llist_header name = (struct llist_header)                           \
  78     {                                                                          \
  79         .prev = &name, .next = &name                                           \
  80     }
  81
  82 /**
  83  * list_entry - get the struct for this entry
  84  * @ptr:        the &struct list_head pointer.
  85  * @type:       the type of the struct this is embedded in.
  86  * @member:     the name of the list_struct within the struct.
  87  */
  88 #define list_entry(ptr, type, member) container_of(ptr, type, member)
  89
  90 /**
  91  * list_for_each_entry  -       iterate over list of given type
  92  * @pos:        the type * to use as a loop counter.
  93  * @head:       the head for your list.
  94  * @member:     the name of the list_struct within the struct.
  95  */
  96 #define llist_for_each(pos, n, head, member)                                   \
  97     for (pos = list_entry((head)->next, typeof(*pos), member),                 \
  98         n = list_entry(pos->member.next, typeof(*pos), member);                \
  99          &pos->member != (head);                                               \
 100          pos = n, n = list_entry(n->member.next, typeof(*n), member))
 101
 102 struct hlist_node
 103 {
 104     struct hlist_node *next, **pprev;
 105 };
 106
 107 static inline void
 108 hlist_delete(struct hlist_node* node)
 109 {
 110     if (!node->pprev)
 111         return;
 112     *node->pprev = node->next;
 113     node->next = 0;
 114     node->pprev = 0;
 115 }
 116
 117 static inline void
 118 hlist_add(struct hlist_node** head, struct hlist_node* node)
 119 {
 120     node->next = *head;
 121     if (*head) {
 122         (*head)->pprev = &node->next;
 123     }
 124     node->pprev = head;
 125     *head = node;
 126 }
 127 #endif /* __LUNAIX_LLIST_H */