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 Lesser 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  * Lesser General Public License for more details.
  16  *
  17  * You should have received a copy of the GNU Lesser 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 #ifdef HAVE_CONFIG_H
  28 #include <config.h>
  29 #endif
  30
  31 #include "glib.h"
  32
  33
  34 G_LOCK_DEFINE_STATIC (queue_memchunk);
  35 static GMemChunk   *queue_memchunk = NULL;
  36 static GTrashStack *free_queue_nodes = NULL;
  37
  38 /**
  39  * g_queue_new:
  40  *
  41  * Creates a new #GQueue.
  42  *
  43  * Returns: a new #GQueue.
  44  **/
  45 GQueue*
  46 g_queue_new (void)
  47 {
  48   GQueue *queue;
  49
  50   G_LOCK (queue_memchunk);
  51   queue = g_trash_stack_pop (&free_queue_nodes);
  52
  53   if (!queue)
  54     {
  55       if (!queue_memchunk)
  56         queue_memchunk = g_mem_chunk_new ("GLib GQueue chunk",
  57                                           sizeof (GNode),
  58                                           sizeof (GNode) * 128,
  59                                           G_ALLOC_ONLY);
  60       queue = g_chunk_new (GQueue, queue_memchunk);
  61     }
  62   G_UNLOCK (queue_memchunk);
  63
  64   queue->head = NULL;
  65   queue->tail = NULL;
  66   queue->length = 0;
  67
  68   return queue;
  69 }
  70
  71 /**
  72  * g_queue_free:
  73  * @queue: a #GQueue.
  74  *
  75  * Frees the memory allocated for the #GQueue.
  76  **/
  77 void
  78 g_queue_free (GQueue *queue)
  79 {
  80   g_return_if_fail (queue != NULL);
  81
  82   g_list_free (queue->head);
  83
  84 #ifdef ENABLE_GC_FRIENDLY
  85   queue->head = NULL;
  86   queue->tail = NULL;
  87 #endif /* ENABLE_GC_FRIENDLY */
  88
  89   G_LOCK (queue_memchunk);
  90   g_trash_stack_push (&free_queue_nodes, queue);
  91   G_UNLOCK (queue_memchunk);
  92 }
  93
  94 /**
  95  * g_queue_push_head:
  96  * @queue: a #GQueue.
  97  * @data: the data for the new element.
  98  *
  99  * Adds a new element at the head of the queue.
 100  **/
 101 void
 102 g_queue_push_head (GQueue  *queue,
 103                    gpointer data)
 104 {
 105   g_return_if_fail (queue != NULL);
 106
 107   queue->head = g_list_prepend (queue->head, data);
 108   if (!queue->tail)
 109     queue->tail = queue->head;
 110   queue->length++;
 111 }
 112
 113 /**
 114  * g_queue_push_head_link:
 115  * @queue: a #GQueue.
 116  * @link: a single #GList element, <emphasis>not</emphasis> a list with
 117  *   more than one element.
 118  *
 119  * Adds a new element at the head of the queue.
 120  **/
 121 void
 122 g_queue_push_head_link (GQueue *queue,
 123                         GList  *link)
 124 {
 125   g_return_if_fail (queue != NULL);
 126   g_return_if_fail (link != NULL);
 127   g_return_if_fail (link->prev == NULL);
 128   g_return_if_fail (link->next == NULL);
 129
 130   link->next = queue->head;
 131   if (queue->head)
 132     queue->head->prev = link;
 133   else
 134     queue->tail = link;
 135   queue->head = link;
 136   queue->length++;
 137 }
 138
 139 /**
 140  * g_queue_push_tail:
 141  * @queue: a #GQueue.
 142  * @data: the data for the new element.
 143  *
 144  * Adds a new element at the tail of the queue.
 145  **/
 146 void
 147 g_queue_push_tail (GQueue  *queue,
 148                    gpointer data)
 149 {
 150   g_return_if_fail (queue != NULL);
 151
 152   queue->tail = g_list_append (queue->tail, data);
 153   if (queue->tail->next)
 154     queue->tail = queue->tail->next;
 155   else
 156     queue->head = queue->tail;
 157   queue->length++;
 158 }
 159
 160 /**
 161  * g_queue_push_tail_link:
 162  * @queue: a #GQueue.
 163  * @link: a single #GList element, <emphasis>not</emphasis> a list with
 164  *   more than one element.
 165  *
 166  * Adds a new element at the tail of the queue.
 167  **/
 168 void
 169 g_queue_push_tail_link (GQueue *queue,
 170                         GList  *link)
 171 {
 172   g_return_if_fail (queue != NULL);
 173   g_return_if_fail (link != NULL);
 174   g_return_if_fail (link->prev == NULL);
 175   g_return_if_fail (link->next == NULL);
 176
 177   link->prev = queue->tail;
 178   if (queue->tail)
 179     queue->tail->next = link;
 180   else
 181     queue->head = link;
 182   queue->tail = link;
 183   queue->length++;
 184 }
 185
 186 /**
 187  * g_queue_pop_head:
 188  * @queue: a #GQueue.
 189  *
 190  * Removes the first element of the queue.
 191  *
 192  * Returns: the data of the first element in the queue, or %NULL if the queue
 193  *   is empty.
 194  **/
 195 gpointer
 196 g_queue_pop_head (GQueue *queue)
 197 {
 198   g_return_val_if_fail (queue != NULL, NULL);
 199
 200   if (queue->head)
 201     {
 202       GList *node = queue->head;
 203       gpointer data = node->data;
 204
 205       queue->head = node->next;
 206       if (queue->head)
 207         queue->head->prev = NULL;
 208       else
 209         queue->tail = NULL;
 210       g_list_free_1 (node);
 211       queue->length--;
 212
 213       return data;
 214     }
 215
 216   return NULL;
 217 }
 218
 219 /**
 220  * g_queue_pop_head_link:
 221  * @queue: a #GQueue.
 222  *
 223  * Removes the first element of the queue.
 224  *
 225  * Returns: the #GList element at the head of the queue, or %NULL if the queue
 226  *   is empty.
 227  **/
 228 GList*
 229 g_queue_pop_head_link (GQueue *queue)
 230 {
 231   g_return_val_if_fail (queue != NULL, NULL);
 232
 233   if (queue->head)
 234     {
 235       GList *node = queue->head;
 236
 237       queue->head = node->next;
 238       if (queue->head)
 239         {
 240           queue->head->prev = NULL;
 241           node->next = NULL;
 242         }
 243       else
 244         queue->tail = NULL;
 245       queue->length--;
 246
 247       return node;
 248     }
 249
 250   return NULL;
 251 }
 252
 253 /**
 254  * g_queue_pop_tail:
 255  * @queue: a #GQueue.
 256  *
 257  * Removes the last element of the queue.
 258  *
 259  * Returns: the data of the last element in the queue, or %NULL if the queue
 260  *   is empty.
 261  **/
 262 gpointer
 263 g_queue_pop_tail (GQueue *queue)
 264 {
 265   g_return_val_if_fail (queue != NULL, NULL);
 266
 267   if (queue->tail)
 268     {
 269       GList *node = queue->tail;
 270       gpointer data = node->data;
 271
 272       queue->tail = node->prev;
 273       if (queue->tail)
 274         queue->tail->next = NULL;
 275       else
 276         queue->head = NULL;
 277       queue->length--;
 278       g_list_free_1 (node);
 279
 280       return data;
 281     }
 282
 283   return NULL;
 284 }
 285
 286 /**
 287  * g_queue_pop_tail_link:
 288  * @queue: a #GQueue.
 289  *
 290  * Removes the last element of the queue.
 291  *
 292  * Returns: the #GList element at the tail of the queue, or %NULL if the queue
 293  *   is empty.
 294  **/
 295 GList*
 296 g_queue_pop_tail_link (GQueue *queue)
 297 {
 298   g_return_val_if_fail (queue != NULL, NULL);
 299
 300   if (queue->tail)
 301     {
 302       GList *node = queue->tail;
 303
 304       queue->tail = node->prev;
 305       if (queue->tail)
 306         {
 307           queue->tail->next = NULL;
 308           node->prev = NULL;
 309         }
 310       else
 311         queue->head = NULL;
 312       queue->length--;
 313
 314       return node;
 315     }
 316
 317   return NULL;
 318 }
 319
 320 /**
 321  * g_queue_is_empty:
 322  * @queue: a #GQueue.
 323  *
 324  * Returns %TRUE if the queue is empty.
 325  *
 326  * Returns: %TRUE if the queue is empty.
 327  **/
 328 gboolean
 329 g_queue_is_empty (GQueue *queue)
 330 {
 331   g_return_val_if_fail (queue != NULL, TRUE);
 332
 333   return queue->head == NULL;
 334 }
 335
 336 /**
 337  * g_queue_peek_head:
 338  * @queue: a #GQueue.
 339  *
 340  * Returns the first element of the queue.
 341  *
 342  * Returns: the data of the first element in the queue, or %NULL if the queue
 343  *   is empty.
 344  **/
 345 gpointer
 346 g_queue_peek_head (GQueue *queue)
 347 {
 348   g_return_val_if_fail (queue != NULL, NULL);
 349
 350   return queue->head ? queue->head->data : NULL;
 351 }
 352
 353 /**
 354  * g_queue_peek_tail:
 355  * @queue: a #GQueue.
 356  *
 357  * Returns the last element of the queue.
 358  *
 359  * Returns: the data of the last element in the queue, or %NULL if the queue
 360  *   is empty.
 361  **/
 362 gpointer
 363 g_queue_peek_tail (GQueue *queue)
 364 {
 365   g_return_val_if_fail (queue != NULL, NULL);
 366
 367   return queue->tail ? queue->tail->data : NULL;
 368 }