invasive doubly linked list

[Joshua N Pritikin <vishnu pobox com>]

Is there any interest in this whatsoever?

An implementation and test suite are attached.  i can write documentation, but
for now you can study the ringtest.c for usage.  Shall i file a bugzilla
enhancement request?

Please comment!

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

#include <glib.h>

#ifndef __G_RING_H__
#define __G_RING_H__

// G_BEGIN_DECLS

typedef struct _GRing GRing;

struct _GRing {
  gpointer self;
  GRing *next;
  GRing *prev;
};

void       g_ring_init             (GRing *ring, gpointer self);
void       g_ring_append           (GRing *r1, GRing *r2);
void       g_ring_prepend          (GRing *r1, GRing *r2);
gpointer   g_ring_detach           (GRing *ring);
guint      g_ring_length           (GRing *first);
void       g_ring_foreach          (GRing *first, GFunc func, gpointer user_data);
GRing     *g_ring_find             (GRing *first, GCompareFunc func, gpointer user_data);
gboolean   g_ring_insert_sorted    (GRing *first, GRing *ready, GCompareFunc func);

#define    g_ring_detached(r1)     ((r1)==(r1)->next)

// G_END_DECLS

#endif  /* __G_RING_H__ */

#include "gring.h"

void
g_ring_init (GRing *ring, gpointer self)
{
  ring->self = self;
  ring->next = ring;
  ring->prev = ring;
}

void
g_ring_prepend (GRing *r1, GRing *r2)
{
  g_return_if_fail(g_ring_detached(r2));

  r2->next = r1;
  r2->prev = r1->prev;
  r2->next->prev = r2;
  r2->prev->next = r2;
}

void
g_ring_append (GRing *r1, GRing *r2)
{
  g_return_if_fail(g_ring_detached(r2));

  r2->next = r1->next;
  r2->prev = r1;
  r2->next->prev = r2;
  r2->prev->next = r2;
}

gpointer
g_ring_detach (GRing *ring)
{
  ring->next->prev = ring->prev;
  ring->prev->next = ring->next;
  ring->next = ring->prev = ring;
  return ring->self;
}

void
g_ring_foreach (GRing *first,
		GFunc func,
		gpointer user_data)
{
  GRing *ring;
  GRing *next;

  ring = first;

  do
    {
      next = ring->next;
      (*func) (ring->self, user_data);
      ring = next;
    }
  while (ring != first);
}

guint
g_ring_length (GRing *first)
{
  GRing *ring;
  guint length;
 
  ring = first;
  length = 0;

  do
    {
      ++length;
      ring = ring->next;
    }
  while (ring != first);
 
  return length;
}

GRing *
g_ring_find (GRing *first,
	     GCompareFunc func,
	     gpointer user_data)
{
  GRing *ring;

  g_return_val_if_fail (func != NULL, NULL);

  ring = first;

  do
    {
      if (! (*func) (ring->self, user_data))
	return ring;
      ring = ring->next;
    }
  while (ring != first);
  
  return NULL;
}

gboolean
g_ring_insert_sorted (GRing *first,
		      GRing *ready,
		      GCompareFunc func)
{
  GRing *ring = first;
  gint cmp;

  g_return_val_if_fail (g_ring_detached(ready), FALSE);
  g_return_val_if_fail (func, FALSE);

  if (ring == ready)
    return FALSE;

  cmp = (*func)(ready->self, ring->self);

  if (cmp < 0)
    {
      g_ring_prepend(ring, ready);
      return TRUE;
    }

  while (ring->next != first && cmp > 0)
    {
      ring = ring->next;
      cmp = (*func)(ready->self, ring->self);
    }

  if (cmp > 0)
      g_ring_append(ring, ready);
  else
      g_ring_prepend(ring, ready);

  return FALSE;
}

#include "gring.h"

typedef struct _Zorf {
  gchar *str;
  GRing ring;
} Zorf;

Zorf *string_new(gchar *_str) {
  Zorf *str = g_new(Zorf, 1);

  str->str = g_strdup(_str);
  g_ring_init(&str->ring, str);

  return str;
}

void string_print(Zorf *str, gpointer _ign) {
  g_print(" %s", str->str);
}

int find_name(Zorf *s1, Zorf *s2)
{ return strcmp (s1->str, s2->str); }

static GRing *names;

void show_names() {
  g_print("Names:");
  g_ring_foreach(names, (GFunc) string_print, NULL);
  g_print("\n");
}

void _concat(Zorf *str, GString *buf)
{ g_string_append(buf, str->str); }

GString *concat_names()
{
  GString *buf = g_string_new(NULL);
  // show_names();
  g_ring_foreach(names, (GFunc) _concat, buf);
  return buf;
}

int main() {
  GString *concat;
  Zorf *str;
  GRing *ring;
  gboolean head;

  names = &string_new("b")->ring;

  g_ring_prepend(names, &string_new("e")->ring);
  g_ring_append(names, &string_new("d")->ring);
  g_ring_prepend(names, &string_new("f")->ring);

  concat = concat_names();
  g_assert(strcmp(concat->str, "bdef")==0);
  g_string_free(concat, TRUE);

  str = g_ring_detach(names->prev);
  g_assert(strcmp(str->str, "f")==0);
  g_assert(g_ring_length(names) == 3);
  g_ring_prepend(names, &str->ring);

  concat = concat_names();
  g_assert(strcmp(concat->str, "bdef")==0);
  g_string_free(concat, TRUE);

  g_assert(g_ring_length(names) == 4);

  ring = g_ring_find(names, (GCompareFunc) find_name, string_new ("b"));
  g_assert(ring);
  g_assert (strcmp (((Zorf*)ring->self)->str, "b")==0);

  ring = g_ring_find(names, (GCompareFunc) find_name, string_new ("f"));
  g_assert(ring);
  g_assert (strcmp (((Zorf*)ring->self)->str, "f")==0);

  ring = g_ring_find(names, (GCompareFunc) find_name, string_new ("c"));
  g_assert(!ring);

  ring = &string_new("a")->ring;
  head = g_ring_insert_sorted(names, ring, (GCompareFunc) find_name);
  g_assert(head);
  names = ring;

  concat = concat_names();
  g_assert(strcmp(concat->str, "abdef")==0);
  g_string_free(concat, TRUE);
  
  ring = &string_new("c")->ring;
  head = g_ring_insert_sorted(names, ring, (GCompareFunc) find_name);
  g_assert(!head);

  ring = &string_new("g")->ring;
  head = g_ring_insert_sorted(names, ring, (GCompareFunc) find_name);
  g_assert(!head);

  concat = concat_names();
  g_assert(strcmp(concat->str, "abcdefg")==0);
  g_string_free(concat, TRUE);
  
  return 0;
}