diff options
author | Michael Sevakis <jethead71@rockbox.org> | 2014-04-28 10:17:38 -0400 |
---|---|---|
committer | Michael Sevakis <jethead71@rockbox.org> | 2014-08-16 00:27:01 -0400 |
commit | eb63d8b4a2a7cbe4e98216b48a75391718fcebd7 (patch) | |
tree | 225c00b2edcd1a071f262aa181603e0c8775b249 /firmware/include/linked_list.h | |
parent | 278e8664a7393f2ca3050660c85d2142c38a4790 (diff) | |
download | rockbox-eb63d8b4a2a7cbe4e98216b48a75391718fcebd7.tar.gz rockbox-eb63d8b4a2a7cbe4e98216b48a75391718fcebd7.zip |
Add common linked list functions
Forms implemented to a greater or lesser degree at the moment:
ll_* = singly-linked list
lld_* = doubly-linked list
lldc_* = doubly-linked circular list
Change-Id: Ieed5af50fc59165c8b14c3513b3b5d0e6f7de9fa
Diffstat (limited to 'firmware/include/linked_list.h')
-rw-r--r-- | firmware/include/linked_list.h | 114 |
1 files changed, 114 insertions, 0 deletions
diff --git a/firmware/include/linked_list.h b/firmware/include/linked_list.h new file mode 100644 index 0000000000..c678cfa7eb --- /dev/null +++ b/firmware/include/linked_list.h | |||
@@ -0,0 +1,114 @@ | |||
1 | /*************************************************************************** | ||
2 | * __________ __ ___. | ||
3 | * Open \______ \ ____ ____ | | _\_ |__ _______ ___ | ||
4 | * Source | _// _ \_/ ___\| |/ /| __ \ / _ \ \/ / | ||
5 | * Jukebox | | ( <_> ) \___| < | \_\ ( <_> > < < | ||
6 | * Firmware |____|_ /\____/ \___ >__|_ \|___ /\____/__/\_ \ | ||
7 | * \/ \/ \/ \/ \/ | ||
8 | * $Id$ | ||
9 | * | ||
10 | * Copyright (C) 2014 by Michael Sevakis | ||
11 | * | ||
12 | * This program is free software; you can redistribute it and/or | ||
13 | * modify it under the terms of the GNU General Public License | ||
14 | * as published by the Free Software Foundation; either version 2 | ||
15 | * of the License, or (at your option) any later version. | ||
16 | * | ||
17 | * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY | ||
18 | * KIND, either express or implied. | ||
19 | * | ||
20 | ****************************************************************************/ | ||
21 | #ifndef LINKED_LIST_H | ||
22 | #define LINKED_LIST_H | ||
23 | |||
24 | /*** | ||
25 | ** NOTES: | ||
26 | ** Node field order chosen so that one type can alias the other for forward | ||
27 | ** list traveral by the same code. | ||
28 | ** | ||
29 | ** Structures are separate, even if logically equivalent, to perform compile- | ||
30 | ** time type checking. | ||
31 | ** | ||
32 | */ | ||
33 | |||
34 | |||
35 | /* (L)inked (L)ist | ||
36 | * | ||
37 | * Format: | ||
38 | * | ||
39 | * XX->YY->ZZ->0 | ||
40 | * head--^ ^ | ||
41 | * tail----------+ | ||
42 | */ | ||
43 | struct ll_head | ||
44 | { | ||
45 | struct ll_node *head; /* First list item */ | ||
46 | struct ll_node *tail; /* Last list item (to make insert_last O(1)) */ | ||
47 | }; | ||
48 | |||
49 | struct ll_node | ||
50 | { | ||
51 | struct ll_node *next; /* Next list item */ | ||
52 | }; | ||
53 | |||
54 | void ll_init(struct ll_head *list); | ||
55 | void ll_insert_next(struct ll_head *list, struct ll_node *node, | ||
56 | struct ll_node *newnode); | ||
57 | void ll_insert_last(struct ll_head *list, struct ll_node *node); | ||
58 | void ll_remove_next(struct ll_head *list, struct ll_node *node); | ||
59 | void ll_remove(struct ll_head *list, struct ll_node *node); | ||
60 | void ll_insert_first(struct ll_head *list, struct ll_node *node); | ||
61 | void ll_remove_first(struct ll_head *list); | ||
62 | |||
63 | |||
64 | /* (L)inked (L)ist (D)double | ||
65 | * | ||
66 | * Format: | ||
67 | * | ||
68 | * 0<-XX<->YY<->ZZ->0 | ||
69 | * head----^ ^ | ||
70 | * tail--------------+ | ||
71 | */ | ||
72 | struct lld_head | ||
73 | { | ||
74 | struct lld_node *head; /* First list item */ | ||
75 | struct lld_node *tail; /* Last list item (to make insert_last O(1)) */ | ||
76 | }; | ||
77 | |||
78 | struct lld_node | ||
79 | { | ||
80 | struct lld_node *next; /* Next list item */ | ||
81 | struct lld_node *prev; /* Previous list item */ | ||
82 | }; | ||
83 | |||
84 | void lld_init(struct lld_head *list); | ||
85 | void lld_insert_first(struct lld_head *list, struct lld_node *node); | ||
86 | void lld_insert_last(struct lld_head *list, struct lld_node *node); | ||
87 | void lld_remove(struct lld_head *list, struct lld_node *node); | ||
88 | |||
89 | |||
90 | /* (L)inked (L)ist (D)ouble (C)ircular | ||
91 | * | ||
92 | * Format: | ||
93 | * +----------------+ | ||
94 | * | | | ||
95 | * +->XX<->YY<->ZZ<-+ | ||
96 | * head------^ | ||
97 | */ | ||
98 | struct lldc_head | ||
99 | { | ||
100 | struct lldc_node *head; /* First list item */ | ||
101 | }; | ||
102 | |||
103 | struct lldc_node | ||
104 | { | ||
105 | struct lldc_node *next; /* Next list item */ | ||
106 | struct lldc_node *prev; /* Previous list item */ | ||
107 | }; | ||
108 | |||
109 | void lldc_init(struct lldc_head *list); | ||
110 | void lldc_insert_first(struct lldc_head *list, struct lldc_node *node); | ||
111 | void lldc_insert_last(struct lldc_head *list, struct lldc_node *node); | ||
112 | void lldc_remove(struct lldc_head *list, struct lldc_node *node); | ||
113 | |||
114 | #endif /* LINKED_LIST_H */ | ||