glist.c 7.52 KB
Newer Older
Elliot Lee's avatar
Elliot Lee committed
1 2 3 4 5 6 7 8 9 10
/* GLIB - Library of useful routines for C programming
 * Copyright (C) 1995-1997  Peter Mattis, Spencer Kimball and Josh MacDonald
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Library General Public
 * License as published by the Free Software Foundation; either
 * version 2 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.	 See the GNU
Elliot Lee's avatar
Elliot Lee committed
12 13 14
 * Library General Public License for more details.
 *
 * You should have received a copy of the GNU Library General Public
15 16 17
 * License along with this library; if not, write to the
 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
 * Boston, MA 02111-1307, USA.
Elliot Lee's avatar
Elliot Lee committed
18 19 20 21 22 23 24 25 26
 */
#include "glib.h"


typedef struct _GRealListAllocator GRealListAllocator;

struct _GRealListAllocator
{
  GMemChunk *list_mem_chunk;
27
  GList	    *free_list;
Elliot Lee's avatar
Elliot Lee committed
28 29 30 31 32 33 34 35 36 37 38
};


static GRealListAllocator *default_allocator = NULL;
static GRealListAllocator *current_allocator = NULL;


GListAllocator*
g_list_allocator_new ()
{
  GRealListAllocator* allocator = g_new (GRealListAllocator, 1);
39
  
Elliot Lee's avatar
Elliot Lee committed
40 41
  allocator->list_mem_chunk = NULL;
  allocator->free_list = NULL;
42
  
Elliot Lee's avatar
Elliot Lee committed
43 44 45 46 47 48 49
  return (GListAllocator*) allocator;
}

void
g_list_allocator_free (GListAllocator* fallocator)
{
  GRealListAllocator* allocator = (GRealListAllocator *) fallocator;
50
  
Elliot Lee's avatar
Elliot Lee committed
51 52 53 54 55 56 57 58 59 60 61
  if (allocator && allocator->list_mem_chunk)
    g_mem_chunk_destroy (allocator->list_mem_chunk);
  if (allocator)
    g_free (allocator);
}

GListAllocator*
g_list_set_allocator (GListAllocator* fallocator)
{
  GRealListAllocator* allocator = (GRealListAllocator *) fallocator;
  GRealListAllocator* old_allocator = current_allocator;
62
  
Elliot Lee's avatar
Elliot Lee committed
63 64 65 66 67 68 69 70
  if (allocator)
    current_allocator = allocator;
  else
    {
      if (!default_allocator)
	default_allocator = (GRealListAllocator*) g_list_allocator_new ();
      current_allocator = default_allocator;
    }
71
  
Elliot Lee's avatar
Elliot Lee committed
72 73 74 75 76
  if (!current_allocator->list_mem_chunk)
    current_allocator->list_mem_chunk = g_mem_chunk_new ("list mem chunk",
							 sizeof (GList),
							 1024,
							 G_ALLOC_ONLY);
77
  
Elliot Lee's avatar
Elliot Lee committed
78 79 80 81 82 83 84 85
  return (GListAllocator*) (old_allocator == default_allocator ? NULL : old_allocator);
}


GList*
g_list_alloc ()
{
  GList *new_list;
86
  
Elliot Lee's avatar
Elliot Lee committed
87 88 89 90 91 92 93 94 95 96
  g_list_set_allocator (NULL);
  if (current_allocator->free_list)
    {
      new_list = current_allocator->free_list;
      current_allocator->free_list = current_allocator->free_list->next;
    }
  else
    {
      new_list = g_chunk_new (GList, current_allocator->list_mem_chunk);
    }
97
  
Elliot Lee's avatar
Elliot Lee committed
98 99 100
  new_list->data = NULL;
  new_list->next = NULL;
  new_list->prev = NULL;
101
  
Elliot Lee's avatar
Elliot Lee committed
102 103 104 105 106 107 108
  return new_list;
}

void
g_list_free (GList *list)
{
  GList *last;
109
  
Elliot Lee's avatar
Elliot Lee committed
110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128
  if (list)
    {
      last = g_list_last (list);
      last->next = current_allocator->free_list;
      current_allocator->free_list = list;
    }
}

void
g_list_free_1 (GList *list)
{
  if (list)
    {
      list->next = current_allocator->free_list;
      current_allocator->free_list = list;
    }
}

GList*
129 130
g_list_append (GList	*list,
	       gpointer	 data)
