GNOME.org
 

Re: gbsearcharray

On Sat, Aug 25, 2001 at 03:10:58PM +0200, Tim Janik wrote:
> 1) gbsearcharray.[hc] should prolly be moved into glib/glib/

i was surprised to see this because i recently implemented a similar
data structure adapted from g_ptr_array.  (Attached.)

Please forgive any mistakes in convention -- gptrset is a work in progress.
gptrset was written to make an easier GtkListStore.  It emits almost the
exact signals which are wanted by GtkTreeModel.

It seems like there are lots of slightly different ways to implement the
same "array of stuff" data structure.  Please consider gptrset in view of
glib's aims of avoid bloat yet offering the most useful data structures.  ;-)

-- 
Get self-realization at <http://sahajayoga.org> ... <http://why-compete.org> ?
  Victory to the Divine Mother!!

/* 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 Lesser 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
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser 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.
 */

/* originally adapted from g_ptr_array */

#ifndef _G_PTRSET_H_
#define _G_PTRSET_H_

#include <glib-object.h>

typedef struct _GPtrSetClass GPtrSetClass;
typedef struct _GPtrSet  GPtrSet;

#define G_TYPE_PTR_SET		  (g_ptr_set_get_type())
#define G_PTR_SET(obj)		  (G_TYPE_CHECK_INSTANCE_CAST((obj), G_TYPE_PTR_SET, GPtrSet))
#define G_IS_PTR_SET(obj)	  (G_TYPE_CHECK_INSTANCE_TYPE((obj), G_TYPE_PTR_SET))
#define G_PTR_SET_GET_CLASS(obj)  (G_TYPE_INSTANCE_GET_CLASS((obj), G_TYPE_PTR_SET, GPtrSetClass))
#define G_PTR_SET_CLASS(klass)	  (G_TYPE_CHECK_CLASS_CAST((klass), G_TYPE_PTR_SET, GPtrSetClass))
#define G_IS_PTR_SET_CLASS(klass) (G_TYPE_CHECK_CLASS_TYPE((klass), G_TYPE_PTR_SET))

struct _GPtrSet
{
  GObject           parent_instance;
  gpointer *        pdata;
  gint              len;
  gint              alloc;
  gconstpointer     compare_data;
  GCompareDataFunc  ptr_compare;
  GCompareDataFunc  key_compare;
  GDestroyNotify    destroy_func;
  guint             objects : 1;   /* whether to use g_object_{ref|unref} */
};

#define    g_ptr_set_at(set,index)    ((set)->pdata)[(index)]

GType      g_ptr_set_get_type         ();

GPtrSet *  g_ptr_set_new              ();
GPtrSet *  g_ptr_set_new              (GCompareDataFunc  ptr_compare,
				       gconstpointer     compare_data);
void       g_ptr_set_set_key_compare  (GPtrSet *set,
				       GCompareDataFunc  key_compare);
void       g_ptr_set_free             (GPtrSet  *set);

gboolean   g_ptr_set_lookup           (GPtrSet *       set,
				       gint *          ret,
				       gconstpointer   sample);
gboolean   g_ptr_set_lookup_key       (GPtrSet *       set,
				       gint *          ret,
				       gconstpointer   sample_key);

gpointer   g_ptr_set_remove_index     (GPtrSet *  set,
				       gint       index);
gboolean   g_ptr_set_remove           (GPtrSet *  set,
				       gpointer   data);
void       g_ptr_set_add_index        (GPtrSet *  set,
				       gint       index,
				       gpointer   data);
void       g_ptr_set_add              (GPtrSet *  set,
				       gpointer   data);
void       g_ptr_set_reorder          (GPtrSet *  set,
				       gint       index);
#endif

