/* ---------------------------------------------------------------------
   (c) ED 2005-2007
   Project      : CLIB
   Function     : Generic Linked list (implementation)
   Module       : GLL
   File         : gll.c
   Created      : 26-08-2005
   Modified     : 15-04-2007
   --------------------------------------------------------------------- */

/* ---------------------------------------------------------------------
   Log

   1.2 15-04-2007 cancellation of the constanteness for data
   1.1 27-10-2005 Enhanced instrumentation
   1.0 28-08-2005 Intial version
   0.0 26-08-2005 Created

   --------------------------------------------------------------------- */
#ifdef __cplusplus
#error This is not C++. Please use a C compiler.
#endif

#include "ed/inc/gll.h"
#include "ed/inc/sysalloc.h"
#include "ed/inc/sys.h"

/* private macro definitions =========================================== */
#define DBG 0
#define ID "GLL"
#define VER "1.2"

#if DBG
#define MODULE ID"."
#define STR_(s) #s
#define STR(s) STR_(s)
#if 0
#define FUNC __func__"."
#else
#define FUNC __FILE__ ":" STR(__LINE__) "."
#endif
#else
#undef PRINTF
#define PRINTF(a)
#endif

/* private constants =================================================== */

/* private types ======================================================= */

/* private structures ================================================== */

struct node
{
   struct node *p_next;
   struct node *p_prev;
   void *p_data;
};

struct gll
{
   struct node *p_head;
   struct node *p_curr;
   struct node *p_tail;
};

/* private functions =================================================== */

/* ---------------------------------------------------------------------
   is_empty ()
   ---------------------------------------------------------------------

   ---------------------------------------------------------------------
   I:
   O:
   --------------------------------------------------------------------- */
static int is_empty (gll_s * this)
{
   int empty = -1;

   ASSERT (this != NULL);

   empty = this->p_head == NULL;

   PRINTF ((MODULE "empty = %d" EOL, empty));

   return empty;
}

/* ---------------------------------------------------------------------
   node_create ()
   ---------------------------------------------------------------------

   ---------------------------------------------------------------------
   I:
   O:
   --------------------------------------------------------------------- */
static struct node *node_create (void *p_data)
{
   struct node *p_node = malloc (sizeof *p_node);

   if (p_node != NULL)
   {
      p_node->p_next = NULL;
      p_node->p_prev = NULL;
      p_node->p_data = p_data;
   }
   return p_node;
}

/* ---------------------------------------------------------------------
   node_clear_r ()
   ---------------------------------------------------------------------

   ---------------------------------------------------------------------
   I:
   O:
   --------------------------------------------------------------------- */
static void node_clear_r (struct node *p_node)
{
   if (p_node != NULL)
   {
      node_clear_r (p_node->p_next);
      FREE (p_node);
   }
}

/* public internal functions =========================================== */

/* entry points ======================================================== */

/* ---------------------------------------------------------------------
   gll_sid ()
   ---------------------------------------------------------------------

   ---------------------------------------------------------------------
   I:
   O:
   --------------------------------------------------------------------- */
char const *gll_sid (void)
{
   return ID;
}

/* ---------------------------------------------------------------------
   gll_sver ()
   ---------------------------------------------------------------------

   ---------------------------------------------------------------------
   I:
   O:
   --------------------------------------------------------------------- */
char const *gll_sver (void)
{
   return VER;
}

/* ---------------------------------------------------------------------
   gll_serr ()
   ---------------------------------------------------------------------

   ---------------------------------------------------------------------
   I:
   O:
   --------------------------------------------------------------------- */
char const *gll_serr (gll_err_e err)
{
   char const *s = "GLL_ERR_???";

   if (err < GLL_ERR_NB)
   {
      static char const *as[] =
      {
         "GLL_OK",
#define ITEM(n_, s_)\
         #s_,

#include "ed/inc/gll_err.itm"

#undef ITEM

      };
      s = as[err];
   }
   return s;
}

/* ---------------------------------------------------------------------
   gll_create ()
   ---------------------------------------------------------------------

   ---------------------------------------------------------------------
   I:
   O:
   --------------------------------------------------------------------- */
gll_s *gll_create (void)
{
   gll_s *this = malloc (sizeof *this);

   if (this != NULL)
   {
      this->p_head = NULL;
      this->p_curr = NULL;
      this->p_tail = NULL;
   }
   return this;
}

