198d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine/* Copyright (C) 2011 The Android Open Source Project 298d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine** 398d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine** This software is licensed under the terms of the GNU General Public 498d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine** License version 2, as published by the Free Software Foundation, and 598d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine** may be copied, distributed, and modified under those terms. 698d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine** 798d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine** This program is distributed in the hope that it will be useful, 898d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine** but WITHOUT ANY WARRANTY; without even the implied warranty of 998d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 1098d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine** GNU General Public License for more details. 1198d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine*/ 1298d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine#ifndef _ANDROID_UTILS_LIST_H 1398d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine#define _ANDROID_UTILS_LIST_H 1498d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine 1598d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine#include <inttypes.h> 1698d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine 17f0c747e01328e713891f2fa66c4f9df64f580dc2David 'Digit' Turner#include "android/utils/compiler.h" 18f0c747e01328e713891f2fa66c4f9df64f580dc2David 'Digit' Turner 19f0c747e01328e713891f2fa66c4f9df64f580dc2David 'Digit' TurnerANDROID_BEGIN_HEADER 20f0c747e01328e713891f2fa66c4f9df64f580dc2David 'Digit' Turner 2198d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine/* Encapsulates a double-linked, circular list. 2298d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine * The list is organized in the following way: 2398d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine * - List entries contain references to the next, and the previous entry in the 2498d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine * list. 2598d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine * - The list is circular, i.e. the "last" list entry references the "list head" 2698d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine * in its 'next' reference, and the "list head" references the "last" entry in 2798d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine * its 'previous' reference. 2898d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine * - The list is empty if its 'next' and 'previous' references are addressing the 2998d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine * head of the list. 3098d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine */ 3198d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkinetypedef struct ACList ACList; 3298d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkinestruct ACList { 3398d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine /* Next entry in the list */ 3498d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine ACList* next; 3598d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine /* Previous entry in the list */ 3698d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine ACList* prev; 3798d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine}; 3898d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine 3998d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine/* Initializes the list. */ 4098d32ba363442a963bac163496513329a44a7959Vladimir ChtchetkineAINLINED void 4198d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkinealist_init(ACList* list) 4298d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine{ 4398d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine list->next = list->prev = list; 4498d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine} 4598d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine 4698d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine/* Checks if the list is empty. */ 4798d32ba363442a963bac163496513329a44a7959Vladimir ChtchetkineAINLINED int 4898d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkinealist_is_empty(const ACList* list) 4998d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine{ 5098d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine return list->next == list; 5198d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine} 5298d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine 5398d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine/* Inserts an entry to the head of the list */ 5498d32ba363442a963bac163496513329a44a7959Vladimir ChtchetkineAINLINED void 5598d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkinealist_insert_head(ACList* list, ACList* entry) 5698d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine{ 5798d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine ACList* const next = list->next; 5898d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine entry->next = next; 5998d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine entry->prev = list; 6098d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine next->prev = entry; 6198d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine list->next = entry; 6298d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine} 6398d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine/* Inserts an entry to the tail of the list */ 6498d32ba363442a963bac163496513329a44a7959Vladimir ChtchetkineAINLINED void 6598d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkinealist_insert_tail(ACList* list, ACList* entry) 6698d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine{ 6798d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine ACList* const prev = list->prev; 6898d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine entry->next = list; 6998d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine entry->prev = prev; 7098d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine prev->next = entry; 7198d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine list->prev = entry; 7298d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine} 7398d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine 7498d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine/* Removes an entry from the list. NOTE: Entry must be in the list when this 7598d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine * routine is called. */ 7698d32ba363442a963bac163496513329a44a7959Vladimir ChtchetkineAINLINED void 7798d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkinealist_remove(ACList* entry) 7898d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine{ 7998d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine ACList* const next = entry->next; 8098d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine ACList* const prev = entry->prev; 8198d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine prev->next = next; 8298d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine next->prev = prev; 8398d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine entry->next = entry->prev = entry; 8498d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine} 8598d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine 8698d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine/* Returns an entry removed from the head of the list. If the list was empty, 8798d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine * this routine returns NULL. */ 8898d32ba363442a963bac163496513329a44a7959Vladimir ChtchetkineAINLINED ACList* 8998d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkinealist_remove_head(ACList* list) 9098d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine{ 9198d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine ACList* entry = NULL; 9298d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine if (!alist_is_empty(list)) { 9398d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine entry = list->next; 9498d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine list->next = entry->next; 9598d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine entry->next->prev = list; 9698d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine entry->next = entry->prev = entry; 9798d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine } 9898d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine return entry; 9998d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine} 10098d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine 10198d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine/* Returns an entry removed from the tail of the list. If the list was empty, 10298d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine * this routine returns NULL. */ 10398d32ba363442a963bac163496513329a44a7959Vladimir ChtchetkineAINLINED ACList* 10498d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkinealist_remove_tail(ACList* list) 10598d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine{ 10698d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine ACList* entry = NULL; 10798d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine if (!alist_is_empty(list)) { 10898d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine entry = list->prev; 10998d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine list->prev = entry->prev; 11098d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine entry->prev->next = list; 11198d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine entry->next = entry->prev = entry; 11298d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine } 11398d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine return entry; 11498d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine} 11598d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine 116f0c747e01328e713891f2fa66c4f9df64f580dc2David 'Digit' TurnerANDROID_END_HEADER 117f0c747e01328e713891f2fa66c4f9df64f580dc2David 'Digit' Turner 11898d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine#endif /* _ANDROID_UTILS_LIST_H */ 119