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/common.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_delete(struct llist_header* elem)
  55 {
  56     elem->prev->next = elem->next;
  57     elem->next->prev = elem->prev;
  58
  59     // make elem orphaned
  60     elem->prev = elem;
  61     elem->next = elem;
  62 }
  63
  64 static inline int
  65 llist_empty(struct llist_header* elem)
  66 {
  67     return elem->next == elem && elem->prev == elem;
  68 }
  69
  70 #define DEFINE_LLIST(name)                                                     \
  71     struct llist_header name = (struct llist_header)                           \
  72     {                                                                          \
  73         .prev = &name, .next = &name                                           \
  74     }
  75
  76 /**
  77  * list_entry - get the struct for this entry
  78  * @ptr:        the &struct list_head pointer.
  79  * @type:       the type of the struct this is embedded in.
  80  * @member:     the name of the list_struct within the struct.
  81  */
  82 #define list_entry(ptr, type, member) container_of(ptr, type, member)
  83
  84 /**
  85  * list_for_each_entry  -       iterate over list of given type
  86  * @pos:        the type * to use as a loop counter.
  87  * @head:       the head for your list.
  88  * @member:     the name of the list_struct within the struct.
  89  */
  90 #define llist_for_each(pos, n, head, member)                                   \
  91     for (pos = list_entry((head)->next, typeof(*pos), member),                 \
  92         n = list_entry(pos->member.next, typeof(*pos), member);                \
  93          &pos->member != (head);                                               \
  94          pos = n, n = list_entry(n->member.next, typeof(*n), member))
  95
  96 struct hlist_node
  97 {
  98     struct hlist_node *next, **pprev;
  99 };
 100
 101 static inline void
 102 hlist_delete(struct hlist_node* node)
 103 {
 104     if (!node->pprev)
 105         return;
 106     *node->pprev = node->next;
 107     node->next = 0;
 108     node->pprev = 0;
 109 }
 110
 111 static inline void
 112 hlist_add(struct hlist_node** head, struct hlist_node* node)
 113 {
 114     node->next = *head;
 115     if (*head) {
 116         (*head)->pprev = &node->next;
 117     }
 118     node->pprev = head;
 119     *head = node;
 120 }
 121 #endif /* __LUNAIX_LLIST_H */