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