/* ---------------------------------------------------------------------
   gll_delete ()
   ---------------------------------------------------------------------

   ---------------------------------------------------------------------
   I:
   O:
   --------------------------------------------------------------------- */
void gll_delete (gll_s * this)
{
   if (this != NULL)
   {
      node_clear_r (this->p_head);
      free (this);
   }
}

/* ---------------------------------------------------------------------
   gll_is_empty ()
   ---------------------------------------------------------------------

   ---------------------------------------------------------------------
   I:
   O:
   --------------------------------------------------------------------- */
int gll_is_empty (gll_s * this, gll_err_e * p_err)
{
   int empty = 1;
   gll_err_e err = GLL_OK;

   if (this != NULL)
   {
      empty = is_empty (this);
   }
   else
   {
      err = GLL_ERR_CONTEXT;
   }

   if (p_err != NULL)
   {
      *p_err = err;
   }

   return empty;
}

#if 0
/* ---------------------------------------------------------------------
   gll_init ()
   ---------------------------------------------------------------------

   ---------------------------------------------------------------------
   I:
   O:
   --------------------------------------------------------------------- */
gll_err_e gll_init (gll_s * this)
{
   gll_err_e err = GLL_OK;

   if (this != NULL)
   {

/*   -> Insert your code here */

   }
   else
   {
      err = GLL_ERR_CONTEXT;
   }
   return err;
}

/* ---------------------------------------------------------------------
   gll_install_out ()
   ---------------------------------------------------------------------

   ---------------------------------------------------------------------
   I:
   O:
   --------------------------------------------------------------------- */
gll_err_e gll_install_out (gll_s * this, gll_out_f * pf, void *p_usr)
{
   gll_err_e err = GLL_OK;

   if (this != NULL)
   {
      this->pf = pf;
      this->p_usr = p_usr;
   }
   else
   {
      err = GLL_ERR_CONTEXT;
   }
   return err;
}
#endif

#if 0
/* ---------------------------------------------------------------------
   gll_in ()
   ---------------------------------------------------------------------

   ---------------------------------------------------------------------
   I:
   O:
   --------------------------------------------------------------------- */
gll_err_e gll_in (gll_s * this, int data)
{
   gll_err_e err = GLL_OK;

   if (this != NULL)
   {
      if (this->pf != NULL)
      {
         int ret = (*this->pf) (this->p_usr, data);

         if (ret != 0)
         {
            err = GLL_ERR_CB_OUT;
         }
      }
   }
   else
   {
      err = GLL_ERR_CONTEXT;
   }
   return err;
}
#endif

/* ---------------------------------------------------------------------
   gll_goto_head ()
   ---------------------------------------------------------------------

   ---------------------------------------------------------------------
   I:
   O:
   --------------------------------------------------------------------- */
gll_err_e gll_goto_head (gll_s * this)
{
   gll_err_e err = GLL_OK;

   if (this != NULL)
   {
      if (!is_empty (this))
      {
         this->p_curr = this->p_head;
      }
      else
      {
         err = GLL_ERR_EMPTY;
      }
   }
   else
   {
      err = GLL_ERR_CONTEXT;
   }
   PRINTF ((MODULE FUNC "err = %d" EOL, err));
   return err;
}

/* ---------------------------------------------------------------------
   gll_goto_tail ()
   ---------------------------------------------------------------------

   ---------------------------------------------------------------------
   I:
   O:
   --------------------------------------------------------------------- */
gll_err_e gll_goto_tail (gll_s * this)
{
   gll_err_e err = GLL_OK;

   if (this != NULL)
   {
      if (!is_empty (this))
      {
         this->p_curr = this->p_tail;
      }
      else
      {
         err = GLL_ERR_EMPTY;
      }
   }
   else
   {
      err = GLL_ERR_CONTEXT;
   }
   PRINTF ((MODULE FUNC "err = %d" EOL, err));
   return err;
}

/* ---------------------------------------------------------------------
   gll_next ()
   ---------------------------------------------------------------------

   ---------------------------------------------------------------------
   I:
   O:
   --------------------------------------------------------------------- */
