Main Page | Class List | Directories | File List | Class Members | File Members

glist.c File Reference

#include "glib.h"

Go to the source code of this file.

Classes

struct  _GAllocator

Functions

 G_LOCK_DEFINE_STATIC (current_allocator)
static void g_list_validate_allocator (GAllocator *allocator)
void g_list_push_allocator (GAllocator *allocator)
void g_list_pop_allocator (void)
GList * g_list_alloc (void)
void g_list_free (GList *list)
void g_list_free_1 (GList *list)
GList * g_list_append (GList *list, gpointer data)
GList * g_list_prepend (GList *list, gpointer data)
GList * g_list_insert (GList *list, gpointer data, gint position)
GList * g_list_concat (GList *list1, GList *list2)
GList * g_list_remove (GList *list, gpointer data)
GList * g_list_remove_link (GList *list, GList *link)
GList * g_list_copy (GList *list)
GList * g_list_reverse (GList *list)
GList * g_list_nth (GList *list, guint n)
gpointer g_list_nth_data (GList *list, guint n)
GList * g_list_find (GList *list, gpointer data)
GList * g_list_find_custom (GList *list, gpointer data, GCompareFunc func)
gint g_list_position (GList *list, GList *link)
gint g_list_index (GList *list, gpointer data)
GList * g_list_last (GList *list)
GList * g_list_first (GList *list)
guint g_list_length (GList *list)
void g_list_foreach (GList *list, GFunc func, gpointer user_data)
GList * g_list_insert_sorted (GList *list, gpointer data, GCompareFunc func)
static GList * g_list_sort_merge (GList *l1, GList *l2, GCompareFunc compare_func)
GList * g_list_sort (GList *list, GCompareFunc compare_func)
GList * g_list_sort2 (GList *list, GCompareFunc compare_func)

Variables

static GAllocator * current_allocator = NULL

Function Documentation

GList* g_list_alloc (  void   ) 
 

Definition at line 104 of file glist.c.

References _GList::data, _GAllocator::free_lists, g_allocator_new(), g_chunk_new, g_list_validate_allocator(), G_LOCK, G_UNLOCK, _GAllocator::last, _GAllocator::mem_chunk, _GList::next, NULL, and _GList::prev.

Referenced by g_list_append(), g_list_copy(), g_list_insert(), g_list_insert_sorted(), and g_list_prepend().

00105 {
00106   GList *list;
00107 
00108   G_LOCK (current_allocator);
00109   if (!current_allocator)
00110     {
00111       GAllocator *allocator = g_allocator_new ("GLib default GList allocator",
00112                                                128);
00113       g_list_validate_allocator (allocator);
00114       allocator->last = NULL;
00115       current_allocator = allocator;
00116     }
00117   if (!current_allocator->free_lists)
00118     {
00119       list = g_chunk_new (GList, current_allocator->mem_chunk);
00120       list->data = NULL;
00121     }
00122   else
00123     {
00124       if (current_allocator->free_lists->data)
00125         {
00126           list = current_allocator->free_lists->data;
00127           current_allocator->free_lists->data = list->next;
00128           list->data = NULL;
00129         }
00130       else
00131         {
00132           list = current_allocator->free_lists;
00133           current_allocator->free_lists = list->next;
00134         }
00135     }
00136   G_UNLOCK (current_allocator);
00137   list->next = NULL;
00138   list->prev = NULL;
00139   
00140   return list;
00141 }

GList* g_list_append (  GList *  list,
gpointer  data
) 
 

Definition at line 170 of file glist.c.

References _GList::data, g_list_alloc(), g_list_last(), _GList::next, and _GList::prev.

Referenced by g_list_insert(), and main().

00172 {
00173   GList *new_list;
00174   GList *last;
00175   
00176   new_list = g_list_alloc ();
00177   new_list->data = data;
00178   
00179   if (list)
00180     {
00181       last = g_list_last (list);
00182       /* g_assert (last != NULL); */
00183       last->next = new_list;
00184       new_list->prev = last;
00185 
00186       return list;
00187     }
00188   else
00189     return new_list;
00190 }

GList* g_list_concat (  GList *  list1,
GList *  list2
) 
 

Definition at line 250 of file glist.c.

References g_list_last(), _GList::next, and _GList::prev.

