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