view release on metacpan or  search on metacpan

acelib/arraysub.c  view on Meta::CPAN

          { 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 ********************************/
/**********************************************************************/