00251 {
00252   GList *tmp_list;
00253   
00254   if (list2)
00255     {
00256       tmp_list = g_list_last (list1);
00257       if (tmp_list)
00258         tmp_list->next = list2;
00259       else
00260         list1 = list2;
00261       list2->prev = tmp_list;
00262     }
00263   
00264   return list1;
00265 }

GList* g_list_copy (  GList *  list  ) 
 

Definition at line 318 of file glist.c.

References _GList::data, g_list_alloc(), _GList::next, NULL, and _GList::prev.

00319 {
00320   GList *new_list = NULL;
00321 
00322   if (list)
00323     {
00324       GList *last;
00325 
00326       new_list = g_list_alloc ();
00327       new_list->data = list->data;
00328       last = new_list;
00329       list = list->next;
00330       while (list)
00331         {
00332           last->next = g_list_alloc ();
00333           last->next->prev = last;
00334           last = last->next;
00335           last->data = list->data;
00336           list = list->next;
00337         }
00338     }
00339 
00340   return new_list;
00341 }

GList* g_list_find (  GList *  list,
gpointer  data
) 
 

Definition at line 381 of file glist.c.

References _GList::data, and _GList::next.

00383 {
00384   while (list)
00385     {
00386       if (list->data == data)
00387         break;
00388       list = list->next;
00389     }
00390   
00391   return list;
00392 }

GList* g_list_find_custom (  GList *  list,
gpointer  data,
GCompareFunc  func
) 
 

Definition at line 395 of file glist.c.

References _GList::data, g_return_val_if_fail, _GList::next, and NULL.

00398 {
00399   g_return_val_if_fail (func != NULL, list);
00400 
00401   while (list)
00402     {
00403       if (! func (list->data, data))
00404         return list;
00405       list = list->next;
00406     }
00407 
00408   return NULL;
00409 }

GList* g_list_first (  GList *  list  ) 
 

Definition at line 461 of file glist.c.

References _GList::prev.

00462 {
00463   if (list)
00464     {
00465       while (list->prev)
00466         list = list->prev;
00467     }
00468   
00469   return list;
00470 }

void g_list_foreach (  GList *  list,
GFunc  func,
gpointer  user_data
) 
 

Definition at line 488 of file glist.c.

References _GList::data, and _GList::next.

00491 {
00492   while (list)
00493     {
00494       (*func) (list->data, user_data);
00495       list = list->next;
00496     }
00497 }

void g_list_free (  GList *  list  ) 
 

Definition at line 144 of file glist.c.

References _GList::data, _GAllocator::free_lists, G_LOCK, G_UNLOCK, and _GList::next.

Referenced by g_completion_add_items(), g_completion_clear_items(), g_completion_complete(), and main().

00145 {
00146   if (list)
00147     {
00148       list->data = list->next;  
00149       G_LOCK (current_allocator);
00150       list->next = current_allocator->free_lists;
00151       current_allocator->free_lists = list;
00152       G_UNLOCK (current_allocator);
00153     }
00154 }

void g_list_free_1 (  GList *  list  ) 
 

Definition at line 157 of file glist.c.

References _GList::data, _GAllocator::free_lists, G_LOCK, G_UNLOCK, _GList::next, and NULL.

Referenced by g_list_remove().

00158 {
00159   if (list)
00160     {
00161       list->data = NULL;  
00162       G_LOCK (current_allocator);
00163       list->next = current_allocator->free_lists;
00164       current_allocator->free_lists = list;
00165       G_UNLOCK (current_allocator);
00166     }
00167 }

gint g_list_index (  GList *  list,
gpointer  data
) 
 

Definition at line 431 of file glist.c.

References _GList::data, and _GList::next.

00433 {
00434   gint i;
00435 
00436   i = 0;
00437   while (list)
00438     {
00439       if (list->data == data)
00440         return i;
00441       i++;
00442       list = list->next;
00443     }
00444 
00445   return -1;
00446 }

GList* g_list_insert (  GList *  list,
gpointer  data,
gint  position
) 
 

Definition at line 216 of file glist.c.

References _GList::data, g_list_alloc(), g_list_append(), g_list_nth(), g_list_prepend(), _GList::next, and _GList::prev.

