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