1 /* Copyright (C) 2011 The Android Open Source Project
2 **
3 ** This software is licensed under the terms of the GNU General Public
4 ** License version 2, as published by the Free Software Foundation, and
5 ** may be copied, distributed, and modified under those terms.
6 **
7 ** This program is distributed in the hope that it will be useful,
8 ** but WITHOUT ANY WARRANTY; without even the implied warranty of
9 ** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
10 ** GNU General Public License for more details.
11 */
12 #ifndef _ANDROID_UTILS_LIST_H
13 #define _ANDROID_UTILS_LIST_H
14
15 #include <inttypes.h>
16
17 /* Encapsulates a double-linked, circular list.
18 * The list is organized in the following way:
19 * - List entries contain references to the next, and the previous entry in the
20 * list.
21 * - The list is circular, i.e. the "last" list entry references the "list head"
22 * in its 'next' reference, and the "list head" references the "last" entry in
23 * its 'previous' reference.
24 * - The list is empty if its 'next' and 'previous' references are addressing the
25 * head of the list.
26 */
27 typedef struct ACList ACList;
28 struct ACList {
29 /* Next entry in the list */
30 ACList* next;
31 /* Previous entry in the list */
32 ACList* prev;
33 };
34
35 /* Initializes the list. */
36 AINLINED void
alist_init(ACList * list)37 alist_init(ACList* list)
38 {
39 list->next = list->prev = list;
40 }
41
42 /* Checks if the list is empty. */
43 AINLINED int
alist_is_empty(const ACList * list)44 alist_is_empty(const ACList* list)
45 {
46 return list->next == list;
47 }
48
49 /* Inserts an entry to the head of the list */
50 AINLINED void
alist_insert_head(ACList * list,ACList * entry)51 alist_insert_head(ACList* list, ACList* entry)
52 {
53 ACList* const next = list->next;
54 entry->next = next;
55 entry->prev = list;
56 next->prev = entry;
57 list->next = entry;
58 }
59 /* Inserts an entry to the tail of the list */
60 AINLINED void
alist_insert_tail(ACList * list,ACList * entry)61 alist_insert_tail(ACList* list, ACList* entry)
62 {
63 ACList* const prev = list->prev;
64 entry->next = list;
65 entry->prev = prev;
66 prev->next = entry;
67 list->prev = entry;
68 }
69
70 /* Removes an entry from the list. NOTE: Entry must be in the list when this
71 * routine is called. */
72 AINLINED void
alist_remove(ACList * entry)73 alist_remove(ACList* entry)
74 {
75 ACList* const next = entry->next;
76 ACList* const prev = entry->prev;
77 prev->next = next;
78 next->prev = prev;
79 entry->next = entry->prev = entry;
80 }
81
82 /* Returns an entry removed from the head of the list. If the list was empty,
83 * this routine returns NULL. */
84 AINLINED ACList*
alist_remove_head(ACList * list)85 alist_remove_head(ACList* list)
86 {
87 ACList* entry = NULL;
88 if (!alist_is_empty(list)) {
89 entry = list->next;
90 list->next = entry->next;
91 entry->next->prev = list;
92 entry->next = entry->prev = entry;
93 }
94 return entry;
95 }
96
97 /* Returns an entry removed from the tail of the list. If the list was empty,
98 * this routine returns NULL. */
99 AINLINED ACList*
alist_remove_tail(ACList * list)100 alist_remove_tail(ACList* list)
101 {
102 ACList* entry = NULL;
103 if (!alist_is_empty(list)) {
104 entry = list->prev;
105 list->prev = entry->prev;
106 entry->prev->next = list;
107 entry->next = entry->prev = entry;
108 }
109 return entry;
110 }
111
112 #endif /* _ANDROID_UTILS_LIST_H */
113