/*  File: arraysub.c
 *  Author: Jean Thierry-Mieg (mieg@mrc-lmba.cam.ac.uk)
 *  Copyright (C) J Thierry-Mieg and R Durbin, 1991
 *-------------------------------------------------------------------
 * This file is part of the ACEDB genome database package, written by
 *      Richard Durbin (MRC LMB, UK) rd@mrc-lmba.cam.ac.uk, and
 *      Jean Thierry-Mieg (CRBM du CNRS, France) mieg@crbm.cnrs-mop.fr
 *
 * Description:
 *              Arbitrary length arrays, stacks, associators
 *              line breaking and all sorts of other goodies
 *              These functions are declared in array.h
 *               (part of regular.h - the header for libfree.a)
 * Exported functions:
 *              See Header file: array.h (includes lots of macros)
 * HISTORY:
 * Last edited: Dec  4 11:12 1998 (fw)
 * * Nov  1 16:11 1996 (srk)
 *              -       MEM_DEBUG code clean-up 
 *                      (some loose ends crept in from WIN32)
 *              -       int (*order)(void*,void*) prototypes used 
 *                                            uniformly throughout
 * * Jun  5 00:48 1996 (rd)
 * * May  2 22:33 1995 (mieg): killed the arrayReport at 20000
      otherwise it swamps 50 Mbytes of RAM
 * * Jan 21 16:25 1992 (mieg): messcrash in uArrayCreate(size<=0)
 * * Dec 17 11:40 1991 (mieg): stackTokeniseTextOn() tokeniser.
 * * Dec 12 15:45 1991 (mieg): Stack magic and stackNextText
 * Created: Thu Dec 12 15:43:25 1989 (mieg)
 *-------------------------------------------------------------------
 */
/* $Id: arraysub.c,v 1.1 2002/11/14 20:00:06 lstein Exp $        */
   /* Warning : if you modify Array or Stack structures or 
      procedures in this file or array.h, you may need to modify 
      accordingly the persistent array package asubs.c.
   */
