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
132
133
134
135
136
137
138
139
140
141
142
|
/***************************************************************************
* __________ __ ___.
* Open \______ \ ____ ____ | | _\_ |__ _______ ___
* Source | _// _ \_/ ___\| |/ /| __ \ / _ \ \/ /
* Jukebox | | ( <_> ) \___| < | \_\ ( <_> > < <
* Firmware |____|_ /\____/ \___ >__|_ \|___ /\____/__/\_ \
* \/ \/ \/ \/ \/
* $Id$
*
* Copyright (C) 2014 by Michael Sevakis
*
* This program is free software; you can redistribute it and/or
* modify it under the terms of the GNU General Public License
* as published by the Free Software Foundation; either version 2
* of the License, or (at your option) any later version.
*
* This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY
* KIND, either express or implied.
*
****************************************************************************/
#ifndef LINKED_LIST_H
#define LINKED_LIST_H
#include <stddef.h>
/***
** NOTES:
** Node field order chosen so that one type can alias the other for forward
** list traveral by the same code.
**
** Structures are separate, even if logically equivalent, to perform compile-
** time type checking.
**
*/
/* (L)inked (L)ist
*
* Format:
*
* XX->YY->ZZ->0
* head--^ ^
* tail----------+
*/
struct ll_head
{
struct ll_node *head; /* First list item */
struct ll_node *tail; /* Last list item (to make insert_last O(1)) */
};
struct ll_node
{
struct ll_node *next; /* Next list item */
};
/**
* Initializes the singly-linked list
*/
static inline void ll_init(struct ll_head *list)
{
list->head = NULL;
list->tail = NULL;
}
void ll_insert_next(struct ll_head *list, struct ll_node *node,
struct ll_node *newnode);
void ll_insert_last(struct ll_head *list, struct ll_node *node);
void ll_remove_next(struct ll_head *list, struct ll_node *node);
void ll_remove(struct ll_head *list, struct ll_node *node);
void ll_insert_first(struct ll_head *list, struct ll_node *node);
void ll_remove_first(struct ll_head *list);
/* (L)inked (L)ist (D)double
*
* Format:
*
* 0<-XX<->YY<->ZZ->0
* head----^ ^
* tail--------------+
*/
struct lld_head
{
struct lld_node *head; /* First list item */
struct lld_node *tail; /* Last list item (to make insert_last O(1)) */
};
struct lld_node
{
struct lld_node *next; /* Next list item */
struct lld_node *prev; /* Previous list item */
};
/**
* Initializes the doubly-linked list
*/
static inline void lld_init(struct lld_head *list)
{
list->head = NULL;
list->tail = NULL;
/* tail could be stored in first item's prev pointer but this simplifies
the routines and maintains the non-circularity */
}
void lld_insert_first(struct lld_head *list, struct lld_node *node);
void lld_insert_last(struct lld_head *list, struct lld_node *node);
void lld_remove(struct lld_head *list, struct lld_node *node);
/* (L)inked (L)ist (D)ouble (C)ircular
*
* Format:
* +----------------+
* | |
* +->XX<->YY<->ZZ<-+
* head------^
*/
struct lldc_head
{
struct lldc_node *head; /* First list item */
};
struct lldc_node
{
struct lldc_node *next; /* Next list item */
struct lldc_node *prev; /* Previous list item */
};
/**
* Initializes the doubly-linked circular list
*/
static inline void lldc_init(struct lldc_head *list)
{
list->head = NULL;
}
void lldc_insert_first(struct lldc_head *list, struct lldc_node *node);
void lldc_insert_last(struct lldc_head *list, struct lldc_node *node);
void lldc_remove(struct lldc_head *list, struct lldc_node *node);
#endif /* LINKED_LIST_H */
|
