GList wrapper (GQList) only if you're interested.

[Steven Rostedt <steven rostedt lmco com>]

A week or so ago, I needed to implement a queue,
and toyed with the GList in glib.
I noticed that, as the list grew larger (1000s of elements)
the queue grew slower. This was due to the way GList 
appends items to the list. 
So I wrote a little Queue wrapper to keep track of the
last item and called this GQList.

But playing more, and adding more functionalities, I 
included indexing with another pointer that would try
to keep track of the last location in the list that was
accessed. Then using the three pointers (the first,
last, and this current one) I would try to find the
closest route to traverse the link list to get the
desired location.
This also made for(i=0;data=g_qlist_index(gqlist,i);i++) 
rather efficient.

I also tried to see if I could write a qsort for 
a link list, and succeeded :)
I'm sure it could be made quicker, but it was just
my first attempt.

I'm planning on writing more functions, but I have to 
wait for my wife to give me more time ;)

any who, here it is, take it or leave it.
/* gqlist.c 
 * Steven Rostedt.
 *
 * Since this is a wrapper for glist, and glist is GNU: 
 * I'm showing a GNU statement here!
 *
 * 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
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.	 See the GNU
 * Library General Public License for more details.
 *
 * You should have received a copy of the GNU Library General Public
 * License along with this library; if not, write to the
 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
 * Boston, MA 02111-1307, USA.
 */
#include <stdio.h>
#include "glib.h"
#include "gqlist.h"

static GList *
qlist_get_index (GQList *gqlist, gint indx)
{
  gint f,c,l,count,inc;
  GList *glist;
  enum {QLIST_FIRST, QLIST_CURR, QLIST_LAST} use;

  if (!gqlist || (indx < 0) || (indx >= gqlist->size)) 
    return NULL;

  /*
   * find the closest way to find the index.
   */
  f = indx;
  l = (gqlist->size-1) - indx;
  c = (gqlist->index < 0) ? -1 :
    (gqlist->index > indx) ? gqlist->index - indx:
    indx - gqlist->index;

  use = (c < 0) || (c > l) ? 
    ((l > f) ? QLIST_FIRST : QLIST_LAST) :
    ((c > f) ? QLIST_FIRST : QLIST_CURR);
  
  switch (use) {
  case QLIST_FIRST:
    glist = gqlist->first;
    count = f;
    inc = TRUE;
    break;

  case QLIST_LAST:
    glist = gqlist->last;
    count = l;
    inc = FALSE;
    break;

  case QLIST_CURR:
    glist = gqlist->current;
    count = c;
    inc = (gqlist->index > indx) ? FALSE : TRUE;
    break;

  } /* endswitch */


  while ((glist) && (count > 0)) {
    if (inc) glist = glist->next;
    else glist = glist->prev;
    count--;
  } /* endwhile */

  gqlist->current = glist;
  gqlist->index = indx;

  return glist;
} /* end qlist_get_index */

static void
qlist_sort_me (GList *left, GList *right, 
	       GCompareFunc func)
{
  GList *last,*i;
  gpointer swap;

  if (!left || !right || (left == right)) return;

  last = left;

  for (i=left->next; (i) && (i!=right->next); i=i->next)
    if ((i!=last) && (*func)(i->data,left->data) < 0) {
      last = last->next;
      swap = last->data;
      last->data = i->data;
      i->data = swap;
    } /* end if */

  if (left!=last) {
    swap = left->data;
    left->data = last->data;
    last->data = swap;
  } /* endif */

  if (last!=left)
    qlist_sort_me(left, last->prev,func);
  if (last!=right)
    qlist_sort_me(last->next,right,func);
  
} /* end qlist_sort_me */

GQList *
g_qlist_new(GList* glist)
{
  GQList *gqlist;

  gqlist = g_new(GQList,1);

  if (glist) {
    gqlist->first = glist;
    gqlist->size = 0;
    while(glist) {
      gqlist->last = glist;
      gqlist->size++;
      glist = glist->next;
    } /* endwhile */
  } else {
    gqlist->first = gqlist->last = NULL;
    gqlist->size = 0;
  } /* endif */

  gqlist->current = NULL;
  gqlist->index = -1;

  return gqlist;
} /* end g_qlist_new */

void 
g_qlist_free (GQList *gqlist)
{
  g_list_free(gqlist->first);

  g_free(gqlist);
} /* end g_qlist_free */

GQList *
g_qlist_append (GQList *gqlist, gpointer data)
{
  if (!gqlist) {
    gqlist = g_qlist_new(g_list_append(NULL,data));
    return gqlist;
  } /* endif */

  if (gqlist->last) {
    /* 
     * We have content.
     */
    g_list_append(gqlist->last,data);
    gqlist->last = gqlist->last->next;
  } else {
    gqlist->first = 
      gqlist->last = g_list_append(NULL,data);
  } /* endif */
  gqlist->size++;

  return gqlist;
} /* end g_qlist_append */

