include/shared/linked_list.h


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131

#ifndef SHARED_LINKED_LIST_H_
#define SHARED_LINKED_LIST_H_

#define linked_list_t(type) linked_list_##type##_t
#define linked_list_node_t(type) linked_list_node_##type##_t
#define linked_list_push_back(type) linked_list_push_back_##type
#define linked_list_push_front(type) linked_list_push_front_##type
#define linked_list_pop_front(type) linked_list_pop_front_##type
#define linked_list_pop_back(type) linked_list_pop_back_##type
#define linked_list_front(type) linked_list_front_##type
#define linked_list_back(type) linked_list_back_##type
#define linked_list_length(type) linked_list_length_##type

#define LINKED_LIST_INIT \
  {                      \
    .head = NULL         \
  }

#define linked_list_foreach(ll, val) \
  typeof(ll.head) _cur_ = ll.head;   \
  typeof(_cur_->value) val;          \
  if (_cur_) val = _cur_->value;     \
  for (; _cur_ != NULL; _cur_ = _cur_->next, val = _cur_ ? _cur_->value : val)

#define NO_ATTRIBUTE

#define LINKED_LIST_DECL(type) LINKED_LIST_INTERNAL_DECL(type, NO_ATTRIBUTE)

#define LINKED_LIST_STATIC_DECL(type) LINKED_LIST_INTERNAL_DECL(type, static)

#define LINKED_LIST_INTERNAL_DECL(type, attr)                                  \
  typedef struct LINKED_LIST_NODE_##type {                                     \
    type value;                                                                \
    struct LINKED_LIST_NODE_##type* next;                                      \
  } linked_list_node_t(type);                                                  \
                                                                               \
  typedef struct {                                                             \
    linked_list_node_t(type) * head;                                           \
  } linked_list_t(type);                                                       \
                                                                               \
  attr void linked_list_push_back(type)(linked_list_t(type) * ll, type value); \
  attr void linked_list_push_front(type)(                                      \
      linked_list_t(type) * ll, type value);                                   \
  attr void linked_list_pop_back(type)(linked_list_t(type) * ll);              \
  attr void linked_list_pop_front(type)(linked_list_t(type) * ll);             \
  attr type* linked_list_front(type)(linked_list_t(type) * ll);                \
  attr type* linked_list_back(type)(linked_list_t(type) * ll);

#define LINKED_LIST_IMPL(type) LINKED_LIST_INTERNAL_IMPL(type, NO_ATTRIBUTE)

#define LINKED_LIST_STATIC_IMPL(type) LINKED_LIST_INTERNAL_IMPL(type, static)

#define LINKED_LIST_INTERNAL_IMPL(type, attr)                                  \
  attr void linked_list_push_back(type)(linked_list_t(type) * ll, type value)  \
  {                                                                            \
    if (!ll->head) {                                                           \
      ll->head = kalloc(sizeof(linked_list_node_t(type)));                     \
      ll->head->value = value;                                                 \
      ll->head->next = NULL;                                                   \
    } else {                                                                   \
      linked_list_node_t(type)* c = ll->head;                                  \
      while (c->next) c = c->next;                                             \
      c->next = kalloc(sizeof(linked_list_node_t(type)));                      \
      c->next->next = NULL;                                                    \
      c->next->value = value;                                                  \
    }                                                                          \
  }                                                                            \
  attr void linked_list_push_front(type)(linked_list_t(type) * ll, type value) \
  {                                                                            \
    if (!ll->head) {                                                           \
      ll->head = kalloc(sizeof(linked_list_node_t(type)));                     \
      ll->head->value = value;                                                 \
      ll->head->next = NULL;                                                   \
    } else {                                                                   \
      linked_list_node_t(type)* node =                                         \
          kalloc(sizeof(linked_list_node_t(type)));                            \
      node->next = ll->head;                                                   \
      node->value = value;                                                     \
      ll->head = node;                                                         \
    }                                                                          \
  }                                                                            \
  attr void linked_list_pop_back(type)(linked_list_t(type) * ll)               \
  {                                                                            \
    if (!ll->head) {                                                           \
      return;                                                                  \
    }                                                                          \
    if (!ll->head->next) {                                                     \
      kfree(ll->head);                                                         \
      ll->head = NULL;                                                         \
      return;                                                                  \
    }                                                                          \
    linked_list_node_t(type)* c = ll->head;                                    \
    while (c->next->next) c = c->next;                                         \
    kfree(c->next);                                                            \
    c->next = NULL;                                                            \
    return;                                                                    \
  }                                                                            \
  attr void linked_list_pop_front(type)(linked_list_t(type) * ll)              \
  {                                                                            \
    if (!ll->head) {                                                           \
      return;                                                                  \
    }                                                                          \
    linked_list_node_t(type)* node = ll->head;                                 \
    ll->head = node->next;                                                     \
    kfree(node);                                                               \
  }                                                                            \
  attr type* linked_list_front(type)(linked_list_t(type) * ll)                 \
  {                                                                            \
    if (!ll->head) {                                                           \
      return NULL;                                                             \
    }                                                                          \
    return &ll->head->value;                                                   \
  }                                                                            \
  attr type* linked_list_back(type)(linked_list_t(type) * ll)                  \
  {                                                                            \
    if (!ll->head) {                                                           \
      return NULL;                                                             \
    }                                                                          \
    linked_list_node_t(type)* cur = ll->head;                                  \
    while (cur->next) cur = cur->next;                                         \
    return &cur->value;                                                        \
  }                                                                            \
  attr size_t linked_list_length(type)(linked_list_t(type) * ll)               \
  {                                                                            \
    linked_list_node_t(type) * cur;                                            \
    size_t ret = 0;                                                            \
    for (cur = ll->head; cur; cur = cur->next) ++ret;                          \
    return ret;                                                                \
  }

#endif /* SHARED_LINKED_LIST_H_ */