/* 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 Lesser 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
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser 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 <glib.h>
#include <string.h>
#include "gptrset.h"
#include "appmarshal.h"

struct _GPtrSetClass {
  GObjectClass parent_class;

  void (*deleted) (GPtrSet *set, gint index, gpointer data);
  void (*inserted) (GPtrSet *set, gint index);
  void (*reordered) (GPtrSet *set, gint old_order, gint new_order);
};

enum {
  PROP_0,

  PROP_COMPARE_DATA,
  PROP_KEY_COMPARE,
  PROP_PTR_COMPARE,
  PROP_DESTROY_FUNC,
  PROP_OBJECTS
};

enum {
  DELETED,
  INSERTED,
  REORDERED,
  LAST_SIGNAL
};
static guint signals[LAST_SIGNAL] = { 0 };


#define MIN_SET_SIZE  16

static void g_ptr_set_maybe_expand (GPtrSet *set,
				    gint     len);


static gint
g_nearest_pow (gint num)
{
  gint n = 1;

  while (n < num)
    n <<= 1;

  return n;
}

GPtrSet *
g_ptr_set_new (GCompareDataFunc  ptr_compare,
	       gconstpointer     compare_data)
{
  GPtrSet *set;

  set = G_PTR_SET (g_object_new (g_ptr_set_get_type(), 0));

  set->ptr_compare = ptr_compare;
  set->compare_data = compare_data;

  return set;
}

void
g_ptr_set_set_key_compare (GPtrSet *set, GCompareDataFunc key_compare)
{
  set->key_compare = key_compare;
}

static void
g_ptr_set_init (GPtrSet *set)
{
  /* zero fill is good */
}

// g_ptr_set_maybe_shrink XXX

static void
g_ptr_set_maybe_expand (GPtrSet *set,
			gint     len)
{
  if ((set->len + len) > set->alloc)
    {
#ifdef ENABLE_GC_FRIENDLY
      gint old_alloc = set->alloc;
#endif /* ENABLE_GC_FRIENDLY */
      set->alloc = g_nearest_pow (set->len + len);
      set->alloc = MAX (set->alloc, MIN_SET_SIZE);
      set->pdata = g_realloc (set->pdata, sizeof(gpointer) * set->alloc);
#ifdef ENABLE_GC_FRIENDLY
      for ( ; old_alloc < set->alloc; old_alloc++)
	set->pdata [old_alloc] = NULL;
#endif /* ENABLE_GC_FRIENDLY */
    }
}

static gboolean
_ptr_set_lookup (GPtrSet *         fset,
		 gint *            ret,
		 GCompareDataFunc  compare,
		 gconstpointer     sample)
{
  gint first, last;
  gint mid;
  gint midsize;
  gint cmp;
  gint tx;

  g_return_val_if_fail (compare, FALSE);
  g_return_val_if_fail (sample, FALSE);

  if (!fset->len)
    {
      if (ret) *ret = 0;
      return FALSE;
    }

  first = 0;
  last = fset->len - 1;

  midsize = last - first;
  
  while (midsize > 1) {
    mid = first + midsize / 2;
    
    cmp = (*compare) (sample, g_ptr_set_at (fset, mid), (gpointer) fset->compare_data);
    
    if (cmp == 0)
      {
	if (ret) *ret = mid;
	return TRUE;
      }
    
    if (cmp < 0)
      last = mid-1;
    else
      first = mid+1;
    
    midsize = last - first;
  }

  for (tx = first; tx <= last; tx++)
    {
      cmp = (*compare) (sample, g_ptr_set_at (fset, tx), (gpointer) fset->compare_data);

      if (cmp < 0)
	{
	  if (ret) *ret = tx;
	  return FALSE;
	}
      if (cmp == 0)
	{
	  if (ret) *ret = tx;
	  return TRUE;
	}
    }

  if (ret) *ret = last+1;
  return FALSE;
}

gboolean
g_ptr_set_lookup (GPtrSet *       fset,
		  gint *          ret,
		  gconstpointer   sample)
{
  g_return_val_if_fail (fset, FALSE);

  return _ptr_set_lookup (fset, ret, fset->ptr_compare, sample);
}

gboolean
g_ptr_set_lookup_key (GPtrSet *      set,
		      gint *         ret,
		      gconstpointer  sample_key)
{
  g_return_val_if_fail (set, FALSE);

  return _ptr_set_lookup (set, ret, set->key_compare, sample_key);
}

static inline void
g_ptr_set_verify_sort (GPtrSet *  set)
{
  gint xx;

  if (set->len <= 1)
    return;

  for (xx=0; xx < set->len - 1; xx++)
    {
      if (set->ptr_compare (g_ptr_set_at (set, xx),
			    g_ptr_set_at (set, xx + 1),
			    (gpointer) set->compare_data) > 0)
	g_critical ("%d, %d are unsorted", xx, xx+1);
    }
}

