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 GQueue*
  39 g_queue_new (void)
  40 {
  41   GQueue *queue;
  42
  43   G_LOCK (queue_memchunk);
  44   queue = g_trash_stack_pop (&free_queue_nodes);
  45
  46   if (!queue)
  47     {
  48       if (!queue_memchunk)
  49         queue_memchunk = g_mem_chunk_new ("GLib GQueue chunk",
  50                                           sizeof (GNode),
  51                                           sizeof (GNode) * 128,
  52                                           G_ALLOC_ONLY);
  53       queue = g_chunk_new (GQueue, queue_memchunk);
  54     }
  55   G_UNLOCK (queue_memchunk);
  56
  57   queue->head = NULL;
  58   queue->tail = NULL;
  59   queue->length = 0;
  60
  61   return queue;
  62 }
  63
  64 void
  65 g_queue_free (GQueue *queue)
  66 {
  67   g_return_if_fail (queue != NULL);
  68
  69   g_list_free (queue->head);
  70
  71 #ifdef ENABLE_GC_FRIENDLY
  72   queue->head = NULL;
  73   queue->tail = NULL;
  74 #endif /* ENABLE_GC_FRIENDLY */
  75
  76   G_LOCK (queue_memchunk);
  77   g_trash_stack_push (&free_queue_nodes, queue);
  78   G_UNLOCK (queue_memchunk);
  79 }
  80
  81 void
  82 g_queue_push_head (GQueue  *queue,
  83                    gpointer data)
  84 {
  85   g_return_if_fail (queue != NULL);
  86
  87   queue->head = g_list_prepend (queue->head, data);
  88   if (!queue->tail)
  89     queue->tail = queue->head;
  90   queue->length++;
  91 }
  92
  93 void
  94 g_queue_push_head_link (GQueue *queue,
  95                         GList  *link)
  96 {
  97   g_return_if_fail (queue != NULL);
  98   g_return_if_fail (link != NULL);
  99   g_return_if_fail (link->prev == NULL);
 100   g_return_if_fail (link->next == NULL);
 101
 102   link->next = queue->head;
 103   if (queue->head)
 104     queue->head->prev = link;
 105   else
 106     queue->tail = link;
 107   queue->head = link;
 108   queue->length++;
 109 }
 110
 111 void
 112 g_queue_push_tail (GQueue  *queue,
 113                    gpointer data)
 114 {
 115   g_return_if_fail (queue != NULL);
 116
 117   queue->tail = g_list_append (queue->tail, data);
 118   if (queue->tail->next)
 119     queue->tail = queue->tail->next;
 120   else
 121     queue->head = queue->tail;
 122   queue->length++;
 123 }
 124
 125 void
 126 g_queue_push_tail_link (GQueue *queue,
 127                         GList  *link)
 128 {
 129   g_return_if_fail (queue != NULL);
 130   g_return_if_fail (link != NULL);
 131   g_return_if_fail (link->prev == NULL);
 132   g_return_if_fail (link->next == NULL);
 133
 134   link->prev = queue->tail;
 135   if (queue->tail)
 136     queue->tail->next = link;
 137   else
 138     queue->head = link;
 139   queue->tail = link;
 140   queue->length++;
 141 }
 142
 143 gpointer
 144 g_queue_pop_head (GQueue *queue)
 145 {
 146   g_return_val_if_fail (queue != NULL, NULL);
 147
 148   if (queue->head)
 149     {
 150       GList *node = queue->head;
 151       gpointer data = node->data;
 152
 153       queue->head = node->next;
 154       if (queue->head)
 155         queue->head->prev = NULL;
 156       else
 157         queue->tail = NULL;
 158       g_list_free_1 (node);
 159       queue->length--;
 160
 161       return data;
 162     }
 163
 164   return NULL;
 165 }
 166
 167 GList*
 168 g_queue_pop_head_link (GQueue *queue)
 169 {
 170   g_return_val_if_fail (queue != NULL, NULL);
 171
 172   if (queue->head)
 173     {
 174       GList *node = queue->head;
 175
 176       queue->head = node->next;
 177       if (queue->head)
 178         {
 179           queue->head->prev = NULL;
 180           node->next = NULL;
 181         }
 182       else
 183         queue->tail = NULL;
 184       queue->length--;
 185
 186       return node;
 187     }
 188
 189   return NULL;
 190 }
 191
 192 gpointer
 193 g_queue_pop_tail (GQueue *queue)
 194 {
 195   g_return_val_if_fail (queue != NULL, NULL);
 196
 197   if (queue->tail)
 198     {
 199       GList *node = queue->tail;
 200       gpointer data = node->data;
 201
 202       queue->tail = node->prev;
 203       if (queue->tail)
 204         queue->tail->next = NULL;
 205       else
 206         queue->head = NULL;
 207       queue->length--;
 208       g_list_free_1 (node);
 209
 210       return data;
 211     }
 212
 213   return NULL;
 214 }
 215
 216 GList*
 217 g_queue_pop_tail_link (GQueue *queue)
 218 {
 219   g_return_val_if_fail (queue != NULL, NULL);
 220
 221   if (queue->tail)
 222     {
 223       GList *node = queue->tail;
 224
 225       queue->tail = node->prev;
 226       if (queue->tail)
 227         {
 228           queue->tail->next = NULL;
 229           node->prev = NULL;
 230         }
 231       else
 232         queue->head = NULL;
 233       queue->length--;
 234
 235       return node;
 236     }
 237
 238   return NULL;
 239 }
 240
 241 gboolean
 242 g_queue_is_empty (GQueue *queue)
 243 {
 244   g_return_val_if_fail (queue != NULL, TRUE);
 245
 246   return queue->head == NULL;
 247 }
 248
 249 gpointer
 250 g_queue_peek_head (GQueue *queue)
 251 {
 252   g_return_val_if_fail (queue != NULL, NULL);
 253
 254   return queue->head ? queue->head->data : NULL;
 255 }
 256
 257 gpointer
 258 g_queue_peek_tail (GQueue *queue)
 259 {
 260   g_return_val_if_fail (queue != NULL, NULL);
 261
 262   return queue->tail ? queue->tail->data : NULL;
 263 }