#include "regular.h"
/*#include <limits.h>*/
extern BOOL finalCleanup ;      /* in messubs.c */
/******** tells how much system stack used *********/
char *stackorigin ;
unsigned int stackused (void)
{ char x ;
  if (!stackorigin)          /* ideally should set in main() */
    stackorigin = &x ;
  return stackorigin - &x ;        /* MSDOS stack grows down */
}
/************ Array : class to implement variable length arrays ************/
static int totalAllocatedMemory = 0 ;
static int totalNumberCreated = 0 ;
static int totalNumberActive = 0 ;
static Array reportArray = 0 ;
static void uArrayFinalise (void *cp) ;
#ifndef MEM_DEBUG
  Array uArrayCreate (int n, int size, STORE_HANDLE handle)
{ int id = totalNumberCreated++ ;
  Array new = (Array) handleAlloc (uArrayFinalise, 
                                   handle,
                                   sizeof (struct ArrayStruct)) ;
#else
Array   uArrayCreate_dbg (int n, int size, STORE_HANDLE handle,
                                              const char *hfname,int hlineno) 
{ int id = totalNumberCreated++ ;
  Array new = (Array) handleAlloc_dbg (uArrayFinalise, 
                                   handle,
                                   sizeof (struct ArrayStruct),
                                   dbgPos(hfname, hlineno, __FILE__), __LINE__) ;
#endif
  if (!reportArray)
    { reportArray = (Array)1 ; /* prevents looping */
      reportArray = arrayCreate (512, Array) ;
    }
  if (size <= 0)
    messcrash("negative size %d in uArrayCreate", size) ;
  if (n < 1)
    n = 1 ;
  totalAllocatedMemory += n * size ;
#ifndef MEM_DEBUG
  new->base = messalloc (n*size) ;
#else
  new->base = messalloc_dbg (n*size,dbgPos(hfname, hlineno, __FILE__), __LINE__) ;
#endif
  new->dim = n ;
  new->max = 0 ;
  new->size = size ;
  new->id = ++id ;
  new->magic = ARRAY_MAGIC ;
  totalNumberActive++ ;
  if (reportArray != (Array)1) 
    { if (new->id < 20000)
        array (reportArray, new->id, Array) = new ;
      else
        { Array aa = reportArray ;
          reportArray = (Array)1 ; /* prevents looping */
          arrayDestroy (aa) ;
        }
    }
  return new ;
}
/**************/
int arrayReportMark (void)
{
  return reportArray != (Array)1 ?  
      arrayMax(reportArray) : 0 ;
}
/**************/
void arrayReport (int j)
{ int i ;
  Array a ;
 if (reportArray == (Array)1) 
   { fprintf(stderr,
             "\n\n %d active arrays, %d created, %d kb allocated\n\n ",   
             totalNumberActive,   totalNumberCreated , totalAllocatedMemory/1024) ;
     return ;
   }
   
  fprintf(stderr,"\n\n") ;
   
  i = arrayMax (reportArray) ;
  while (i-- && i > j)
    { a = arr (reportArray, i, Array) ;
      if (arrayExists(a))
        fprintf (stderr, "Array %d  size=%d max=%d\n", i, a->size, a->max) ;
    }
}
/**************/
void arrayStatus (int *nmadep, int *nusedp, int *memAllocp, int *memUsedp)
{ 
  int i ;
  Array a, *ap ;
  *nmadep = totalNumberCreated ; 
  *nusedp = totalNumberActive ;
  *memAllocp = totalAllocatedMemory ;
  *memUsedp = 0 ;
  if (reportArray == (Array)1) 
    return ;
  i = arrayMax(reportArray) ;
  ap = arrp(reportArray, 0, Array) - 1 ;
  while (ap++, i--)
    if (arrayExists (*ap))
      { a = *ap ;
        *memUsedp += a->max * a->size ;
      }
}
/**************/
Array uArrayReCreate (Array a, int n, int size)
{ if (!arrayExists(a))
    return  uArrayCreate(n, size, 0) ;
  if(a->size != size)
    messcrash("Type  missmatch in uArrayRecreate, you should always "
              "call recreate using the same type") ;
  if (n < 1)
    n = 1 ;
  if (a->dim < n || 
      (a->dim - n)*size > (1 << 19) ) /* free if save > 1/2 meg */
    { totalAllocatedMemory -= a->dim * size ;
      messfree (a->base) ;
      a->dim = n ;
      totalAllocatedMemory += a->dim * size ;
      a->base = messalloc (a->dim*size) ;
    }
  memset(a->base,0,(mysize_t)(a->dim*size)) ;
  a->max = 0 ;
  return a ;
}
/**************/
void uArrayDestroy (Array a)
/* Note that the finalisation code attached to the memory does the work, 
   see below */
{
  if (!a) return;
  if (a->magic != ARRAY_MAGIC)
    messcrash ("uArrayDestroy received corrupt array->magic");
  messfree(a);
}
static void uArrayFinalise (void *cp)
{ Array a = (Array)cp;
  totalAllocatedMemory -= a->dim * a->size ;
  if (!finalCleanup) messfree (a->base) ;
  a->magic = 0 ;
  totalNumberActive-- ;
  if (!finalCleanup && reportArray != (Array)1) 
    arr(reportArray, a->id, Array) = 0 ;
}
/******************************/
#ifndef MEM_DEBUG
  void arrayExtend (Array a, int n)
#else
  void arrayExtend_dbg (Array a, int n, const char *hfname,int hlineno) 
#endif
{
  char *new ;
  if (!a || n < a->dim)
    return ;
  totalAllocatedMemory -= a->dim * a->size ;
  if (a->dim*a->size < 1 << 23)  /* 2 megs of keys, or 8 megs of ram */
    a->dim *= 2 ;
  else
    a->dim += 1024 + ((1 << 23) / a->size) ;
  if (n >= a->dim)
    a->dim = n + 1 ;
  totalAllocatedMemory += a->dim * a->size ;
#ifndef MEM_DEBUG
  new = messalloc (a->dim*a->size) ;
#else
  new = messalloc_dbg (a->dim*a->size,dbgPos(hfname, hlineno, __FILE__), __LINE__) ;
#endif
  memcpy (new,a->base,a->size*a->max) ;
  messfree (a->base) ;
  a->base = new ;
}
/***************/
char *uArray (Array a, int i)
{
  if (i < 0)
    messcrash ("referencing array element %d < 0", i) ;
  if (!a)
    messcrash ("uArray called with NULL Array struc");
  if (i >= a->max)
    { if (i >= a->dim)
        arrayExtend (a,i) ;
      a->max = i+1 ;
    }
  return a->base + i*a->size ;
}
/***************/
char *uArrayCheck (Array a, int i)
{
  if (i < 0)
    messcrash ("referencing array element %d < 0", i) ;
  return uArray(a, i) ;
}
/***************/
char *uArrCheck (Array a, int i)
{
  if (i >= a->max || i < 0)
    messcrash ("array index %d out of bounds [0,%d]",
               i, a->max - 1) ;
  return a->base + i*a->size ;
}
/**************/
#ifndef MEM_DEBUG
  Array arrayCopy (Array a)
#else
  Array arrayCopy_dbg(Array a, const char *hfname,int hlineno) 
#endif
{ Array b ;
   
  if (arrayExists (a) && a->size)
    {
#ifndef MEM_DEBUG
      b = uArrayCreate (a->max, a->size, 0) ;
#else
          b = uArrayCreate_dbg (a->max, a->size, 0,
                                dbgPos(hfname, hlineno, __FILE__), __LINE__) ;
#endif
      memcpy(b->base, a->base, a->max * a->size);
      b->max = a->max ;
      return b;
    }
  else
    return 0 ;
}
/**************/
Array arrayTruncatedCopy (Array a, int x1, int x2)
{ Array b = 0 ;
   
  if (x1 < 0 || x2 < x1 || x2 > a->max)
    messcrash 
      ("Bad coordinates x1 = %d, x2 = %d in arrayTruncatedCopy",
       x1, x2) ;
  if (arrayExists (a) && a->size)
    { if (x2 - x1)
        { b = uArrayCreate (x2 - x1, a->size, 0) ;
          b->max = x2 - x1 ;
          memcpy(b->base, a->base + x1, b->max * b->size);
        }
      else
        b = uArrayCreate (10, a->size, 0) ;
    }
  return b;
}
/**************/
void arrayCompress(Array a)
{
  int i, j, k , as ;
  char *x, *y, *ab  ;
   
  if (!a || !a->size || arrayMax(a) < 2 )
    return ;
  ab = a->base ; 
  as = a->size ;
  for (i = 1, j = 0 ; i < arrayMax(a) ; i++)
    { x = ab + i * as ; y = ab + j * as ;
      for (k = a->size ; k-- ;)              
        if (*x++ != *y++) 
          goto different ;
      continue ;
       
    different:
      if (i != ++j)
        { x = ab + i * as ; y = ab + j * as ;
          for (k = a->size ; k-- ;)   
            *y++ = *x++ ;
        }
    }
  arrayMax(a) = j + 1 ;
}
/****************/
/* 31.7.1995 dok408  added arraySortPos() - restricted sorting to tail of array */
void arraySort(Array a, int (*order)(void*, void*)) { arraySortPos(a, 0, order) ; }
void arraySortPos (Array a, int pos, int (*order)(void*, void*))
{
  typedef int (*CONSTORDER)(const void*, const void*) ;
  unsigned int n = a->max - pos, s = a->size ;
  void *v = a->base + pos * a->size ;
  
  if (pos < 0) messcrash("arraySortPos: pos = %d", pos);
  if (n > 1) 
#if defined(THINK_C) || defined(metrowerks) /* THINK C & Metrowerks quicksorts suck */
    { extern void qcksrt (char *base, int n, int size, 
                          int (*comp)(void*, void*)) ;
      qcksrt (v, n, s, order) ;
    }
#else
    qsort(v, n, s, (CONSTORDER)order) ;
#endif
}
/***********************************************************/
BOOL arrayIsEntry (Array a, int i, void *s)
{
  char *cp = uArray(a,i), *cq = s ;
  int j = a->size;
  while (j--)
    if (*cp++ != *cq++) 
      return FALSE ;
  return TRUE;
}
/***********************************************/
       /* Finds Entry s from Array  a
        * sorted in ascending order of order()
        * If found, returns TRUE and sets *ip
        * if not, returns FALSE and sets *ip one step left
        */
BOOL arrayFind(Array a, void *s, int *ip, int (* order)(void*, void*))
{
  int ord;
  int i = 0 , j = arrayMax(a), k;
  if(!j || (ord = order(s,uArray(a,0)))<0)
    { if (ip)
        *ip = -1; 
      return FALSE;
    }   /* not found */
  if (ord == 0)
    { if (ip)
        *ip = 0;
      return TRUE;
    }
  if ((ord = order(s,uArray(a,--j)))>0 )
    { if (ip)
        *ip = j; 
      return FALSE;
    }
   
  if (ord == 0)
    { if (ip)
        *ip = j;
      return TRUE;
    }
  while(TRUE)
    { k = i + ((j-i) >> 1) ; /* midpoint */
      if ((ord = order(s, uArray(a,k))) == 0)
        { if (ip)
            *ip = k; 
          return TRUE;
        }
      if (ord > 0) 
        (i = k);
      else
        (j = k) ;
      if (i == (j-1) )
        break;
    }
  if (ip)
    *ip = i ;
  return FALSE;
}
/**************************************************************/
       /* Removes Entry s from Array  a
        * sorted in ascending order of order()
        */
BOOL arrayRemove (Array a, void * s, int (* order)(void*, void*))
{
  int i;
  if (arrayFind(a, s, &i,order))
    {
      /* memcpy would be faster but regions overlap
       * and memcpy is said to fail with some compilers
       */
      char *cp = uArray(a,i),  *cq = cp + a->size ;
      int j = (arrayMax(a) - i)*(a->size) ;
      while(j--)
        *cp++ = *cq++;
      arrayMax(a) --;
      return TRUE;
    }
  else
    return FALSE;
}
/**************************************************************/
       /* Insert Segment s in Array  a
        * in ascending order of s.begin
        */
BOOL arrayInsert(Array a, void * s, int (*order)(void*, void*))
{
  int i, j;
  if (arrayFind(a, s, &i,order))
    return FALSE;  /* no doubles */
   
  j = arrayMax(a) + 1;
  uArray(a,j-1) ; /* to create space */
        /* avoid memcpy for same reasons as above */
  {
    char* cp = uArray(a,j - 1) + a->size - 1,  *cq = cp - a->size ;
    int k = (j - i - 1)*(a->size);
    while(k--)
      *cp-- = *cq--;
     
    cp = uArray(a,i+1); cq = (char *) s; k = a->size;
    while(k--)
      *cp++ = *cq++;
  }
  return TRUE;
}
/********* Stack : arbitrary Stack class - inherits from Array **********/
static void uStackFinalise (void *cp) ;
#ifndef MEM_DEBUG
Stack stackHandleCreate (int n, STORE_HANDLE handle)  /* n is initial size */
{
  Stack s = (Stack) handleAlloc (uStackFinalise, 
                                 handle,
                                 sizeof (struct StackStruct)) ;
#else
Stack stackHandleCreate_dbg (int n, STORE_HANDLE handle,  /* n is initial size */
                                              const char *hfname, int hlineno)
{
  Stack s = (Stack) handleAlloc_dbg (uStackFinalise, 
                                 handle,
                                 sizeof (struct StackStruct),
                                 hfname, hlineno) ;
#endif
  s->magic = STACK_MAGIC ;
  s->a = arrayCreate (n,char) ;
  s->pos = s->ptr = s->a->base ;
  s->safe = s->a->base + s->a->dim - 16 ; /* safe to store objs up to size 8 */
  s->textOnly = FALSE;
  return s ;
}
void stackTextOnly(Stack s)
{ if (!stackExists(s))
    messcrash("StackTextOnly given non-exisant stack.");
  s->textOnly = TRUE;
}
Stack stackReCreate (Stack s, int n)               /* n is initial size */
{
  if (!stackExists(s))
    return stackCreate(n) ;
  s->a = arrayReCreate (s->a,n,char) ;
  s->pos = s->ptr = s->a->base ;
  s->safe = s->a->base + s->a->dim - 16 ; /* safe to store objs up to size 8 */
  return s ;
}
Stack stackCopy (Stack s, STORE_HANDLE handle)
{
  Stack new ;
  if (!stackExists(s))
    return 0 ;
  new = (Stack) handleAlloc (uStackFinalise, handle,
                             sizeof (struct StackStruct)) ;
  *new = *s ;
  new->a = arrayCopy (s->a) ;
  return new ;
}
Stack arrayToStack (Array a)
{ 
  Stack s ;
  int n ;
  if (!arrayExists(a) || a->size != 1 )
    return 0 ;
     
  n = arrayMax(a) ;
  s = stackCreate(n  + 32) ;
               
  memcpy(s->a->base, a->base, n) ;
                 
  s->pos = s->a->base ;
  s->ptr = s->a->base + n ;
  s->safe = s->a->base + s->a->dim - 16 ; /* safe to store objs up to size 8 */
  while ((long)s->ptr % STACK_ALIGNMENT)
    *(s->ptr)++ = 0 ;   
  return s ;
}
void uStackDestroy(Stack s)
{ if (s && s->magic == STACK_MAGIC) messfree(s);
} /* the rest is done below as a consequence */
static void uStackFinalise (void *cp)
{ Stack s = (Stack)cp;
  if (!finalCleanup) arrayDestroy (s->a) ;
  s->magic = 0 ;
}
void stackExtend (Stack s, int n)
{
  int ptr = s->ptr - s->a->base,
      pos = s->pos - s->a->base ;
  s->a->max = s->a->dim ;   /* since only up to ->max copied over */
  arrayExtend (s->a,ptr+n+16) ;      /* relies on arrayExtend mechanism */
  s->ptr = s->a->base + ptr ;
  s->pos = s->a->base + pos ;
  s->safe = s->a->base + s->a->dim - 16 ;
}
int stackMark (Stack s)
{ return (s->ptr - s->a->base) ;
}
int stackPos (Stack s)
{ return (s->pos - s->a->base) ;
}
void stackCursor (Stack s, int mark)
{ s->pos = s->a->base + mark ;
}
/* access doubles on the stack by steam on systems where we don't
   align the stack strictly enough, this code assumes that ints are 32bits
   and doubles 64 */
union mangle { double d;
               struct { int i1;
                        int i2;
                      } i;
             };
void ustackDoublePush(Stack stk, double x)
{ union mangle m;
  m.d = x;
  push(stk, m.i.i1, int);
  push(stk, m.i.i2, int);
}
double ustackDoublePop(Stack stk)
{ union mangle m;
  m.i.i2 = pop(stk, int);
  m.i.i1 = pop(stk, int);
  return m.d;
}
double ustackDoubleNext(Stack stk)
{ union mangle m;
  m.i.i1 = stackNext(stk, int);
  m.i.i2 = stackNext(stk, int);
  return m.d;
}
void pushText (Stack s, char* text)
{
  while (s->ptr + strlen(text)  > s->safe) 
    stackExtend (s,strlen(text)+1) ;
  while ((*(s->ptr)++ = *text++)) ;
  if (!s->textOnly)
    while ((long)s->ptr % STACK_ALIGNMENT)
      *(s->ptr)++ = 0 ;   
}
char* popText (Stack s)
{
  char *base = s->a->base ;
  while (s->ptr > base && !*--(s->ptr)) ;
  while (s->ptr >= base && *--(s->ptr)) ;
  return ++(s->ptr) ;
}
void catText (Stack s, char* text)
{
  while (s->ptr + strlen(text) > s->safe)
    stackExtend (s,strlen(text)+1) ;
  *s->ptr = 0 ;
  while (s->ptr >= s->a->base && *s->ptr == 0)
    s->ptr -- ;
  s->ptr ++ ;
  while ((*(s->ptr)++ = *text++)) ;
  if (!s->textOnly)
    while ((long)s->ptr % STACK_ALIGNMENT)
      *(s->ptr)++ = 0 ;   
}
void catBinary (Stack s, char* data, int size)
{
  int total;
  total = size + 1;
  while (s->ptr + total > s->safe)
    stackExtend (s,size+1) ;
  *s->ptr = 0 ;
  while (s->ptr >= s->a->base && *s->ptr == 0)
    s->ptr -- ;
  s->ptr ++ ;
  memcpy(s->ptr,data,size);
  s->ptr += size;
  /* end with a newline to prevent truncation by next cat */
  *(s->ptr)++ = '\n';
  if (!s->textOnly)
    while ((long)s->ptr % STACK_ALIGNMENT)
      *(s->ptr)++ = 0 ;   
}
char* stackNextText (Stack s)
{ char *text = s->pos ;
  if (text>= s->ptr)
    return 0 ;  /* JTM, so while stackNextText makes sense */
  while (*s->pos++) ;
  if (!s->textOnly)
    while ((long)s->pos % STACK_ALIGNMENT)
      ++s->pos ;
  return text ;
}
/*********/
     /* Push text in stack s, after breaking it on delimiters */
     /* You can later access the tokens with command
        while (token = stackNextText(s)) work on your tokens ;
        */
void  stackTokeniseTextOn(Stack s, char *text, char *delimiters)
{
  char *cp, *cq , *cend, *cd, old, oldend ;
  int i, n ;
  if(!stackExists(s) || !text || !delimiters)
    messcrash("stackTextOn received some null parameter") ;
  n = strlen(delimiters) ;
  cp = cq  = text ;
  while(TRUE)
    {
      while(*cp == ' ')
        cp++ ;
      cq = cp ;
      old = 0 ;
      while(*cq)
        { for (cd = delimiters, i = 0 ; i < n ; cd++, i++)
            if (*cd == *cq)
              { old = *cq ;
                *cq = 0 ;
                goto found ;
              }
          cq++ ;
        }
    found:
      cend = cq ;
      while(cend > cp && *--cend == ' ') ;
      if (*cend != ' ') cend++ ;
      oldend = *cend ; *cend = 0 ;
      if (*cp && cend > cp)
        pushText(s,cp) ;
      *cend = oldend ;
      if(!old)
        { stackCursor(s, 0) ;
          return ;
        }
      *cq = old ;
      cp = cq + 1 ;
    }
}
void stackClear(Stack s)
{ if (stackExists(s))
    { s->pos = s->ptr = s->a->base;
      s->a->max = 0;
    }
}
/****************** routines to set text into lines ***********************/
static char *linesText ;
static Array lines ;
static Array textcopy ;
static int kLine, popLine ;
/**********/
int uLinesText (char *text, int width)
{
  char *cp,*bp ;
  int i ;
  int nlines = 0 ;
  int length = strlen (text) ;
  int safe = length + 2*(length/(width > 0 ? width : 1) + 1) ; /* mieg: avoid zero divide */
  static int isFirst = TRUE ;
  if (isFirst)
    { isFirst = FALSE ;
      lines = arrayCreate(16,char*) ;
      textcopy = arrayCreate(128,char) ;
    }
  linesText = text ;
  array(textcopy,safe,char) = 0 ;   /* ensures textcopy is long enough */
  if (!*text)
    { nlines = popLine = kLine = 0 ;
      array(lines,0,char*) = 0 ;
      return 0 ;
    }
  cp = textcopy->base ;
  nlines = 0 ;
  for (bp = text ; *bp ; ++bp)
    { array(lines,nlines++,char*) = cp ;
      for (i = 0 ; (*cp = *bp) && *cp != '\n' ; ++i, ++cp, ++bp)
        if (i == width)         /* back up to last space */
          { while (i--)
              { --bp ; --cp ;
                if (*cp == ' ' || *cp == ',' || *cp == ';')
                  goto eol ;
              }
            cp += width ;       /* no coma or spaces in whole line ! */
            bp += width ;
            break ;
          }
eol:  if (!*cp)
        break ;
      if (*cp != '\n')
        ++cp ;
      *cp++ = 0 ;
    }
  kLine = 0 ;                   /* reset for uNextLine() */
  popLine = nlines ;
  array(lines,nlines,char*) = 0 ; /* 0 terminate */
  return nlines ;
 }
char *uNextLine (char *text)
 {
   if (text != linesText)
     messout ("Warning : uNextLine being called with bad context") ;
   return array(lines,kLine++,char*) ;
 }
char *uPopLine (char *text)
 {
   if (text != linesText)
     messout ("Warning : uPopLine being called with bad context") ;
   if (popLine)
     return array(lines,--popLine,char*) ;
   else return 0;
 }
char **uBrokenLines (char *text, int width)
{
  uLinesText (text,width) ;
  return (char**)lines->base ;
}
char *uBrokenText (char *text, int width)
{
  char *cp ;
  uLinesText (text,width) ;
  uNextLine (text) ;
  while ((cp = uNextLine (text)))
    *(cp-1) = '\n' ;
  return arrp(textcopy,0,char) ;
}
/*************************************************************/
/* perfmeters */
int assBounce = 0, assFound = 0, assNotFound = 0, assInserted = 0, assRemoved = 0 ;
/* Associator package is for associating pairs of pointers. 
   Assumes that an "in" item is non-zero and non -1.
   Implemented as a hash table of size 2^m.  
    
   Originally grabbed from Steve Om's sather code by Richard Durbin.
   Entirelly rewritten by mieg, using bouncing by relative primes
   and deletion flagging.
   User has access to structure member ->n = # of pairs
*/
#define VSIZE (sizeof(void*))
#define VS5 (VSIZE/5)
#define VS7 (VSIZE/7)
#define moins_un ((void*) (-1))
#define HASH(_xin) { register long z = VS5, x = (char*)(_xin) - (char*)0 ; \
                  for (hash = x, x >>= 5 ; z-- ; x >>= 5) hash ^= x ; \
                  hash &= a->mask ; \
                }
#define DELTA(_xin)   { register long z = VS7, x = (char*)(_xin) - (char*)0 ; \
                       for (delta = x, x >>= 7 ; z-- ; x >>= 7) delta ^= x ; \
                       delta = (delta & a->mask) | 0x01 ; \
                   }  /* delta odd is prime relative to  2^m */