Elliot Lee's avatar
Elliot Lee committed
131 132 133
{
  GList *new_list;
  GList *last;
134
  
Elliot Lee's avatar
Elliot Lee committed
135 136
  new_list = g_list_alloc ();
  new_list->data = data;
137 138
  
  if (list)
Elliot Lee's avatar
Elliot Lee committed
139 140
    {
      last = g_list_last (list);
141
      /* g_assert (last != NULL); */
Elliot Lee's avatar
Elliot Lee committed
142 143 144
      last->next = new_list;
      new_list->prev = last;

145 146 147 148
      return list;
    }
  else
    return new_list;
Elliot Lee's avatar
Elliot Lee committed
149 150 151
}

GList*
152
g_list_prepend (GList	 *list,
Elliot Lee's avatar
Elliot Lee committed
153 154 155
		gpointer  data)
{
  GList *new_list;
156
  
Elliot Lee's avatar
Elliot Lee committed
157 158
  new_list = g_list_alloc ();
  new_list->data = data;
159
  
Elliot Lee's avatar
Elliot Lee committed
160 161 162
  if (list)
    {
      if (list->prev)
163 164 165 166
	{
	  list->prev->next = new_list;
	  new_list->prev = list->prev;
	}
Elliot Lee's avatar
Elliot Lee committed
167
      list->prev = new_list;
168
      new_list->next = list;
Elliot Lee's avatar
Elliot Lee committed
169
    }
170
  
Elliot Lee's avatar
Elliot Lee committed
171 172 173 174
  return new_list;
}

GList*
175 176 177
g_list_insert (GList	*list,
	       gpointer	 data,
	       gint	 position)
Elliot Lee's avatar
Elliot Lee committed
178 179 180
{
  GList *new_list;
  GList *tmp_list;
181
  
Elliot Lee's avatar
Elliot Lee committed
182 183 184 185
  if (position < 0)
    return g_list_append (list, data);
  else if (position == 0)
    return g_list_prepend (list, data);
186
  
Elliot Lee's avatar
Elliot Lee committed
187 188 189
  tmp_list = g_list_nth (list, position);
  if (!tmp_list)
    return g_list_append (list, data);
190
  
Elliot Lee's avatar
Elliot Lee committed
191 192
  new_list = g_list_alloc ();
  new_list->data = data;
193
  
Elliot Lee's avatar
Elliot Lee committed
194
  if (tmp_list->prev)
195 196 197 198
    {
      tmp_list->prev->next = new_list;
      new_list->prev = tmp_list->prev;
    }
Elliot Lee's avatar
Elliot Lee committed
199 200
  new_list->next = tmp_list;
  tmp_list->prev = new_list;
201
  
Elliot Lee's avatar
Elliot Lee committed
202
  if (tmp_list == list)
203 204 205
    return new_list;
  else
    return list;
Elliot Lee's avatar
Elliot Lee committed
206 207
}

208 209 210 211
GList *
g_list_concat (GList *list1, GList *list2)
{
  GList *tmp_list;
212
  
213 214 215 216 217 218 219 220 221
  if (list2)
    {
      tmp_list = g_list_last (list1);
      if (tmp_list)
	tmp_list->next = list2;
      else
	list1 = list2;
      list2->prev = tmp_list;
    }
222
  
223 224 225
  return list1;
}

Elliot Lee's avatar
Elliot Lee committed
226
GList*
227 228
g_list_remove (GList	*list,
	       gpointer	 data)
Elliot Lee's avatar
Elliot Lee committed
229 230
{
  GList *tmp;
231
  
Elliot Lee's avatar
Elliot Lee committed
232 233 234
  tmp = list;
  while (tmp)
    {
235 236 237
      if (tmp->data != data)
	tmp = tmp->next;
      else
Elliot Lee's avatar
Elliot Lee committed
238 239 240 241 242
	{
	  if (tmp->prev)
	    tmp->prev->next = tmp->next;
	  if (tmp->next)
	    tmp->next->prev = tmp->prev;
243
	  
Elliot Lee's avatar
Elliot Lee committed
244 245
	  if (list == tmp)
	    list = list->next;
246 247 248
	  
	  g_list_free_1 (tmp);
	  
Elliot Lee's avatar
Elliot Lee committed
249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264
	  break;
	}
    }
  return list;
}