GQList *
g_qlist_prepend (GQList *gqlist, gpointer data)
{
  if (!gqlist) {
    gqlist = g_qlist_new(g_list_append(NULL,data));
    return gqlist;
  } /* endif */

  if (gqlist->first) {
    /* 
     * We have content.
     */
    g_list_prepend(gqlist->first,data);
    gqlist->first = gqlist->first->prev;
  } else {
    gqlist->first = 
      gqlist->last = g_list_prepend(NULL,data);
  } /* endif */
  gqlist->size++;

  return gqlist;
} /* end g_qlist_prepend */

GQList *
g_qlist_insert_index (GQList *gqlist, gint indx, gpointer data)
{

  if (!gqlist) {
    /* print some error here! */
    fprintf (stderr,"ouch! GQList NOT INITIALIZED! (g_qlist_insert_index)\n");
    return NULL;
  } /* endif */

  if (indx == 0) {
    /* 
     * same as prepend.
     */
    gqlist = g_qlist_prepend (gqlist,data);
  } else if ((indx == -1) || (indx == (gqlist->size-1))) {
    /*
     * same as append.
     */
    gqlist = g_qlist_append (gqlist,data);
  } else {
    GList *glist;
    /* find the position. */
    glist = qlist_get_index (gqlist,indx);
    if (!glist) {
      /*
       * bad index.
       */
      return NULL;
    } /* endif */
    g_list_prepend(glist,data);
    /* 
     * Don't worry about checking first or last
     * we already did that with the previous logic
     */
  } /* endif */

  gqlist->size++;

  return gqlist;
} /* end g_qlist_insert_index */  

gpointer
g_qlist_remove_first (GQList *gqlist)
{
  gpointer data;
  GList *glist;

  if (!gqlist || !(gqlist->first)) return NULL;

  glist = gqlist->first;
  data = glist->data;
  gqlist->first = glist->next;
  glist->next = glist->prev = NULL;
  g_list_free(glist);

  if (gqlist->first == NULL) 
    gqlist->last = NULL;

  /* reset indexing */
  gqlist->current = NULL;
  gqlist->index = -1;

  gqlist->size--;

  return data;
} /* end g_list_remove_first */

gpointer
g_qlist_remove_last (GQList *gqlist)
{
  gpointer data;
  GList *glist;

  if (!gqlist || !(gqlist->last)) return NULL;

  glist = gqlist->last;
  data = glist->data;
  gqlist->last = glist->prev;
  glist->next = glist->prev = NULL;
  g_list_free(glist);

  if (gqlist->last == NULL) 
    gqlist->first = NULL;

  /* reset indexing */
  gqlist->current = NULL;
  gqlist->index = -1;

  gqlist->size--;

  return data;
} /* end g_list_remove_first */

gpointer
g_list_remove_index (GQList *gqlist, gint indx)
{
  GList *glist;
  gpointer data;

  if (!gqlist || !(gqlist->first)) return NULL;

  if (indx == 0) {
    /*
     * Same as g_qlist_remove_first 
     */
    return g_qlist_remove_first(gqlist);
  }
  if ((indx == -1) || (indx == (gqlist->size-1))) {
    /*
     * Same as g_qlist_remove_last
     */
    return g_qlist_remove_last(gqlist);
  }
  /* 
   * All the rest are within the first and last.
   */
  glist = qlist_get_index(gqlist,indx);

  if (!glist) {
    /* bad index */
    return NULL;
  } /* end */

  data = glist->data;
  glist->prev->next = glist->next;
  glist->next->prev = glist->prev;
  glist->next = glist->prev = NULL;
  g_list_free (glist);

  /* reset indexing */
  gqlist->current = NULL;
  gqlist->index = -1;

  gqlist->size--;

  return data;
} /* end g_qlist_remove_index */

gpointer 
g_qlist_get_first (GQList *gqlist)
{
  if (!(gqlist) || !(gqlist->first)) return NULL;

  return (gqlist->first->data);
} /* end g_qlist_get_first */

gpointer 
g_qlist_get_last (GQList *gqlist)
{
  if (!(gqlist) || !(gqlist->last)) return NULL;

  return (gqlist->last->data);
} /* end g_qlist_get_last */

gpointer 
g_qlist_get_data (GQList *gqlist, gint indx)
{
  GList *glist;
  if (!(gqlist) || !(gqlist->first)) return NULL;

  glist = qlist_get_index(gqlist,indx);

  if (!glist) return NULL;

  return (glist->data);
} /* end g_qlist_get_data */


gint
g_qlist_size (GQList *gqlist)
{ 
  /*
   * I just don't like accessing the objects directly
   * from the structure. 
   * I like C++ type of C programming :)
   */
  if (!gqlist) return 0;
  return gqlist->size;
} /* end g_qlist_size */


void
g_qlist_sort (GQList *gqlist,
	      GCompareFunc func)
{
  qlist_sort_me(gqlist->first, gqlist->last,func);
} /* endif */