/**************** Destruction ****************************/
static void assFinalise(void *cp)
{ Associator a = (Associator)cp;
  a->magic = 0 ;
  if (!finalCleanup)
    { messfree(a->in) ;
      messfree(a->out);
    }
}
void uAssDestroy (Associator a)
{ if (assExists(a))
    messfree (a) ;  /* calls assFinalise */
}
/**************** Creation *******************************/
#ifndef MEM_DEBUG
  static Associator assDoCreate (int nbits, STORE_HANDLE handle)
#else
  static Associator assDoCreate (int nbits, STORE_HANDLE handle,
                                 const char *hfname, int hlineno)
#endif
{ static int nAss = 0 ;
  Associator a ;
  int size = 1 << nbits,  /* size must be a power of 2 */
      vsize = size * VSIZE ; 
#ifndef MEM_DEBUG
  a = (Associator) handleAlloc(assFinalise, 
                               handle, 
                               sizeof (struct AssStruct)) ;
  a->in = (void**) messalloc (vsize) ;
  a->out = (void**) messalloc (vsize) ;
#else
  a = (Associator) handleAlloc_dbg(assFinalise, 
                               handle, 
                               sizeof (struct AssStruct),
                                   dbgPos(hfname, hlineno, __FILE__), __LINE__) ;
  a->in = (void**) messalloc_dbg(vsize,dbgPos(hfname, hlineno, __FILE__), __LINE__) ;
  a->out = (void**) messalloc_dbg(vsize,dbgPos(hfname, hlineno, __FILE__), __LINE__) ;
#endif
  a->magic = ASS_MAGIC ;
  a->id = ++nAss ;
  a->n = 0 ;
  a->i = 0 ; /* start up position for recursive calls */
  a->m = nbits ;
  a->mask = size - 1 ;
  return a ;
}
/*******************/
#ifndef MEM_DEBUG
  Associator assBigCreate (int size)
