g_ptr_array bsearch & etc [RESEND]

[Joshua N Pritikin <vishnu pobox com>]

Can the following be added to g_ptr_array?

gboolean
g_ptr_array_bsearch (GPtrArray *     array,
		     guint *         ret,
		     gconstpointer   sample,
		     GCompareFunc    compare_func);
void
g_ptr_array_add_index (GPtrArray * array,
		       guint       index,
		       gpointer    data);
void
g_ptr_array_add_sorted (GPtrArray *   array,
			gpointer      data,
			GCompareFunc  compare_func);

Implementation and test suite are attached.

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

#include <glib.h>
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>

gint strcmp_count=0;

// ---------------------------- copied from garray.c

typedef struct _GRealPtrArray  GRealPtrArray;

struct _GRealPtrArray
{
  gpointer *pdata;
  guint     len;
  guint     alloc;
};

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

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

  return n;
}

static void
g_ptr_array_maybe_expand (GRealPtrArray *array,
			  gint        len)
{
  if ((array->len + len) > array->alloc)
    {
#ifdef ENABLE_GC_FRIENDLY
      guint old_alloc = array->alloc;
#endif /* ENABLE_GC_FRIENDLY */
      array->alloc = g_nearest_pow (array->len + len);
      array->alloc = MAX (array->alloc, 16);
      array->pdata = g_realloc (array->pdata, sizeof(gpointer) * array->alloc);
#ifdef ENABLE_GC_FRIENDLY
      for ( ; old_alloc < array->alloc; old_alloc++)
	array->pdata [old_alloc] = NULL;
#endif /* ENABLE_GC_FRIENDLY */
    }
}

// ----------------------------

gboolean
g_ptr_array_bsearch (GPtrArray *     array,
		     guint *         ret,
		     gconstpointer   sample,
		     GCompareFunc    compare_func)
{
  guint first, last;
  guint mid;
  guint midsize;
  gint cmp;
  guint tx;

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

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

  midsize = last - first;
  
  while (midsize > 1) {
    mid = first + midsize / 2;
    
    cmp = compare_func (sample, g_ptr_array_index (array, mid));
    
    if (cmp == 0)
      {
	*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_func (sample, g_ptr_array_index (array, tx));
      if (cmp < 0)
	{
	  *ret = tx;
	  return FALSE;
	}
      if (cmp == 0)
	{
	  *ret = tx;
	  return TRUE;
	}
    }

  *ret = last+1;
  return FALSE;
}

void
g_ptr_array_add_index (GPtrArray * array,
		       guint       index,
		       gpointer    data)
{
  g_return_if_fail (array);

  g_ptr_array_maybe_expand (array, 1);

  g_memmove (&g_ptr_array_index (array, 1 + index), 
	     &g_ptr_array_index (array, index), 
	     sizeof(gpointer) * (array->len - index));

  g_ptr_array_index (array, index) = data;

  array->len += 1;
}

void
g_ptr_array_add_sorted (GPtrArray *   array,
			gpointer      data,
			GCompareFunc  compare_func)
{
  guint at;

  if (g_ptr_array_bsearch (array, &at, data, compare_func))
    ++at;  // reduce memmove

  g_ptr_array_add_index (array, at, data);
}

// -----------------------------------------

gint count_strcmp (gchar *s1, gchar *s2)
{
  ++strcmp_count;
  return strcmp(s1, s2);
}

gint indirect_strcmp (gchar **s1, gchar **s2)
{ return strcmp(*s1, *s2); }

gint simple_strcmp (gchar *s1, gchar *s2)
{ return strcmp(s1, s2); }

int
main(int argc, char *argv[])
{
  FILE *file;
  GPtrArray *dict;
  GPtrArray *disorder;
  GPtrArray *subset;
  int xx;
  const gint bufsize = 100;
  gchar buf[bufsize];
  GRand *rand;
  gint bsearch_count = 0;

  int word_count = argv[1]? atoi (argv[1]) : 50;

  rand = g_rand_new_with_seed (0);

  file = fopen("/usr/share/dict/words", "r");
  g_assert (file);

  dict = g_ptr_array_new ();
  disorder = g_ptr_array_new ();
  subset = g_ptr_array_new ();
  
  for (xx=0; xx < word_count; xx++) {
    gchar *ready;

    fgets(buf, bufsize, file);
    g_strchomp (buf);

    ready = g_strdup(buf);

    g_ptr_array_add (dict, ready);

    if (xx && xx < word_count-1 && g_rand_int_range(rand, 0,10))
      g_ptr_array_add (disorder, ready);
  }

  while (disorder->len)
    {
      guint from;

      from = g_rand_int_range(rand, 0, disorder->len);
      g_ptr_array_add_sorted (subset,
			      g_ptr_array_index (disorder, from),
			      (GCompareFunc) simple_strcmp);
      g_ptr_array_remove_index (disorder, from);
    }

  for (xx=0; xx < dict->len; xx++)
    {
      glong rx;
      guint at;
      gboolean match;
      
      ++ bsearch_count;
      match = g_ptr_array_bsearch (subset,
				   &at,
				   g_ptr_array_index(dict, xx),
				   (GCompareFunc) count_strcmp);

      if (match)
	{
	  if (strcmp(g_ptr_array_index (subset, at),
		     g_ptr_array_index(dict, xx)) == 0)
	    continue;
	}
      else
	{
	  if (at > 0 && at < subset->len &&
	      strcmp(g_ptr_array_index (subset, at-1),
		     g_ptr_array_index(dict, xx)) < 0 &&
	      strcmp(g_ptr_array_index(dict, xx),
		     g_ptr_array_index (subset, at)) < 0)
	    continue;
	  if (at == 0 &&
	      strcmp(g_ptr_array_index(dict, xx),
		     g_ptr_array_index (subset, at)) < 0)
	    continue;
	  if (at == subset->len &&
	      strcmp(g_ptr_array_index (subset, at-1),
		     g_ptr_array_index(dict, xx)) < 0)
	    continue;
	}

      g_print ("\n%d> %s\n", match, (gchar*) g_ptr_array_index(dict, xx));

      if (match)
	{
	  for (rx = at-1; rx <= at+1; rx++) {
	    if (rx < 0)
	      { g_print ("---\n"); continue; }
	    if (rx >= subset->len)
	      { g_print ("-+-\n"); continue; }
	    g_print ("%s\n", (gchar*) g_ptr_array_index(subset, rx));
	  }
	}
      else
	{
	  for (rx = ((glong)at)-1; rx <= at; rx++) {
	    if (rx < 0)
	      { g_print ("---\n"); continue; }
	    if (rx >= subset->len)
	      { g_print ("-+-\n"); continue; }
	    g_print ("%s\n", (gchar*) g_ptr_array_index(subset, rx));
	  }
	}
    }

  g_print ("%d / %d = %.2f\n",
	   strcmp_count, bsearch_count, strcmp_count / (double) bsearch_count);

  return 0;
}