gll_err_e gll_next (gll_s * this)
{
   gll_err_e err = GLL_OK;

   if (this != NULL)
   {
      if (!is_empty (this))
      {
         if (this->p_curr != NULL)
         {
            if (this->p_curr->p_next != NULL)
            {
               this->p_curr = this->p_curr->p_next;
            }
            else
            {
               err = GLL_ERR_CURR_AT_END;
            }
         }
         else
         {
            err = GLL_ERR_CURR_UNDEFINED;
         }
      }
      else
      {
         err = GLL_ERR_EMPTY;
      }
   }
   else
   {
      err = GLL_ERR_CONTEXT;
   }
   PRINTF ((MODULE FUNC "err = %d" EOL, err));
   return err;
}

/* ---------------------------------------------------------------------
   gll_prev ()
   ---------------------------------------------------------------------

   ---------------------------------------------------------------------
   I:
   O:
   --------------------------------------------------------------------- */
gll_err_e gll_prev (gll_s * this)
{
   gll_err_e err = GLL_OK;

   if (this != NULL)
   {
      if (!is_empty (this))
      {
         if (this->p_curr != NULL)
         {
            if (this->p_curr->p_prev != NULL)
            {
               this->p_curr = this->p_curr->p_prev;
            }
            else
            {
               err = GLL_ERR_CURR_AT_TOP;
            }
         }
         else
         {
            err = GLL_ERR_CURR_UNDEFINED;
         }
      }
      else
      {
         err = GLL_ERR_EMPTY;
      }
   }
   else
   {
      err = GLL_ERR_CONTEXT;
   }
   PRINTF ((MODULE FUNC "err = %d" EOL, err));
   return err;
}

/* ---------------------------------------------------------------------
   gll_read_data ()
   ---------------------------------------------------------------------

   ---------------------------------------------------------------------
   I:
   O:
   --------------------------------------------------------------------- */
void *gll_read_data (gll_s * this, gll_err_e * p_err)
{
   void *p_data = NULL;
   gll_err_e err = GLL_OK;

   if (this != NULL)
   {
      if (!is_empty (this))
      {
         if (this->p_curr != NULL)
         {
            p_data = this->p_curr->p_data;
         }
         else
         {
            err = GLL_ERR_CURR_UNDEFINED;
         }
      }
      else
      {
         err = GLL_ERR_EMPTY;
      }
   }
   else
   {
      err = GLL_ERR_CONTEXT;
   }

   if (p_err != NULL)
   {
      *p_err = err;
   }

   PRINTF ((MODULE FUNC "err = %d" EOL, err));
   return p_data;
}

/* ---------------------------------------------------------------------
   gll_clear ()
   ---------------------------------------------------------------------

   ---------------------------------------------------------------------
   I:
   O:
   --------------------------------------------------------------------- */
gll_err_e gll_clear (gll_s * this)
{
   gll_err_e err = GLL_OK;

   if (this != NULL)
   {
      node_clear_r (this->p_head);

      this->p_curr = NULL;
      this->p_head = NULL;
      this->p_tail = NULL;
   }
   else
   {
      err = GLL_ERR_CONTEXT;
   }
   PRINTF ((MODULE FUNC "err = %d" EOL, err));
   return err;
}

/* ---------------------------------------------------------------------
   gll_insert_left ()
   ---------------------------------------------------------------------

   ---------------------------------------------------------------------
   I:
   O:
   --------------------------------------------------------------------- */
gll_err_e gll_insert_left (gll_s * this, void *p_data)
{
   gll_err_e err = GLL_OK;

   if (this != NULL)
   {
      struct node *p_node = node_create (p_data);

      if (p_node != NULL)
      {
         if (is_empty (this))
         {
            /* NIL <- A -> NIL */
            this->p_head = p_node;
            this->p_tail = p_node;
         }
         else
         {
            /* NIL <- A -> NIL
             *        H
             *        T
             */

            /* B <- A */
            this->p_head->p_prev = p_node;

            /* B -> A */
            p_node->p_next = this->p_head;

            /* NIL <- B <=...=> A -> NIL
             *        H         T
             */
            this->p_head = p_node;
         }

         /* the current pointer points to the last entered node */
         this->p_curr = p_node;
      }
      else
      {
         err = GLL_ERR_MEMORY;
      }
   }
   else
   {
      err = GLL_ERR_CONTEXT;
   }
   PRINTF ((MODULE FUNC "err = %d" EOL, err));
   return err;
}