00219 {
00220   GList *new_list;
00221   GList *tmp_list;
00222   
00223   if (position < 0)
00224     return g_list_append (list, data);
00225   else if (position == 0)
00226     return g_list_prepend (list, data);
00227   
00228   tmp_list = g_list_nth (list, position);
00229   if (!tmp_list)
00230     return g_list_append (list, data);
00231   
00232   new_list = g_list_alloc ();
00233   new_list->data = data;
00234   
00235   if (tmp_list->prev)
00236     {
00237       tmp_list->prev->next = new_list;
00238       new_list->prev = tmp_list->prev;
00239     }
00240   new_list->next = tmp_list;
00241   tmp_list->prev = new_list;
00242   
00243   if (tmp_list == list)
00244     return new_list;
00245   else
00246     return list;
00247 }

GList* g_list_insert_sorted (  GList *  list,
gpointer  data,
GCompareFunc  func
) 
 

Definition at line 501 of file glist.c.

References _GList::data, g_list_alloc(), g_return_val_if_fail, _GList::next, NULL, and _GList::prev.

Referenced by main().

00504 {
00505   GList *tmp_list = list;
00506   GList *new_list;
00507   gint cmp;
00508 
00509   g_return_val_if_fail (func != NULL, list);
00510   
00511   if (!list) 
00512     {
00513       new_list = g_list_alloc();
00514       new_list->data = data;
00515       return new_list;
00516     }
00517   
00518   cmp = (*func) (data, tmp_list->data);
00519   
00520   while ((tmp_list->next) && (cmp > 0))
00521     {
00522       tmp_list = tmp_list->next;
00523       cmp = (*func) (data, tmp_list->data);
00524     }
00525 
00526   new_list = g_list_alloc();
00527   new_list->data = data;
00528 
00529   if ((!tmp_list->next) && (cmp > 0))
00530     {
00531       tmp_list->next = new_list;
00532       new_list->prev = tmp_list;
00533       return list;
00534     }
00535    
00536   if (tmp_list->prev)
00537     {
00538       tmp_list->prev->next = new_list;
00539       new_list->prev = tmp_list->prev;
00540     }
00541   new_list->next = tmp_list;
00542   tmp_list->prev = new_list;
00543  
00544   if (tmp_list == list)
00545     return new_list;
00546   else
00547     return list;
00548 }

GList* g_list_last (  GList *  list  ) 
 

Definition at line 449 of file glist.c.

References _GList::next.

Referenced by g_list_append(), and g_list_concat().

00450 {
00451   if (list)
00452     {
00453       while (list->next)
00454         list = list->next;
00455     }
00456   
00457   return list;
00458 }

guint g_list_length (  GList *  list  ) 
 

Definition at line 473 of file glist.c.

References _GList::next.

00474 {
00475   guint length;
00476   
00477   length = 0;
00478   while (list)
00479     {
00480       length++;
00481       list = list->next;
00482     }
00483   
00484   return length;
00485 }

GList* g_list_nth (  GList *  list,
guint  n
) 
 

Definition at line 361 of file glist.c.

References _GList::next.

Referenced by g_list_insert(), and main().

00363 {
00364   while ((n-- > 0) && list)
00365     list = list->next;
00366   
00367   return list;
00368 }

gpointer g_list_nth_data (  GList *  list,
guint  n
) 
 

Definition at line 371 of file glist.c.

References _GList::data, _GList::next, and NULL.

00373 {
00374   while ((n-- > 0) && list)
00375     list = list->next;
00376   
00377   return list ? list->data : NULL;
00378 }

void g_list_pop_allocator (  void   ) 
 

Definition at line 88 of file glist.c.

References G_LOCK, G_UNLOCK, _GAllocator::is_unused, _GAllocator::last, NULL, and TRUE.

00089 {
00090   G_LOCK (current_allocator);
00091   if (current_allocator)
00092     {
00093       GAllocator *allocator;
00094 
00095       allocator = current_allocator;
00096       current_allocator = allocator->last;
00097       allocator->last = NULL;
00098       allocator->is_unused = TRUE;
00099     }
00100   G_UNLOCK (current_allocator);
00101 }

gint g_list_position (  GList *  list,
GList *  link
) 
 

Definition at line 413 of file glist.c.

References _GList::next.

Referenced by main().

00415 {
00416   gint i;
00417 
00418   i = 0;
00419   while (list)
00420     {
00421       if (list == link)
00422         return i;
00423       i++;
00424       list = list->next;
00425     }
00426 
00427   return -1;
00428 }

GList* g_list_prepend (  GList *  list,
gpointer  data
) 
 

