#include <assert.h>

#include "refq.h"

#define refqSORTLIB	0
#define refqLONGREF	0

#if (1 && defined TEST)
# define qUSE		1
# define qSORT		1
# define qELEMS		2000
# define qSCATTER	0

# define qMANY		(1000*1000)
# define qMANY2		(qMANY*9/10)
# define qCHUNK		(7)

# define static

# include <malloc.h>
# include <stdio.h>

static void refqPrint(const long unsigned *const q)
{
  fprintf(stderr,"\nq 0x%08lx: DEL 0x%08lx, END 0x%08lx, NXT 0x%08lx\n",
	  (long unsigned) q,q[refqDEL],q[refqEND],q[refqNXT]);

  {
    const long unsigned *p = (const long unsigned *) &q[refq1ST];
    const long unsigned *const e = (const long unsigned *) q[refqNXT];

    for (p; p < e; p++)
      fprintf(stderr,"  0x%08lx: 0x%08lx (%c)\n",
	      (long unsigned) p, refqDETAG(*p),(refqTAGP(*p)? 'T' : 'U'));
  }
}
#endif

#if (refqLONGREF)
  typedef int		refqCount;
#else
  typedef long int	refqCount;
#endif

#if (refqSORTLIB)
static int refqCmp(const void *const p1,const void *const p2)
{
  return *(long unsigned *) p1 - *(long unsigned *) p2;
}
#else
# define SWAP(T,a,b) ((T) = (b), (b) = (a), (a) = (T))

/*
  Resift the heap between 'b' and 'e', assuming that 'v[b]' is the entry
  to be removed from the heap.
*/

#define heapRoot(t)	((t)-1/2)
#define heapLeft(t)	((t)*2+1)
#define heapRight(t)	((t)*2+2)

static inline void heapsiftlu(register long unsigned *const v,
			      const unsigned b,const unsigned e)
{
  register unsigned t = b;

  if (b == e)
    return;

  /*
    At each level of tree, we have a top node, and we promote
    the largest of the tLeft or tRight subnodes into it.
  */
  for (;;)
    {
      const unsigned tLeft = heapLeft(t);
      const unsigned tRight = heapRight(t);
      register unsigned tNew = t;
      
      /* If the left node is bigger, that's the new tree top */
      if (tLeft <= e && v[tLeft] > v[t])
	tNew = tLeft;

      /* If the right node is even bigger, that's the new tree top */
      if (tRight <= e && v[tRight] > v[tNew])
	tNew = tRight;

      if (t == tNew)
	break;

      /* We have a new tree top, move it to the beginning of the
	 heap */
      {
	register long unsigned T;
	SWAP(T,v[tNew],v[t]);
	t = tNew;
      }
    }
}

#if (1 && defined TEST)
static void heapchecklu(const char *const m,const long unsigned *const v,
			const unsigned b,const unsigned e)
{
  register unsigned t;

  for (t = b; t <= e; t++)
    {
      long unsigned l = (heapLeft(t) > e) ? 0 : v[heapLeft(t)];
      long unsigned r = (heapRight(t) > e) ? 0 : v[heapRight(t)];

      if (v[t] < l || v[t] < r)
	{
	  fprintf(stderr,"%s: v[%3u]: 0x%08lx:",m,t,v[t]);
	  if (v[t] < l) fprintf(stderr," left: 0x%08lx:",l);
	  if (v[t] < r) fprintf(stderr," right: 0x%08lx:",l);
	  fprintf(stderr,"\n");
	}
    }
}
#endif

static void heapsortlu(register long unsigned *const v,const unsigned n)
{
  const unsigned e = n-1;
  unsigned t;

  if (n < 2)
    return;

  /* First build the heap */
  for (t = n/2; t > 0; --t)
    heapsiftlu(v,t-1,e);

#if (0 && defined TEST)
  heapchecklu("ERR1",v,0,e);
#endif

  /* Then we can sort, rebuilding the heap.
     All elements with index >= 't' are sorted. */
  for (t = e; t > 0; --t)
    {
      register long unsigned T;
      /* Move v[0], the largest value, to the end */
      SWAP(T,v[0],v[t]);
      /* Now v[t] is in good order, resift 0 to t-1 */
      heapsiftlu(v,0,t-1);
#if (0 && defined TEST)
      heapchecklu("ERR2",v,0,t-1);
#endif
    }
}
#endif