/* ---------------------------------------------------------------------
   gll_insert_right ()
   ---------------------------------------------------------------------

   ---------------------------------------------------------------------
   I:
   O:
   --------------------------------------------------------------------- */
gll_err_e gll_insert_right (gll_s * this, void *p_data)
{
   gll_err_e err = GLL_OK;

   if (this != NULL)
   {
      struct node *p_node = node_create (p_data);

      if (p_node != NULL)
      {
         if (is_empty (this))
         {
            /* NIL <- A -> NIL */
            this->p_head = p_node;
            this->p_tail = p_node;
         }
         else
         {
            /* NIL <- A -> NIL
             *        H
             *        T
             */

            /* A -> B */
            this->p_tail->p_next = p_node;

            /* A <- B */
            p_node->p_prev = this->p_tail;

            /* NIL <- A <=...=> B -> NIL
             *        H         T
             */
            this->p_tail = p_node;
         }

         /* the current pointer points to the last entered node */
         this->p_curr = p_node;
      }
      else
      {
         err = GLL_ERR_MEMORY;
      }
   }
   else
   {
      err = GLL_ERR_CONTEXT;
   }
   PRINTF ((MODULE FUNC "err = %d" EOL, err));
   return err;
}

/* ---------------------------------------------------------------------
   gll_remove ()
   ---------------------------------------------------------------------

   ---------------------------------------------------------------------
   I:
   O:
   --------------------------------------------------------------------- */

void *gll_remove (gll_s * this, gll_err_e * p_err)
{
   void *p_data = NULL;
   gll_err_e err = GLL_OK;

   if (this != NULL)
   {
      if (!is_empty (this))
      {
         if (this->p_curr != NULL)
         {
            struct node *p_node = this->p_curr;

            p_data = p_node->p_data;

            /* remake the links */

            if (this->p_curr->p_next == NULL
                && this->p_curr->p_prev == NULL)
            {
               /* last */
               this->p_curr = NULL;
               this->p_head = NULL;
               this->p_tail = NULL;
            }
            else
            {
               /* not last */

               if (this->p_curr == this->p_head)
               {
                  /* head */
                  ASSERT (this->p_curr->p_next != NULL);

                  this->p_curr->p_next->p_prev = NULL;
                  this->p_head = this->p_head->p_next;
                  this->p_curr = this->p_head;
               }
               else if (this->p_curr == this->p_tail)
               {
                  /* tail */
                  ASSERT (this->p_curr->p_prev != NULL);

                  this->p_curr->p_prev->p_next = NULL;
                  this->p_tail = this->p_tail->p_prev;
                  this->p_curr = this->p_tail;
               }
               else
               {
                  /* middle ? */
                  ASSERT (this->p_curr->p_next != NULL);
                  ASSERT (this->p_curr->p_prev != NULL);

                  this->p_curr->p_prev->p_next = this->p_curr->p_next;
                  this->p_curr->p_next->p_prev = this->p_curr->p_prev;

                  /* 'next' priority (arbitrary) */
                  if (this->p_curr->p_next != NULL)
                  {
                     this->p_curr = this->p_curr->p_next;
                  }
                  else if (this->p_curr->p_prev != NULL)
                  {
                     this->p_curr = this->p_curr->p_prev;
                  }
                  else
                  {
                     ASSERT (0);
                  }
               }
            }
            FREE (p_node);

            PRINTF ((MODULE FUNC "gll_remove.data=%p (%s)" EOL
            , (void *) p_data
            , (char *) p_data
            ));
         }
         else
         {
            err = GLL_ERR_CURR_UNDEFINED;
         }
      }
      else
      {
         err = GLL_ERR_EMPTY;
      }
   }
   else
   {
      err = GLL_ERR_CONTEXT;
   }

   if (p_err != NULL)
   {
      *p_err = err;
   }

   PRINTF ((MODULE FUNC"err = %d" EOL, err));
   return p_data;
}

/* public data ========================================================= */

/* ---------------------------------------------------------------------
   Generated by NEW (c) ED 2.8
   Powered by C-code generator library  1.2
   --------------------------------------------------------------------- */