GList*
g_list_remove_link (GList *list,
		    GList *link)
{
  if (link)
    {
      if (link->prev)
	link->prev->next = link->next;
      if (link->next)
	link->next->prev = link->prev;
265
      
Elliot Lee's avatar
Elliot Lee committed
266 267
      if (link == list)
	list = list->next;
268
      
Elliot Lee's avatar
Elliot Lee committed
269 270 271
      link->next = NULL;
      link->prev = NULL;
    }
272
  
Elliot Lee's avatar
Elliot Lee committed
273 274 275 276 277 278 279
  return list;
}

GList*
g_list_reverse (GList *list)
{
  GList *last;
280
  
Elliot Lee's avatar
Elliot Lee committed
281 282 283 284
  last = NULL;
  while (list)
    {
      last = list;
285 286 287
      list = last->next;
      last->next = last->prev;
      last->prev = list;
Elliot Lee's avatar
Elliot Lee committed
288
    }
289
  
Elliot Lee's avatar
Elliot Lee committed
290 291 292 293 294
  return last;
}

GList*
g_list_nth (GList *list,
295
	    guint  n)
Elliot Lee's avatar
Elliot Lee committed
296 297 298
{
  while ((n-- > 0) && list)
    list = list->next;
299
  
Elliot Lee's avatar
Elliot Lee committed
300 301 302
  return list;
}

303 304 305 306 307 308 309 310 311 312 313 314 315 316 317
gint
g_list_position (GList     *list,
		 GList     *link)
{
  gint nth;
  GList *curlink;
  for(nth = 0, curlink = list; curlink; curlink = g_list_next(curlink), nth++)
    {
	if(curlink == link) return nth;
    }

  return -1;
}


Elliot Lee's avatar
Elliot Lee committed
318 319 320 321 322 323 324 325 326 327
GList*
g_list_find (GList    *list,
	     gpointer  data)
{
  while (list)
    {
      if (list->data == data)
	break;
      list = list->next;
    }
328
  
Elliot Lee's avatar
Elliot Lee committed
329 330 331 332 333 334 335 336 337 338 339
  return list;
}

GList*
g_list_last (GList *list)
{
  if (list)
    {
      while (list->next)
	list = list->next;
    }
340
  
Elliot Lee's avatar
Elliot Lee committed
341 342 343 344 345 346 347 348 349
  return list;
}

GList*
g_list_first (GList *list)
{
  if (list)
    {
      while (list->prev)
350
	list = list->prev;
Elliot Lee's avatar
Elliot Lee committed
351
    }
352
  
Elliot Lee's avatar
Elliot Lee committed
353 354 355
  return list;
}

356
guint
Elliot Lee's avatar
Elliot Lee committed
357 358
g_list_length (GList *list)
{
359
  guint length;
360
  
Elliot Lee's avatar
Elliot Lee committed
361 362 363 364 365 366
  length = 0;
  while (list)
    {
      length++;
      list = list->next;
    }
367
  
Elliot Lee's avatar
Elliot Lee committed
368 369 370 371
  return length;
}

void
372 373
g_list_foreach (GList	 *list,
		GFunc	  func,
Elliot Lee's avatar
Elliot Lee committed
374 375 376 377 378 379 380 381
		gpointer  user_data)
{
  while (list)
    {
      (*func) (list->data, user_data);
      list = list->next;
    }
}
382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399


GList*
g_list_insert_sorted (GList    *list,
                      gpointer  data,
                      GCompareFunc  func)
{
  GList *tmp_list = list;
  GList *new_list;
  gint cmp;
  
  if (!list) 
    {
      new_list = g_list_alloc();
      new_list->data = data;
      return new_list;
    }
  
400
  cmp = (*func) (data, tmp_list->data);
401 402 403 404
  
  while ((tmp_list->next) && (cmp > 0))
    {
      tmp_list = tmp_list->next;
405
      cmp = (*func) (data, tmp_list->data);
406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430
    }

  new_list = g_list_alloc();
  new_list->data = data;

  if ((!tmp_list->next) && (cmp > 0))
    {
      tmp_list->next = new_list;
      new_list->prev = tmp_list;
      return list;
    }
   
  if (tmp_list->prev)
    {
      tmp_list->prev->next = new_list;
      new_list->prev = tmp_list->prev;
    }
  new_list->next = tmp_list;
  tmp_list->prev = new_list;
 
  if (tmp_list == list)
    return new_list;
  else
    return list;
}