glib/gqueue.c

   1 /* GLIB - Library of useful routines for C programming
   2  * Copyright (C) 1995-1997  Peter Mattis, Spencer Kimball and Josh MacDonald
   3  *
   4  * GQueue: Double ended queue implementation, piggy backed on GList.
   5  * Copyright (C) 1998 Tim Janik
   6  *
   7  * This library is free software; you can redistribute it and/or
   8  * modify it under the terms of the GNU Library General Public
   9  * License as published by the Free Software Foundation; either
  10  * version 2 of the License, or (at your option) any later version.
  11  *
  12  * This library is distributed in the hope that it will be useful,
  13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15  * Library General Public License for more details.
  16  *
  17  * You should have received a copy of the GNU Library General Public
  18  * License along with this library; if not, write to the
  19  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  20  * Boston, MA 02111-1307, USA.
  21  */
  22
  23 /*
  24  * MT safe
  25  */
  26
  27 #include "glib.h"
  28
  29
  30 G_LOCK_DEFINE_STATIC (queue_memchunk);
  31 static GMemChunk   *queue_memchunk = NULL;
  32 static GTrashStack *free_queue_nodes = NULL;
  33
  34 GQueue*
  35 g_queue_create (void)
  36 {
  37   GQueue *queue;
  38
  39   G_LOCK (queue_memchunk);
  40   queue = g_trash_stack_pop (&free_queue_nodes);
  41
  42   if (!queue)
  43     {
  44       if (!queue_memchunk)
  45         queue_memchunk = g_mem_chunk_new ("GLib GQueue chunk",
  46                                           sizeof (GNode),
  47                                           sizeof (GNode) * 128,
  48                                           G_ALLOC_ONLY);
  49       queue = g_chunk_new (GQueue, queue_memchunk);
  50     }
  51   G_UNLOCK (queue_memchunk);
  52
  53   queue->head = NULL;
  54   queue->tail = NULL;
  55   queue->length = 0;
  56
  57   return queue;
  58 }
  59
  60 void
  61 g_queue_free (GQueue *queue)
  62 {
  63   g_return_if_fail (queue != NULL);
  64
  65   g_list_free (queue->head);
  66
  67   G_LOCK (queue_memchunk);
  68   g_trash_stack_push (&free_queue_nodes, queue);
  69   G_UNLOCK (queue_memchunk);
  70 }
  71
  72 void
  73 g_queue_push_head (GQueue  *queue,
  74                    gpointer data)
  75 {
  76   g_return_if_fail (queue != NULL);
  77
  78   queue->head = g_list_prepend (queue->head, data);
  79   if (!queue->tail)
  80     queue->tail = queue->head;
  81   queue->length++;
  82 }
  83
  84 void
  85 g_queue_push_head_link (GQueue *queue,
  86                         GList  *link)
  87 {
  88   g_return_if_fail (queue != NULL);
  89   g_return_if_fail (link != NULL);
  90   g_return_if_fail (link->prev != NULL);
  91   g_return_if_fail (link->next != NULL);
  92
  93   link->next = queue->head;
  94   if (queue->head)
  95     queue->head->prev = link;
  96   else
  97     queue->tail = link;
  98   queue->head = link;
  99   queue->length++;
 100 }
 101
 102 void
 103 g_queue_push_tail (GQueue  *queue,
 104                    gpointer data)
 105 {
 106   g_return_if_fail (queue != NULL);
 107
 108   queue->tail = g_list_append (queue->tail, data);
 109   if (queue->tail->next)
 110     queue->tail = queue->tail->next;
 111   else
 112     queue->head = queue->tail;
 113   queue->length++;
 114 }
 115
 116 void
 117 g_queue_push_tail_link (GQueue *queue,
 118                         GList  *link)
 119 {
 120   g_return_if_fail (queue != NULL);
 121   g_return_if_fail (link != NULL);
 122   g_return_if_fail (link->prev != NULL);
 123   g_return_if_fail (link->next != NULL);
 124
 125   link->prev = queue->tail;
 126   if (queue->tail)
 127     queue->tail->next = link;
 128   else
 129     queue->head = link;
 130   queue->tail = link;
 131   queue->length++;
 132 }
 133
 134 gpointer
 135 g_queue_pop_head (GQueue *queue)
 136 {
 137   g_return_val_if_fail (queue != NULL, NULL);
 138
 139   if (queue->head)
 140     {
 141       GList *node = queue->head;
 142       gpointer data = node->data;
 143
 144       queue->head = node->next;
 145       if (queue->head)
 146         queue->head->prev = NULL;
 147       else
 148         queue->tail = NULL;
 149       g_list_free_1 (node);
 150       queue->length--;
 151
 152       return data;
 153     }
 154
 155   return NULL;
 156 }
 157
 158 GList*
 159 g_queue_pop_head_link (GQueue *queue)
 160 {
 161   g_return_val_if_fail (queue != NULL, NULL);
 162
 163   if (queue->head)
 164     {
 165       GList *node = queue->head;
 166
 167       queue->head = node->next;
 168       if (queue->head)
 169         {
 170           queue->head->prev = NULL;
 171           node->next = NULL;
 172         }
 173       else
 174         queue->tail = NULL;
 175       queue->length--;
 176
 177       return node;
 178     }
 179
 180   return NULL;
 181 }
 182
 183 gpointer
 184 g_queue_pop_tail (GQueue *queue)
 185 {
 186   g_return_val_if_fail (queue != NULL, NULL);
 187
 188   if (queue->tail)
 189     {
 190       GList *node = queue->tail;
 191       gpointer data = node->data;
 192
 193       queue->tail = node->prev;
 194       if (queue->tail)
 195         queue->tail->next = NULL;
 196       else
 197         queue->head = NULL;
 198       queue->length--;
 199       g_list_free_1 (node);
 200
 201       return data;
 202     }
 203
 204   return NULL;
 205 }
 206
 207 GList*
 208 g_queue_pop_tail_link (GQueue *queue)
 209 {
 210   g_return_val_if_fail (queue != NULL, NULL);
 211
 212   if (queue->tail)
 213     {
 214       GList *node = queue->tail;
 215
 216       queue->tail = node->prev;
 217       if (queue->tail)
 218         {
 219           queue->tail->next = NULL;
 220           node->prev = NULL;
 221         }
 222       else
 223         queue->head = NULL;
 224       queue->length--;
 225
 226       return node;
 227     }
 228
 229   return NULL;
 230 }
 231
 232 gboolean
 233 g_queue_is_empty (GQueue *queue)
 234 {
 235   g_return_val_if_fail (queue != NULL, TRUE);
 236
 237   return queue->head == NULL;
 238 }
 239
 240 gpointer
 241 g_queue_peek_head (GQueue *queue)
 242 {
 243   g_return_val_if_fail (queue != NULL, NULL);
 244
 245   return queue->head ? queue->head->data : NULL;
 246 }
 247
 248 gpointer
 249 g_queue_peek_tail (GQueue *queue)
 250 {
 251   g_return_val_if_fail (queue != NULL, NULL);
 252
 253   return queue->tail ? queue->tail->data : NULL;
 254 }