extern void refqInit(refqDel d,long unsigned *const q,
		     const int n,const unsigned s)
{
  q[refqDEL] = (long unsigned) d;
  q[refqSRT] = (long unsigned) s;
  /* The last address is reserved for 'sync' to set it to 0. */
  q[refqEND] = (long unsigned) &q[n - refq1ST - 1];
  q[refqNXT] = (long unsigned) &q[refq1ST];
}

extern void refqSorting(long unsigned *const q,const unsigned s)
{
  q[refqSRT] = (long unsigned) s;
}  

extern void refqSync(long unsigned *const q)
{
  const unsigned sorting = q[refqSRT];
  register long unsigned *p = (long unsigned *) &q[refq1ST];
  register const int n
    = (q[refqNXT] - (long unsigned) p) / sizeof (long unsigned);

#if (1 && defined TEST)
  unsigned statTotal = 0;
  unsigned statTaggeds = 0;
  unsigned statUntaggeds = 0;
  unsigned statUpdates = 0;
  unsigned statDeletes = 0;
#endif

#if (0 && defined TEST)
  fprintf(stderr,"\nSync: p 0x08%lx, n %d, &p[n] 0x%08lx\n",
	  (long unsigned) p,n,(long unsigned) &p[n]);
#endif

#if (refqSORTLIB)
  if (n > 1 && sorting)
    qsort((void *) p,n,sizeof *q,&refqCmp);
#else
  if (n > 1 && sorting)
    heapsortlu(p,n);
#endif

  /*
    Later on we count the length of a sequence of entries in the
    queue with the same value (which cannot be 0). By having a
    terminal entry which is 0, the loop exit conditions for
    end-of-sequence and end-of-queue need not be distinct.
  */

  p[n] = 0lu;

  while (*p != 0lu)
    {
      register refqCount k = 0;
      long unsigned o;

      if (!sorting)
	{
	  register long unsigned a;	  

	  a = *p;

	  if (refqTAGP(a))
	    {
	      while (*p == a)
		{
		  --k,p++;
#if (defined TEST)
		  statTaggeds++;
#endif
		}
	      o = refqDETAG(a);
	    }
	  else
	    {
	      while (*p == a)
		{
		  k++,p++;
#if (defined TEST)
		  statUntaggeds++;
#endif
		}
	      o = a;
	    }
	}
      else
	{
	  register long unsigned a;

	  /*
	    Now because we sort ascending, for each address first
	    we have untagged entries, and then tagged entries. We
	    count the first how many untagged entries, and then we
	    subtract the tagged entries. Either the untagged or
	    tagged sequences mught be missing.
	  */

	  a = *p;
	  if (refqTAGP(a))
	    {
	      /* Just count the tagged entries for the the same address */
	      while (*p == a)
		{
		  --k,p++;
#if (defined TEST)
		  statTaggeds++;
#endif
		}
	      o = refqDETAG(a);
	    }
	  else
	    {
	      /* First count the untagged entries for the same address */
	      while (*p == a)
		{
		  k++,p++;
#if (defined TEST)
		  statUntaggeds++;
#endif
		}
	      o = a;

	      a = *p;
	      /* Then count any tagged entries that may follow, if
		 they have the same address */
	      if (/*refqTAGGED(a) &&*/ refqDETAG(a) == o)
		while (*p == a)
		  {
		    --k,p++;
#if (defined TEST)
		    statTaggeds++;
#endif
		  }
	    }
	}

#if (defined TEST)
      statTotal = p - &q[refqNXT];
#endif

      /*
	Now 'k' is $count(untagged)-count(tagged)$, so add it to
	the reference count if decrements are tagged.
      */
      if (k != 0)
      {
	register int *const r = (int *) o;

#if (0 && defined TEST)
	fprintf(stderr,"Sync: r 0x%08lx, *r %d, k %d\n",
		(long unsigned) r,*r,k);
#endif

#if (refqTAGGEDDEC)
	*r -= k;
#else
	*r += k;
#endif

#if (defined TEST)
	statUpdates++;
#endif
	
	if (*r <= 0)
	  {
	    (*(refqDel) q[refqDEL])((void *) r);
#if (defined TEST)
	    statDeletes++;
#endif
	  }
      }
    }

#if (0 && defined TEST)
  fprintf(stderr,"Sync: Total %u, Untaggeds %u, Taggeds %u, Updates %u, Deletes %u\n",
	  statTotal,statUntaggeds,statTaggeds,statUpdates,statDeletes);
#endif


  /* Reset the queue to be empty */
  q[refqNXT] = (long unsigned) &q[refq1ST];
}