#else
  Associator assBigCreate_dbg(int size, const char *hfname, int hlineno)
#endif
{
  int n = 2 ; /* make room, be twice as big as needed */
  if (size <= 0) 
    messcrash ("assBigCreate called with size = %d <= 0", size) ;
  --size ;
  while (size >>= 1) n++ ; /* number of left most bit + 1 */
#ifndef MEM_DEBUG
  return assDoCreate(n, 0) ;
#else
  return assDoCreate(n, 0, hfname, hlineno) ;
#endif
}
/*******************/
#ifndef MEM_DEBUG
  Associator assHandleCreate(STORE_HANDLE handle) { return assDoCreate(5, handle) ;}
#else
  Associator assHandleCreate_dbg(STORE_HANDLE handle, const char *hfname,int hlineno)
  { return assDoCreate(5, handle, dbgPos(hfname, hlineno, __FILE__), __LINE__) ; }
#endif
/*******************/
void assClear (Associator a)
{ mysize_t sz ;
  if (!assExists(a)) 
    return ;
   
  a->n = 0 ;
  sz = ( 1 << a->m) *  VSIZE ;
  memset(a->in, 0, sz) ;
  memset(a->out, 0, sz) ;
}
/********************/
Associator assReCreate (Associator a)
{ if (!assExists(a))
    return assCreate() ;
  else
    { assClear (a) ;  return a ; }
}
/********************/
static void assDouble (Associator a)
{ int oldsize, newsize, nbits ;
  register int hash, delta ;
  void **old_in = a->in, **old_out = a->out, **xin, **xout ;
  int i ;
  nbits = a->m ;
  oldsize = 1 << nbits ;
  newsize = oldsize << 1 ; /* size must be a power of 2 */
  a->n = 0 ;
  a->i = 0 ; /* start up position for recursive calls */
  a->m = nbits + 1 ;
  a->mask = newsize - 1 ;
  a->in  = (void**) messalloc (newsize * VSIZE) ;
  a->out = (void**) messalloc (newsize * VSIZE) ;
  for (i = 0, xin = old_in, xout = old_out ; i < oldsize ; i++, xin++, xout++)
    if (*xin && *xin != moins_un)
      { HASH(*xin) ;
        while (TRUE)
          { if (!a->in[hash])  /* don't need to test moins_un */
              { a->in[hash] = *xin ;
                a->out[hash] = *xout ;
                ++a->n ;
                assInserted++ ;
                break ;
              }
            assBounce++ ;
            DELTA(*xin) ;       /* redo each time - cheap overall */
            hash = (hash + delta) & a->mask ;
          }
      }
  messfree (old_in) ;
  messfree (old_out) ;
}
/************************ Searches  ************************************/
BOOL uAssFind (Associator a, void* xin, void** pout)
/* if found, updates *pout and returns TRUE, else returns FALSE */
{ int hash, delta = 0 ;
  void* test ;
  if (!assExists(a))
    messcrash ("assFind received corrupted associator") ;
  if (!xin || xin == moins_un) return FALSE ;
  HASH(xin) ;
  while (TRUE)
    { test = a->in[hash] ;
      if (test == xin)
        { if (pout)
            *pout = a->out[hash] ;
          assFound++ ;
          a->i = hash ;
          return TRUE ;
        }
      if (!test)
        break ;
      assBounce++ ;
      if (!delta) DELTA(xin) ;
      hash = (hash + delta) & a->mask ;
    }
  assNotFound++ ;
  return FALSE ;
}
/********************/
  /* Usage: if(uAssFind()){while (uAssFindNext()) ... } */