Definition at line 193 of file glist.c.

References _GList::data, g_list_alloc(), _GList::next, and _GList::prev.

Referenced by g_completion_add_items(), g_completion_complete(), g_list_insert(), and main().

00195 {
00196   GList *new_list;
00197   
00198   new_list = g_list_alloc ();
00199   new_list->data = data;
00200   
00201   if (list)
00202     {
00203       if (list->prev)
00204         {
00205           list->prev->next = new_list;
00206           new_list->prev = list->prev;
00207         }
00208       list->prev = new_list;
00209       new_list->next = list;
00210     }
00211   
00212   return new_list;
00213 }

void g_list_push_allocator (  GAllocator *  allocator  ) 
 

Definition at line 78 of file glist.c.

References g_list_validate_allocator(), G_LOCK, G_UNLOCK, and _GAllocator::last.

00079 {
00080   G_LOCK (current_allocator);
00081   g_list_validate_allocator ( allocator );
00082   allocator->last = current_allocator;
00083   current_allocator = allocator;
00084   G_UNLOCK (current_allocator);
00085 }

GList* g_list_remove (  GList *  list,
gpointer  data
) 
 

Definition at line 268 of file glist.c.

References _GList::data, g_list_free_1(), _GList::next, and _GList::prev.

Referenced by g_completion_remove_items().

00270 {
00271   GList *tmp;
00272   
00273   tmp = list;
00274   while (tmp)
00275     {
00276       if (tmp->data != data)
00277         tmp = tmp->next;
00278       else
00279         {
00280           if (tmp->prev)
00281             tmp->prev->next = tmp->next;
00282           if (tmp->next)
00283             tmp->next->prev = tmp->prev;
00284           
00285           if (list == tmp)
00286             list = list->next;
00287           
00288           g_list_free_1 (tmp);
00289           
00290           break;
00291         }
00292     }
00293   return list;
00294 }

GList* g_list_remove_link (  GList *  list,
GList *  link
) 
 

Definition at line 297 of file glist.c.

References _GList::next, NULL, and _GList::prev.

Referenced by g_completion_complete().

00299 {
00300   if (link)
00301     {
00302       if (link->prev)
00303         link->prev->next = link->next;
00304       if (link->next)
00305         link->next->prev = link->prev;
00306       
00307       if (link == list)
00308         list = list->next;
00309       
00310       link->next = NULL;
00311       link->prev = NULL;
00312     }
00313   
00314   return list;
00315 }

GList* g_list_reverse (  GList *  list  ) 
 

Definition at line 344 of file glist.c.

References _GList::next, NULL, and _GList::prev.

Referenced by main().

00345 {
00346   GList *last;
00347   
00348   last = NULL;
00349   while (list)
00350     {
00351       last = list;
00352       list = last->next;
00353       last->next = last->prev;
00354       last->prev = list;
00355     }
00356   
00357   return last;
00358 }

GList* g_list_sort (  GList *  list,
GCompareFunc  compare_func
) 
 

Definition at line 586 of file glist.c.

References g_list_sort(), g_list_sort_merge(), _GList::next, and NULL.

Referenced by g_list_sort(), and main().

00588 {
00589   GList *l1, *l2;
00590   
00591   if (!list) 
00592     return NULL;
00593   if (!list->next) 
00594     return list;
00595   
00596   l1 = list; 
00597   l2 = list->next;
00598 
00599   while ((l2 = l2->next) != NULL)
00600     {
00601       if ((l2 = l2->next) == NULL) 
00602         break;
00603       l1 = l1->next;
00604     }
00605   l2 = l1->next; 
00606   l1->next = NULL; 
00607 
00608   return g_list_sort_merge (g_list_sort (list, compare_func),
00609                             g_list_sort (l2,   compare_func),
00610                             compare_func);
00611 }

GList* g_list_sort2 (  GList *  list,
GCompareFunc  compare_func
) 
 

Definition at line 614 of file glist.c.

References _GSList::data, _GList::data, g_list_sort_merge(), g_slist_append(), g_slist_free(), _GSList::next, _GList::next, and NULL.

