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, head->next);
  45 }
  46
  47 static inline void
  48 llist_prepend(struct llist_header* head, struct llist_header* elem)
  49 {
  50     __llist_add(elem, head->prev, head);
  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 /**
  71  * list_entry - get the struct for this entry
  72  * @ptr:        the &struct list_head pointer.
  73  * @type:       the type of the struct this is embedded in.
  74  * @member:     the name of the list_struct within the struct.
  75  */
  76 #define list_entry(ptr, type, member) container_of(ptr, type, member)
  77
  78 /**
  79  * list_for_each_entry  -       iterate over list of given type
  80  * @pos:        the type * to use as a loop counter.
  81  * @head:       the head for your list.
  82  * @member:     the name of the list_struct within the struct.
  83  */
  84 #define llist_for_each(pos, n, head, member)                                   \
  85     for (pos = list_entry((head)->next, typeof(*pos), member),                 \
  86         n = list_entry(pos->member.next, typeof(*pos), member);                \
  87          &pos->member != (head);                                               \
  88          pos = n, n = list_entry(n->member.next, typeof(*n), member))
  89
  90 struct hlist_node
  91 {
  92     struct hlist_node *next, **pprev;
  93 };
  94
  95 static inline void
  96 hlist_del(struct hlist_node* node)
  97 {
  98     *node->pprev = node->next;
  99     node->next = 0;
 100     node->pprev = 0;
 101 }
 102
 103 static inline void
 104 hlist_add(struct hlist_node** head, struct hlist_node* node)
 105 {
 106     node->next = *head;
 107     if (*head) {
 108         (*head)->pprev = &node->next;
 109     }
 110     node->pprev = head;
 111     *head = node;
 112 }
 113 #endif /* __LUNAIX_LLIST_H */