BOOL uAssFindNext (Associator a, void* xin, void** pout)
/* if found, updates *pout and returns TRUE, else returns FALSE */
{ int   hash, delta ;
  void* test ;
  if (!assExists(a))
    messcrash ("assFindNext received corrupted associator") ;
  if (!xin || xin == moins_un || !a->in[a->i]) 
    return FALSE ;
  if (a->in[a->i] != xin)
    messcrash ("Non consecutive call to assFindNext") ;
  hash = a->i ;
  DELTA(xin) ;
  while (TRUE)
    { test = a->in[hash] ;
      if (test == xin)
        { if (pout)
            *pout = a->out[hash] ;
          while (TRUE) /* locate on next entry */
            { hash = (hash + delta) & a->mask ; 
              test = a->in[hash] ;
              if (!test || test == xin)
                break ;
              assBounce++ ;
            }
          a->i = hash ; /* points to next entry or zero */
          assFound++ ;
          return TRUE ;
        }
      if (!test)
        break ;
      assBounce++ ;
      hash = (hash + delta) & a->mask ;
    }
  assNotFound++ ;
  return FALSE ;
}
/************************ Insertions  ************************************/
     /* if already there returns FALSE, else inserts and returns TRUE */
static BOOL assDoInsert (Associator a, void* xin, void* xout, BOOL noMultiples)
{ int   hash, delta = 0 ;
  void* test ;
  if (!assExists(a))
    messcrash ("assInsert received corrupted associator") ;
  if (!xin || xin == moins_un) 
    messcrash ("assInsert received forbidden value xin == 0") ;
  if (a->n >= (1 << (a->m - 1))) /* reaching floating line */
    assDouble (a) ;
  HASH (xin) ;
  
  while (TRUE)
    { test = a->in[hash] ;
      if (!test || test == moins_un)  /* reuse deleted slots */
        { a->in[hash] = xin ;
          a->out[hash] = xout ;
          ++a->n ;
          assInserted++ ;
          return TRUE ;
        }
      if (noMultiples && test == xin)           /* already there */
        return FALSE ;
      assBounce++ ;
      if (!delta) DELTA (xin) ;
      hash = (hash + delta) & a->mask ;
    }
}
/*****************/
     /* This one does not allow multiple entries in one key. */
