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 1798d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine/* Encapsulates a double-linked, circular list. 1898d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine * The list is organized in the following way: 1998d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine * - List entries contain references to the next, and the previous entry in the 2098d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine * list. 2198d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine * - The list is circular, i.e. the "last" list entry references the "list head" 2298d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine * in its 'next' reference, and the "list head" references the "last" entry in 2398d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine * its 'previous' reference. 2498d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine * - The list is empty if its 'next' and 'previous' references are addressing the 2598d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine * head of the list. 2698d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine */ 2798d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkinetypedef struct ACList ACList; 2898d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkinestruct ACList { 2998d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine /* Next entry in the list */ 3098d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine ACList* next; 3198d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine /* Previous entry in the list */ 3298d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine ACList* prev; 3398d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine}; 3498d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine 3598d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine/* Initializes the list. */ 3698d32ba363442a963bac163496513329a44a7959Vladimir ChtchetkineAINLINED void 3798d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkinealist_init(ACList* list) 3898d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine{ 3998d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine list->next = list->prev = list; 4098d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine} 4198d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine 4298d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine/* Checks if the list is empty. */ 4398d32ba363442a963bac163496513329a44a7959Vladimir ChtchetkineAINLINED int 4498d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkinealist_is_empty(const ACList* list) 4598d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine{ 4698d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine return list->next == list; 4798d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine} 4898d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine 4998d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine/* Inserts an entry to the head of the list */ 5098d32ba363442a963bac163496513329a44a7959Vladimir ChtchetkineAINLINED void 5198d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkinealist_insert_head(ACList* list, ACList* entry) 5298d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine{ 5398d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine ACList* const next = list->next; 5498d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine entry->next = next; 5598d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine entry->prev = list; 5698d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine next->prev = entry; 5798d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine list->next = entry; 5898d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine} 5998d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine/* Inserts an entry to the tail of the list */ 6098d32ba363442a963bac163496513329a44a7959Vladimir ChtchetkineAINLINED void 6198d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkinealist_insert_tail(ACList* list, ACList* entry) 6298d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine{ 6398d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine ACList* const prev = list->prev; 6498d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine entry->next = list; 6598d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine entry->prev = prev; 6698d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine prev->next = entry; 6798d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine list->prev = entry; 6898d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine} 6998d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine 7098d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine/* Removes an entry from the list. NOTE: Entry must be in the list when this 7198d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine * routine is called. */ 7298d32ba363442a963bac163496513329a44a7959Vladimir ChtchetkineAINLINED void 7398d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkinealist_remove(ACList* entry) 7498d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine{ 7598d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine ACList* const next = entry->next; 7698d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine ACList* const prev = entry->prev; 7798d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine prev->next = next; 7898d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine next->prev = prev; 7998d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine entry->next = entry->prev = entry; 8098d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine} 8198d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine 8298d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine/* Returns an entry removed from the head of the list. If the list was empty, 8398d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine * this routine returns NULL. */ 8498d32ba363442a963bac163496513329a44a7959Vladimir ChtchetkineAINLINED ACList* 8598d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkinealist_remove_head(ACList* list) 8698d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine{ 8798d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine ACList* entry = NULL; 8898d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine if (!alist_is_empty(list)) { 8998d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine entry = list->next; 9098d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine list->next = entry->next; 9198d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine entry->next->prev = list; 9298d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine entry->next = entry->prev = entry; 9398d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine } 9498d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine return entry; 9598d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine} 9698d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine 9798d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine/* Returns an entry removed from the tail of the list. If the list was empty, 9898d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine * this routine returns NULL. */ 9998d32ba363442a963bac163496513329a44a7959Vladimir ChtchetkineAINLINED ACList* 10098d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkinealist_remove_tail(ACList* list) 10198d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine{ 10298d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine ACList* entry = NULL; 10398d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine if (!alist_is_empty(list)) { 10498d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine entry = list->prev; 10598d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine list->prev = entry->prev; 10698d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine entry->prev->next = list; 10798d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine entry->next = entry->prev = entry; 10898d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine } 10998d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine return entry; 11098d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine} 11198d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine 11298d32ba363442a963bac163496513329a44a7959Vladimir Chtchetkine#endif /* _ANDROID_UTILS_LIST_H */ 113