camel/camel-list-utils.h

   1 /*
   2  * Authors: Michael Zucchi <notzed@ximian.com>
   3  *
   4  * Copyright 2004 Novell, Inc. (www.novell.com)
   5  *
   6  * This program is free software; you can redistribute it and/or
   7  * modify it under the terms of version 2 of the GNU Lesser General Public
   8  * License as published by the Free Software Foundation.
   9  *
  10  * This program is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13  * General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU Lesser General Public
  16  * License along with this program; if not, write to the
  17  * Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  18  * Boston, MA 02110-1301, USA.
  19  *
  20  */
  21
  22 #ifndef _CAMEL_LIST_UTILS_H
  23 #define _CAMEL_LIST_UTILS_H
  24
  25 G_BEGIN_DECLS
  26
  27 /* This is a copy of Amiga's Exec lists, the head and tail nodes are
  28  * overlapped and merged into a single list header.  All operations
  29  * are O(1), including node removal and addition from/to either end of
  30  * the list.  It can be used to implement O(1) queues, fifo's and
  31  * normal lists.  You don't need the list header to remove the node. */
  32
  33 typedef struct _CamelDList CamelDList;
  34 typedef struct _CamelDListNode CamelDListNode;
  35
  36 /**
  37  * struct _CamelDListNode - A double-linked list node.
  38  *
  39  * @next: The next node link.
  40  * @prev: The previous node link.
  41  *
  42  * A double-linked list node header.  Put this at the start of the
  43  * list node structure.  Data is stored in the list by subclassing the
  44  * node header rather than using a pointer.  Or more normally by just
  45  * duplicating the next and previous pointers for better type safety.
  46  **/
  47 struct _CamelDListNode {
  48         struct _CamelDListNode *next;
  49         struct _CamelDListNode *prev;
  50 };
  51
  52 /**
  53  * struct _CamelDList - A double-linked list header.
  54  *
  55  * @head: The head node's next pointer.
  56  * @tail: The tail node's next pointer.
  57  * @tailpred: The previous node to the tail node.
  58  *
  59  * This is the merging of two separate head and tail nodes into a
  60  * single structure.  i.e. if you ahve a NULL terminated head and tail
  61  * node such as head = { first, NULL } and tail = { NULL, last } then
  62  * overlap them at the common NULL, you get this structure.
  63  *
  64  * The list header must be initialised with camel_dlist_init, or by
  65  * using the static CAMEL_DLIST_INITIALISER macro.
  66  **/
  67 struct _CamelDList {
  68         struct _CamelDListNode *head;
  69         struct _CamelDListNode *tail;
  70         struct _CamelDListNode *tailpred;
  71 };
  72
  73 #define CAMEL_DLIST_INITIALISER(l) { (CamelDListNode *)&l.tail, 0, (CamelDListNode *)&l.head }
  74
  75 void camel_dlist_init(CamelDList *v);
  76 CamelDListNode *camel_dlist_addhead(CamelDList *l, CamelDListNode *n);
  77 CamelDListNode *camel_dlist_addtail(CamelDList *l, CamelDListNode *n);
  78 CamelDListNode *camel_dlist_remove(CamelDListNode *n);
  79 CamelDListNode *camel_dlist_remhead(CamelDList *l);
  80 CamelDListNode *camel_dlist_remtail(CamelDList *l);
  81 int camel_dlist_empty(CamelDList *l);
  82 int camel_dlist_length(CamelDList *l);
  83
  84 /* This is provided mostly for orthogonality with the dlist structure.
  85  * By making the nodes contain all of the data themselves it
  86  * simplifies memory management.  Removing and adding from/to the head
  87  * of the list is O(1), the rest of the operations are O(n). */
  88
  89 typedef struct _CamelSListNode CamelSListNode;
  90 typedef struct _CamelSList CamelSList;
  91
  92 /**
  93  * struct _CamelSListNode - A single-linked list node.
  94  *
  95  * @next: The next node in the list.
  96  *
  97  * A single-linked list node header.  Put this at hte start of the
  98  * actual list node structure, or more commonly, just a next pointer.
  99  * Data is stored in the list node by subclassing the node-header
 100  * rather than using a pointer.
 101  **/
 102 struct _CamelSListNode {
 103         struct _CamelSListNode *next;
 104 };
 105
 106 /**
 107  * struct _CamelSList - A single-linked list header.
 108  *
 109  * @head: The head of the list.
 110  *
 111  * This is the header of a single-linked list.
 112  **/
 113 struct _CamelSList {
 114         struct _CamelSListNode *head;
 115 };
 116
 117 #define CAMEL_SLIST_INITIALISER(l) { 0 }
 118
 119 void camel_slist_init(CamelSList *l);
 120 CamelSListNode *camel_slist_addhead(CamelSList *l, CamelSListNode *n);
 121 CamelSListNode *camel_slist_addtail(CamelSList *l, CamelSListNode *n);
 122 CamelSListNode *camel_slist_remove(CamelSList *l, CamelSListNode *n);
 123 CamelSListNode *camel_slist_remhead(CamelSList *l);
 124 CamelSListNode *camel_slist_remtail(CamelSList *l);
 125 int camel_slist_empty(CamelSList *l);
 126 int camel_slist_length(CamelSList *l);
 127
 128 G_END_DECLS
 129
 130 #endif