/*
                             *******************
******************************* C SOURCE FILE *******************************
**                           *******************                           **
**                                                                         **
** project      : The C Kernel                                             ** 
** filename     : CKQUEUE.C                                                **
** version      : 2                                                        **
** last revised : August 22, 2004                                          **
**                                                                         **
*****************************************************************************
**                                                                         **
** Copyright (c) 1998-2004, P.K. van der Vlugt                             **
** All rights reserved.                                                    **
**                                                                         **
*****************************************************************************

VERSION HISTORY:
----------------

Version     : 1
Date        : June 01, 2003
Revised by  : P.K. van der Vlugt
Description : Original version.

Version     : 2
Date        : August 22, 2004
Revised by  : P.K. van der Vlugt
Description : * Changed module name to comply to new kernel module naming 
                convention.

*/

#define _CKQUEUE_C_SRC

/****************************************************************************/
/**                                                                        **/
/**                     MODULES USED                                       **/
/**                                                                        **/
/****************************************************************************/

#include "ckqueue.h"

/****************************************************************************/
/**                                                                        **/
/**                     DEFINITIONS AND MACROS                             **/
/**                                                                        **/
/****************************************************************************/

#define MAX_KEY   0xFFFF
#define MIN_KEY   0

/****************************************************************************/
/**                                                                        **/
/**                     TYPEDEFS AND STRUCTURES                            **/
/**                                                                        **/
/****************************************************************************/

/****************************************************************************/
/**                                                                        **/
/**                     PROTOTYPES OF LOCAL FUNCTIONS                      **/
/**                                                                        **/
/****************************************************************************/

static void init (int8u id);

/****************************************************************************/
/**                                                                        **/
/**                     EXPORTED VARIABLES                                 **/
/**                                                                        **/
/****************************************************************************/

QueueType Q[NR_OF_QENTRIES];

/****************************************************************************/
/**                                                                        **/
/**                     GLOBAL VARIABLES                                   **/
/**                                                                        **/
/****************************************************************************/

static bool Qreq[NR_OF_QUEUES];

/****************************************************************************/
/**                                                                        **/
/**                     EXPORTED FUNCTIONS                                 **/
/**                                                                        **/
/****************************************************************************/

/****************************************************************************/
void QueueInit (void)
/****************************************************************************/
{
int8u id;

  /**** Initialize all id's ****/
  for (id = 0; id < NR_OF_QUEUES; id++)
    init (id);
}

/****************************************************************************/
int8u QueueAlloc (void)
/****************************************************************************/
{
int8u id;

  for (id = 0; id < NR_OF_QUEUES; id++)
  {
    /**** Search for a free Id ****/
    if (!Qreq[id])
    {
      /**** Initialize head and tail ****/
      init (id);
      /**** Mark id as allocated ****/
      Qreq[id] = TRUE;
      break;
    }
  }

  return (id);
}

/****************************************************************************/
void QueueFree (int8u id)
/****************************************************************************/
{
  /**** Cannot free illegal id ****/
  if (id >= NR_OF_QUEUES)
    return;

  init (id);
}

/****************************************************************************/
void Enqueue (int8u qid, int8u tid)
/****************************************************************************/
{
int16u t, prev;

  /**** Get tail index for queue ****/
  t = Tail (qid);
  /**** Item next points to tail ****/
  Q[tid].qnext = t;
  /**** Previous item of tail ****/
  prev = Q[t].qprev;
  /**** Item prev to tail's prev ****/
  Q[tid].qprev = prev;
  /**** Prev item's next to item ****/
  Q[prev].qnext = tid;
  /**** Tail prev to item ****/
  Q[t].qprev = tid;
}

/****************************************************************************/
void Dequeue (int8u tid)
/****************************************************************************/
{
int16u id;

  /**** Item prev pointer ****/
  id = Q[tid].qprev;
  /**** Prev next to item's next ****/
  Q[id].qnext = Q[tid].qnext;
  /**** Item next pointer ****/
  id = Q[tid].qnext;
  /**** Next prev to item's prev ****/
  Q[id].qprev = Q[tid].qprev;
}

/****************************************************************************/
void Insert (int8u qid, int8u tid, int16u key)
/****************************************************************************/
{
int16u h;
int16u next, prev;

  /**** Get qeueue head ****/
  h = Head (qid);

  /**** Get next pointer ****/
  next = Q[h].qnext;
  /**** Find entry base on it's key ****/
  while (Q[next].qkey < key)
    next = Q[next].qnext;

  /**** Next insert in queue ****/
  Q[tid].qnext = next;
  prev = Q[next].qprev;
  Q[tid].qprev = prev;
  Q[tid].qkey = key;
  Q[prev].qnext = tid;
  Q[next].qprev = tid;
}

/****************************************************************************/
int8u GetFirst (int8u qid)
/****************************************************************************/
{
int16u h;
int16u tid;

  /**** Get first item from queue head ****/
  h = Head (qid);
  tid = Q[h].qnext;
  if (tid < NR_OF_TASKS)
  {
    Dequeue ((int8u) tid);

    return ((int8u) tid);
  }
  else
    return (LIST_EMPTY);
}

/****************************************************************************/
int8u GetLast (int8u qid)
/****************************************************************************/
{
int16u t;
int16u tid;

  /**** Get last item from queue tail ****/
  t = Tail (qid);
  tid = Q[t].qprev;
  if (tid < NR_OF_TASKS)
  {
    Dequeue ((int8u) tid);

    return ((int8u) tid);
  }
  else
    return (LIST_EMPTY);
}

/****************************************************************************/
void InsertDelta (int8u qid, int8u tid, int16u key)
/****************************************************************************/
{
int16u prev, next;

  /**** Insert item based on delta key ****/
  prev = Head (qid);
  next = FirstId (qid);
  while (Q[next].qkey < key)
  {
    key = key - Q[next].qkey;
    prev = next;
    next = Q[next].qnext;
  }

  Q[tid].qnext = next;
  Q[tid].qprev = prev;
  Q[tid].qkey  = key;

  Q[prev].qnext = tid;
  Q[next].qprev = tid;

  if (next < NR_OF_TASKS)
    Q[next].qkey = Q[next].qkey - key;
}

/****************************************************************************/
void DeleteDelta (int8u tid)
/****************************************************************************/
{
int16u next;

  /**** Delete delta item from queue ****/
  next = Q[tid].qnext;
  if (next < NR_OF_TASKS)
    Q[next].qkey = Q[next].qkey + Q[tid].qkey;

  Dequeue (tid);
}

/****************************************************************************/
/**                                                                        **/
/**                     LOCAL FUNCTIONS                                    **/
/**                                                                        **/
/****************************************************************************/

/****************************************************************************/
static void init (int8u id)
/****************************************************************************/
{
int16u h, t;

  Qreq[id] = FALSE;

  h = Head (id);
  t = Tail (id);

  Q[h].qkey  = MIN_KEY;
  Q[h].qnext = t;
  Q[h].qprev = LIST_EMPTY;

  Q[t].qkey  = MAX_KEY;
  Q[t].qnext = LIST_EMPTY;
  Q[t].qprev = h;
}

/****************************************************************************/
/**                                                                        **/
/**                               EOF                                      **/
/**                                                                        **/
/****************************************************************************/