void
g_ptr_set_reorder (GPtrSet *  set,
		   gint       index)
{
  gpointer data;
  gint mx;

  g_return_if_fail (set);
  g_return_if_fail (0 <= index && index < set->len);

  data = g_ptr_set_at (set, index);

  if (index != set->len - 1)
    g_memmove (set->pdata + index, set->pdata + index + 1, 
	       sizeof (gpointer) * (set->len - index - 1));
  -- set->len;

  g_ptr_set_lookup (set, &mx, data);

  g_memmove (&g_ptr_set_at (set, 1 + mx), 
	     &g_ptr_set_at (set, mx), 
	     sizeof(gpointer) * (set->len - mx));

  g_ptr_set_at (set, mx) = data;

  ++ set->len;

  if (mx == index)
    return;

  g_ptr_set_verify_sort (set);
  g_signal_emit (set, signals[REORDERED], 0, index, mx);
}

gpointer
g_ptr_set_remove_index (GPtrSet* fset,
			gint    index)
{
  gpointer result;

  g_return_val_if_fail (fset, NULL);
  g_return_val_if_fail (0 <= index && index < fset->len, NULL);

  result = fset->pdata[index];
  
  if (index != fset->len - 1)
    g_memmove (fset->pdata + index, fset->pdata + index + 1, 
	       sizeof (gpointer) * (fset->len - index - 1));
  
  fset->len -= 1;

#ifdef ENABLE_GC_FRIENDLY  
  fset->pdata[fset->len] = NULL;
#endif /* ENABLE_GC_FRIENDLY */  

  g_ptr_set_verify_sort (fset);
  g_signal_emit (fset, signals[DELETED], 0, index, result);

  if (fset->destroy_func)
    (*fset->destroy_func) (result);
  if (fset->objects)
    g_object_unref (result);

  return result;
}

gboolean
g_ptr_set_remove (GPtrSet* fset,
		  gpointer data)
{
  gint at;

  g_return_val_if_fail (fset, FALSE);
  g_return_val_if_fail (data, FALSE);

  /* only remove first match */
  if (g_ptr_set_lookup (fset, &at, data))
    {
      g_ptr_set_remove_index (fset, at);
      return TRUE;
    }

  return FALSE;
}

void
g_ptr_set_add_index (GPtrSet *   set,
		     gint        index,
		     gpointer    data)
{
  g_return_if_fail (set);
  g_return_if_fail (0 <= index && index <= set->len);

  if (set->objects)
    g_object_ref (data);

  g_ptr_set_maybe_expand ((GPtrSet*) set, 1);

  g_memmove (&g_ptr_set_at (set, 1 + index), 
	     &g_ptr_set_at (set, index), 
	     sizeof(gpointer) * (set->len - index));

  g_ptr_set_at (set, index) = data;

  set->len += 1;

  g_ptr_set_verify_sort (set);
  g_signal_emit (set, signals[INSERTED], 0, index);
}


void
g_ptr_set_add (GPtrSet *   set,
	       gpointer    data)
{
  gint at;

  g_return_if_fail (set);
  g_return_if_fail (data);

  if (g_ptr_set_lookup (set, &at, data))
    ++at;  // reduce memmove

  g_ptr_set_add_index (set, at, data);
}

static void
g_ptr_set_set_property (GObject      *object,
			guint         prop_id,
			const GValue *value,
			GParamSpec   *pspec)
{
  GPtrSet *set = G_PTR_SET (object);

  g_return_if_fail (set->len == 0);

  switch (prop_id) {
  case PROP_COMPARE_DATA:
    set->compare_data = g_value_get_pointer (value);
    break;

  case PROP_KEY_COMPARE:
    set->key_compare = g_value_get_pointer (value);
    break;

  case PROP_PTR_COMPARE:
    set->ptr_compare = g_value_get_pointer (value);
    break;

  case PROP_DESTROY_FUNC:
    set->destroy_func = g_value_get_pointer (value);
    break;

  case PROP_OBJECTS:
    set->objects = g_value_get_boolean (value);
    break;

  default:
    G_OBJECT_WARN_INVALID_PROPERTY_ID (object, prop_id, pspec);
    break;
  }
}

static void
g_ptr_set_get_property (GObject      *object,
			guint         prop_id,
			GValue       *value,
			GParamSpec   *pspec)
{
  GPtrSet *set = G_PTR_SET (object);

  switch (prop_id) {
  case PROP_COMPARE_DATA:
    g_value_set_pointer (value, (gpointer) set->compare_data);
    break;

  case PROP_KEY_COMPARE:
    g_value_set_pointer (value, set->key_compare);
    break;

  case PROP_PTR_COMPARE:
    g_value_set_pointer (value, set->ptr_compare);
    break;

  case PROP_DESTROY_FUNC:
    g_value_set_pointer (value, set->destroy_func);
    break;

  case PROP_OBJECTS:
    g_value_set_boolean (value, set->objects);
    break;

  default:
    G_OBJECT_WARN_INVALID_PROPERTY_ID (object, prop_id, pspec);
    break;
  }
}