BOOL assInsert (Associator a, void* xin, void* xout)
{ return assDoInsert (a, xin, xout, TRUE) ;
}
  
/*****************/
void assMultipleInsert (Associator a, void* xin, void* xout)
     /* This one allows multiple entries in one key. */
{ assDoInsert (a, xin, xout, FALSE) ;
}
  
/************************ Removals ************************************/
   /* if found, removes entry and returns TRUE, else returns FALSE      */
   /* No a->n--, because the entry is blanked but not actually removed */
BOOL assRemove (Associator a, void* xin)
{ if (assExists(a) && uAssFind (a, xin, 0))
    { a->in[a->i] = moins_un ;
      assRemoved++ ;
      return TRUE ;
    }
  else
    return FALSE ;
}
/*******************/
/* if found, removes entry and returns TRUE, else returns FALSE */
/* Requires both xin and xout to match */
BOOL assPairRemove (Associator a, void* xin, void* xout)
{ if (!assExists(a) || !xin || xin == moins_un) return FALSE ;
  if (uAssFind (a, xin, 0))
    while (uAssFindNext (a, xin, 0))
      if (a->out[a->i] == xout)
        { a->in[a->i] = moins_un ;
          assRemoved++ ;
          return TRUE ;
        }
  return FALSE ;
}
/************************ dumpers ********************************/
     /* lets you step through all members of the table */