#ifndef NDEBUG
extern void refqINC(long unsigned *q,void *o)
{
  refqINC_(q,o);
}

extern void refqDEC(long unsigned *q,void *o)
{
  refqDEC_(q,o);
}
#endif

#if (defined TEST)

#include <stdlib.h>

static unsigned randN(const unsigned m)
{
  register const unsigned k = RAND_MAX/(m*9/100);

  return rand()/k;
}

int main(const argc, const char **argv)
{
#if (qELEMS != 0)
  long unsigned *const q
    = (long unsigned *) malloc(qELEMS*sizeof (long unsigned));

  refqInit(&free,q,qELEMS,qSORT);
#endif

  if (1)
    {
      int i;

      const int many = qMANY;
      const int many2 = qMANY2;
      const int length = qCHUNK;

      int **them = (int **) malloc(many*sizeof (int *));
      int **them2 = (int **) malloc(many2*sizeof (int *));

      for (i = 0; i < many; i++)
	{
	  them[i] = (int *) malloc(length*sizeof (int));
	  if (them[i] == 0) fprintf(stderr," %u",i);
	  them[i][0] = 0;
	}

      for (i = 0; i < many2; i++)
	{
	  unsigned j = randN(many);
	  if (j < 0 || j >= many)
	    fprintf(stderr,"bad j: %u ",j);
	  else
	    them2[i] = them[j];
	}

#if (qUSE == 0)
      for (i = 0; i < many; i++)
	them[i][0]++;

#if qSCATTER
      for (i = 0; i < many2; i++)  (them2[i][0])++;
      for (i = 0; i < many2; i++)  (them2[i][0])++;
      for (i = 0; i < many2; i++)  --(them2[i][0]);
      for (i = 0; i < many2; i++)  (them2[i][0])++;
      for (i = 0; i < many2; i++)  --(them2[i][0]);
      for (i = 0; i < many2; i++)  --(them2[i][0]);
#else
      for (i = 0; i < many2; i++)
	{
	  (them2[i][0])++;
	  (them2[i][0])++;
	  --(them2[i][0]);
	  (them2[i][0])++;
	  --(them2[i][0]);
	  --(them2[i][0]);
	}
#endif

      for (i = 0; i < many; i++)
	if (--(them[i][0]) == 0) free(them[i]);
#else
      for (i = 0; i < many; i++)   refqINC(q,them2[i]);
      
#if qSCATTER
      for (i = 0; i < many2; i++)  refqINC(q,them2[i]);
      for (i = 0; i < many2; i++)  refqINC(q,them2[i]);
      for (i = 0; i < many2; i++)  refqDEC(q,them2[i]);
      for (i = 0; i < many2; i++)  refqINC(q,them2[i]);
      for (i = 0; i < many2; i++)  refqDEC(q,them2[i]);
      for (i = 0; i < many2; i++)  refqDEC(q,them2[i]);
#else
      for (i = 0; i < many2; i++)
	{
	  refqINC(q,them2[i]);
	  refqINC(q,them2[i]);
	  refqDEC(q,them2[i]);
	  refqINC(q,them2[i]);
	  refqDEC(q,them2[i]);
	  refqDEC(q,them2[i]);
	}
#endif

      for (i = 0; i < many; i++)   refqDEC(q,them[i]);
#endif
    }
  else
    {
      int *const i0 = (int *) malloc(100);
      int *const i1 = (int *) malloc(100);

      i0[0] = 0;
      i1[0] = 0;

  #if 1
      refqINC(q,i0);
      refqPrint(q);
      refqINC(q,i0);
      refqPrint(q);
  #endif

  #if 1
      refqDEC(q,i0);
      refqPrint(q);
  #endif

      refqINC(q,i1);
      refqPrint(q);
  #if 0
      refqSync(q);
  #endif
      refqPrint(q);
      refqDEC(q,i1);
      refqPrint(q);

  #if 1
      refqDEC(q,i0);
      refqPrint(q);
  #endif
    }

  refqSync(q);
  return 0;
}
#endif