static GObjectClass *parent_class;

static void
g_ptr_set_finalize (GObject *object)
{
  GPtrSet *set;
  gint xx;

  g_return_if_fail (G_IS_PTR_SET (object));

  set = G_PTR_SET (object);

  if (set->destroy_func)
    for (xx=0; xx < set->len; xx++)
      (* set->destroy_func) (g_ptr_set_at (set, xx));

  if (set->objects)
    for (xx=0; xx < set->len; xx++)
      g_object_unref (g_ptr_set_at (set, xx));

  g_free (set->pdata);
  set->pdata = NULL;

  (* G_OBJECT_CLASS(parent_class)->finalize) (object);
}

static void
g_ptr_set_class_init(GPtrSetClass *klass) {
  GObjectClass *object_class = G_OBJECT_CLASS(klass);

  parent_class = g_type_class_peek_parent (klass);

  object_class->set_property = g_ptr_set_set_property;
  object_class->get_property = g_ptr_set_get_property;

  object_class->finalize = g_ptr_set_finalize;

  g_object_class_install_property
    (object_class, PROP_COMPARE_DATA,
     g_param_spec_pointer ("compare_Data",
			   "",
			   "",
			   G_PARAM_READABLE|G_PARAM_WRITABLE));

  g_object_class_install_property
    (object_class, PROP_KEY_COMPARE,
     g_param_spec_pointer ("key_compare",
			   "",
			   "GCompareDataFunc",
			   G_PARAM_READABLE|G_PARAM_WRITABLE));

  g_object_class_install_property
    (object_class, PROP_PTR_COMPARE,
     g_param_spec_pointer ("ptr_compare",
			   "",
			   "GCompareDataFunc",
			   G_PARAM_READABLE|G_PARAM_WRITABLE));

  g_object_class_install_property
    (object_class, PROP_DESTROY_FUNC,
     g_param_spec_pointer ("destroy_func",
			   "",
			   "GDestroyNotify",
			   G_PARAM_READABLE|G_PARAM_WRITABLE));

  g_object_class_install_property
    (object_class, PROP_OBJECTS,
     g_param_spec_boolean ("objects",
			   "",
			   "Whether to do reference count the elements.",
			   FALSE,
			   G_PARAM_READABLE|G_PARAM_WRITABLE));

  signals[DELETED] =
    g_signal_new ("deleted",
		  G_OBJECT_CLASS_TYPE (object_class),
		  0,
		  0,
		  NULL, NULL,
		  app_marshal_VOID__UINT_POINTER,
		  G_TYPE_NONE,
		  2,
		  G_TYPE_UINT,
		  G_TYPE_POINTER);
  signals[INSERTED] =
    g_signal_new ("inserted",
		  G_OBJECT_CLASS_TYPE (object_class),
		  0,
		  0,
		  NULL, NULL,
		  app_marshal_VOID__UINT,
		  G_TYPE_NONE,
		  1,
		  G_TYPE_UINT);
  signals[REORDERED] =
    g_signal_new ("reordered",
		  G_OBJECT_CLASS_TYPE (object_class),
		  0,
		  0,
		  NULL, NULL,
		  app_marshal_VOID__UINT_UINT,
		  G_TYPE_NONE,
		  2,
		  G_TYPE_UINT,
		  G_TYPE_UINT);
}

GType
g_ptr_set_get_type() {
  static GType our_type = 0;

  if (our_type == 0) {
    static const GTypeInfo our_info = {
      sizeof(GPtrSetClass),
      (GBaseInitFunc) NULL,
      (GBaseFinalizeFunc) NULL,
      (GClassInitFunc) g_ptr_set_class_init,
      NULL,           /* class_finalize */
      NULL,           /* class_data */
      sizeof (GPtrSet),
      0,              /* n_preallocs */
      (GInstanceInitFunc) g_ptr_set_init
    };

    our_type = g_type_register_static (G_TYPE_OBJECT,
				       "GPtrSet",
				       &our_info,
				       0);
  }
  return our_type;
}
[Date Prev][Date Next]   [Thread Prev][Thread Next]   [Thread Index] [Date Index] [Author Index]