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 19 ANDROID_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 */ 31 typedef struct ACList ACList; 32 struct 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. */ 40 AINLINED void 41 alist_init(ACList* list) 42 { 43 list->next = list->prev = list; 44 } 45 46 /* Checks if the list is empty. */ 47 AINLINED int 48 alist_is_empty(const ACList* list) 49 { 50 return list->next == list; 51 } 52 53 /* Inserts an entry to the head of the list */ 54 AINLINED void 55 alist_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 */ 64 AINLINED void 65 alist_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. */ 76 AINLINED void 77 alist_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. */ 88 AINLINED ACList* 89 alist_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. */ 103 AINLINED ACList* 104 alist_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 116 ANDROID_END_HEADER 117 118 #endif /* _ANDROID_UTILS_LIST_H */ 119
