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