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#include "android/utils/compiler.h"
18
19ANDROID_BEGIN_HEADER
20
21/* Encapsulates a double-linked, circular list.
22 * The list is organized in the following way:
23 * - List entries contain references to the next, and the previous entry in the
24 *   list.
25 * - The list is circular, i.e. the "last" list entry references the "list head"
26 *   in its 'next' reference, and the "list head" references the "last" entry in
27 *   its 'previous' reference.
28 * - The list is empty if its 'next' and 'previous' references are addressing the
29 *   head of the list.
30 */
31typedef struct ACList ACList;
32struct ACList {
33    /* Next entry in the list */
34    ACList*  next;
35    /* Previous entry in the list */
36    ACList*  prev;
37};
38
39/* Initializes the list. */
40AINLINED void
41alist_init(ACList* list)
42{
43    list->next = list->prev = list;
44}
45
46/* Checks if the list is empty. */
47AINLINED int
48alist_is_empty(const ACList* list)
49{
50    return list->next == list;
51}
52
53/* Inserts an entry to the head of the list */
54AINLINED void
55alist_insert_head(ACList* list, ACList* entry)
56{
57    ACList* const next = list->next;
58    entry->next = next;
59    entry->prev = list;
60    next->prev = entry;
61    list->next = entry;
62}
63/* Inserts an entry to the tail of the list */
64AINLINED void
65alist_insert_tail(ACList* list, ACList* entry)
66{
67    ACList* const prev = list->prev;
68    entry->next = list;
69    entry->prev = prev;
70    prev->next = entry;
71    list->prev = entry;
72}
73
74/* Removes an entry from the list. NOTE: Entry must be in the list when this
75 * routine is called. */
76AINLINED void
77alist_remove(ACList* entry)
78{
79    ACList* const next = entry->next;
80    ACList* const prev = entry->prev;
81    prev->next = next;
82    next->prev = prev;
83    entry->next = entry->prev = entry;
84}
85
86/* Returns an entry removed from the head of the list. If the list was empty,
87 * this routine returns NULL. */
88AINLINED ACList*
89alist_remove_head(ACList* list)
90{
91    ACList* entry = NULL;
92    if (!alist_is_empty(list)) {
93        entry = list->next;
94        list->next = entry->next;
95        entry->next->prev = list;
96        entry->next = entry->prev = entry;
97    }
98    return entry;
99}
100
101/* Returns an entry removed from the tail of the list. If the list was empty,
102 * this routine returns NULL. */
103AINLINED ACList*
104alist_remove_tail(ACList* list)
105{
106    ACList* entry = NULL;
107    if (!alist_is_empty(list)) {
108        entry = list->prev;
109        list->prev = entry->prev;
110        entry->prev->next = list;
111        entry->next = entry->prev = entry;
112    }
113    return entry;
114}
115
116ANDROID_END_HEADER
117
118#endif  /* _ANDROID_UTILS_LIST_H */
119