1/* @title: Hash list */
2#pragma once
3#include <container_of.h>
4#include <stdbool.h>
5#include <stddef.h>
6
7struct hlist_head {
8 struct hlist_node *first;
9};
10
11struct hlist_node {
12 struct hlist_node *next;
13 struct hlist_node **pprev;
14};
15
16#define HLIST_HEAD_INIT {.first = NULL}
17#define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)
18
19static inline void INIT_HLIST_NODE(struct hlist_node *h) {
20 h->next = NULL;
21 h->pprev = NULL;
22}
23
24static inline bool hlist_unhashed(const struct hlist_node *h) {
25 return !h->pprev;
26}
27
28static inline bool hlist_empty(const struct hlist_head *h) {
29 return !h->first;
30}
31
32static inline void hlist_add_before(struct hlist_node *n,
33 struct hlist_node *next) {
34 n->pprev = next->pprev;
35 n->next = next;
36 *next->pprev = n;
37 next->pprev = &n->next;
38}
39
40static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h) {
41 struct hlist_node *first = h->first;
42 n->next = first;
43 if (first)
44 first->pprev = &n->next;
45 h->first = n;
46 n->pprev = &h->first;
47}
48
49static inline void hlist_del(struct hlist_node *n) {
50 struct hlist_node *next = n->next;
51 struct hlist_node **pprev = n->pprev;
52
53 *pprev = next;
54 if (next)
55 next->pprev = pprev;
56
57 n->next = NULL;
58 n->pprev = NULL;
59}
60
61static inline void hlist_move_list(struct hlist_head *old,
62 struct hlist_head *new) {
63 new->first = old->first;
64 if (new->first)
65 new->first->pprev = &new->first;
66 old->first = NULL;
67}
68
69static inline struct hlist_node *hlist_pop_head(struct hlist_head *h) {
70 struct hlist_node *first = h->first;
71 if (first)
72 hlist_del(n: first);
73 return first;
74}
75
76#define hlist_entry(ptr, type, member) container_of(ptr, type, member)
77
78#define hlist_for_each_entry(pos, head, member) \
79 for (pos = hlist_entry((head)->first, typeof(*pos), member); pos; \
80 pos = hlist_entry(pos->member.next, typeof(*pos), member))
81