/* gqlist.h
 * Steven Rostedt.
 *
 * Since this is a wrapper for glist, and glist is GNU: 
 * I'm showing a GNU statement here!
 *
 * 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
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.	 See the GNU
 * Library General Public License for more details.
 *
 * You should have received a copy of the GNU Library General Public
 * License along with this library; if not, write to the
 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
 * Boston, MA 02111-1307, USA.
 */
#ifndef __G_QLIST_H__
#define __G_QLIST_H__

/*
 * GQList is a wrapper for the GList. I originally 
 *  designed this in a separate project when I needed a queue.
 *  (hence the Q part in GQList :^)
 *  The glist was not efficient when handling a lot of additions
 *  to the end of the list.
 *  All I did was make an abstract object that would keep track
 *  of the last element in the list, so I would be able to 
 *  add to the end efficiently.
 *
 *  But like all things else, it grew!
 * 
 * Now GQList keeps track of the first, last and an arbitrary 
 *  "current" location that changes almost every time
 *   data is retrieved (but not removed).
 *
 * It allows indexing, using the three locations to find
 *  the closest route to get the indexed data.
 *
 * So traversing down the list using an index is still rather
 *  efficient!
 *
 * Out of the blue I decided to write a sort algorithm based on
 *  K&R's qsort algorithm in the ANSI C edition.
 *
 * I plan on writing many more interfaces for this object,
 *  but I appreciate the GNU environment I thought I would
 *  give this simple object over to anyone who likes to play ;)
 *
 *
 * !!!!!!!!! WARNING WARNING WARNING !!!!!!!!!!!
 *
 *  I HAVE NOT FULLY DEBUGGED THE ROUTINES, 
 *  Actually I did very few tests.
 *  So please use at YOUR OWN RISK!!!!
 *
 *  Please report bugs to me :) thank you in advance.
 *
 * S.D. Rostedt.
 *  steven.rostedt@lmco.com
 */

typedef struct _GQList GQList;

struct _GQList {
  GList *first;
  GList *last;
  GList *current;
  gint index;
  gint size;
};

/*
 * There are really four ways of initializing the gqlist object.
 *  gqlist = g_qlist_new(NULL);
 *  gqlist = g_qlist_new(some_g_list);
 *  gqlist = g_qlist_append(NULL,data);
 *  gqlist = g_qlist_prepend(NULL,data);
 */
GQList *
g_qlist_new(GList* glist);

/* 
 * This function simply adds an item to the end of the list.
 */
GQList *
g_qlist_append (GQList *gqlist, gpointer data);

/*
 * this function simply adds an item to the beginning of the list.
 */
GQList *
g_qlist_prepend (GQList *gqlist, gpointer data);

/*
 * This function inserts an item at some index. 
 * Note: index is used consistent with C. Starts with zero.
 * Insert z into location 2 of a list a,b,c returns
 *   a,b,z,c
 */
GQList *
g_qlist_insert_index (GQList *gqlist, gint indx, gpointer data);

/*
 * This function removes the first item from the list
 *  and returns that item (data)
 * NULL if list is empty.
 */
gpointer
g_qlist_remove_first (GQList *gqlist);

/*
 * This function removes the last item from the list
 *  and returns that item (data)
 * NULL if list is empty.
 */
gpointer
g_qlist_remove_last (GQList *gqlist);

/*
 * This function removes a item at a specified location on 
 *  the list. Note: index starts with zero.
 * NULL if bad index or list is empty.
 */
gpointer
g_list_remove_index (GQList *gqlist, gint indx);

/*
 * This function returns the first item on a list.
 * But does not modify the list. (Maybe I should declare
 *   gqlist as const GQList *)
 *  NULL if empty.
 */
gpointer 
g_qlist_get_first (GQList *gqlist);

/*
 * This function returns the last item on a list,
 * But does not modify the list.
 *  NULL if empty.
 */
gpointer 
g_qlist_get_last (GQList *gqlist);

/*
 * This function returns a data item a a specified location.
 *  NULL if bad location. 
 *  Does not modify the list.
 */
gpointer 
g_qlist_get_data (GQList *gqlist, gint indx);

/*
 * This function actually runs qsort on a link list :)
 */
void
g_qlist_sort (GQList *gqlist,
	      GCompareFunc func);


/******************** TBD TBD TBD TBD TBD TBD **********/
/*
 * The following are TBDs, 
 *  I just haven't had the time to write them yet.
 *  But I will (if someone else doesn't beat me to it :)
 */
gpointer
g_qlist_bsearch (GQList *gqlist,
		 GCompareFunc func,
		 gpointer data);

GQList *
g_qlist_insert_sorted (GQList *gqlist,
		    GCompareFunc func,
		    gpointer data);

gint
g_qlist_position(GQList *gqlist, gpointer data);

void
g_qlist_foreach (GQList *gqlist, 
		 GFunc func,
		 gpointer data);

GQList *
g_qlist_concat (GQList *gqlist1, GQList *gqlist2);


#endif