BOOL uAssNext (Associator a, void* *pin, void* *pout)
{ int size ;
  void *test ;
  if (!assExists(a))
     messcrash("uAssNext received a non existing associator") ;
  size = 1 << a->m ;
  if (!*pin)
    a->i = -1 ;
  else if (*pin != a->in[a->i])
    { messerror ("Non-consecutive call to assNext()") ;
      return FALSE ;
    }
  while (++a->i < size)
    { test = a->in[a->i] ;
      if (test && test != moins_un) /* not empty or deleted */
        { *pin = a->in[a->i] ;
          if (pout)
            *pout = a->out[a->i] ;
          return TRUE ;
        }
    }
  return FALSE ;
}
/*******************/
void assDump (Associator a)
{ int i ; 
  void **in, **out ;
  char *cp0 = 0 ;
  if (!assExists(a)) return ;
  i = 1 << a->m ;
  in = a->in - 1 ; out = a->out - 1 ;
      /* keep stderr here since it is for debugging */
  fprintf (stderr,"Associator %lx : %d pairs\n",(unsigned long)a,a->n) ;
  while (in++, out++, i--)
    if (*in && *in != moins_un) /* not empty or deleted */
      fprintf (stderr,"%lx - %lx\n",
               (long)((char*)(*in) - cp0),(long)( (char *)(*out) - cp0)) ;
}
/************************  end of file ********************************/
/**********************************************************************/