00616 {
00617   GSList *runs = NULL;
00618   GList *tmp;
00619 
00620   /* Degenerate case.  */
00621   if (!list) return NULL;
00622 
00623   /* Assume: list = [12,2,4,11,2,4,6,1,1,12].  */
00624   for (tmp = list; tmp; )
00625     {
00626       GList *tmp2;
00627       for (tmp2 = tmp;
00628            tmp2->next && compare_func (tmp2->data, tmp2->next->data) <= 0;
00629            tmp2 = tmp2->next)
00630         /* Nothing */;
00631       runs = g_slist_append (runs, tmp);
00632       tmp = tmp2->next;
00633       tmp2->next = NULL;
00634     }
00635   /* Now: runs = [[12],[2,4,11],[2,4,6],[1,1,12]].  */
00636   
00637   while (runs->next)
00638     {
00639       /* We have more than one run.  Merge pairwise.  */
00640       GSList *dst, *src, *dstprev = NULL;
00641       dst = src = runs;
00642       while (src && src->next)
00643         {
00644           dst->data = g_list_sort_merge (src->data,
00645                                          src->next->data,
00646                                          compare_func);
00647           dstprev = dst;
00648           dst = dst->next;
00649           src = src->next->next;
00650         }
00651 
00652       /* If number of runs was odd, just keep the last.  */
00653       if (src)
00654         {
00655           dst->data = src->data;
00656           dstprev = dst;
00657           dst = dst->next;
00658         }
00659 
00660       dstprev->next = NULL;
00661       g_slist_free (dst);
00662     }
00663 
00664   /* After 1st loop: runs = [[2,4,11,12],[1,1,2,4,6,12]].  */
00665   /* After 2nd loop: runs = [[1,1,2,2,4,4,6,11,12,12]].  */
00666 
00667   list = runs->data;
00668   g_slist_free (runs);
00669   return list;
00670 }

static GList* g_list_sort_merge (  GList *  l1,
GList *  l2,
GCompareFunc  compare_func
)  [static]
 

Definition at line 551 of file glist.c.

References _GList::data, _GList::next, NULL, and _GList::prev.

Referenced by g_list_sort(), and g_list_sort2().

00554 {
00555   GList list, *l, *lprev;
00556 
00557   l = &list; 
00558   lprev = NULL;
00559 
00560   while (l1 && l2)
00561     {
00562       if (compare_func (l1->data, l2->data) < 0)
00563         {
00564           l->next = l1;
00565           l = l->next;
00566           l->prev = lprev; 
00567           lprev = l;
00568           l1 = l1->next;
00569         } 
00570       else 
00571         {
00572           l->next = l2;
00573           l = l->next;
00574           l->prev = lprev; 
00575           lprev = l;
00576           l2 = l2->next;
00577         }
00578     }
00579   l->next = l1 ? l1 : l2;
00580   l->next->prev = l;
00581 
00582   return list.next;
00583 }

static void g_list_validate_allocator (  GAllocator *  allocator  )  [static]
 

Definition at line 50 of file glist.c.

References FALSE, _GAllocator::free_lists, G_ALLOC_ONLY, G_ALLOCATOR_LIST, g_mem_chunk_destroy(), g_mem_chunk_new(), g_return_if_fail, _GAllocator::is_unused, _GAllocator::mem_chunk, _GAllocator::n_preallocs, _GAllocator::name, NULL, TRUE, and _GAllocator::type.

Referenced by g_list_alloc(), and g_list_push_allocator().

00051 {
00052   g_return_if_fail (allocator != NULL);
00053   g_return_if_fail (allocator->is_unused == TRUE);
00054 
00055   if (allocator->type != G_ALLOCATOR_LIST)
00056     {
00057       allocator->type = G_ALLOCATOR_LIST;
00058       if (allocator->mem_chunk)
00059         {
00060           g_mem_chunk_destroy (allocator->mem_chunk);
00061           allocator->mem_chunk = NULL;
00062         }
00063     }
00064 
00065   if (!allocator->mem_chunk)
00066     {
00067       allocator->mem_chunk = g_mem_chunk_new (allocator->name,
00068                                               sizeof (GList),
00069                                               sizeof (GList) * allocator->n_preallocs,
00070                                               G_ALLOC_ONLY);
00071       allocator->free_lists = NULL;
00072     }
00073 
00074   allocator->is_unused = FALSE;
00075 }

G_LOCK_DEFINE_STATIC (  current_allocator   ) 
 

Variable Documentation

GAllocator* current_allocator = NULL [static]
 

Definition at line 45 of file glist.c.

© sourcejam.com 2005-2008