/* sparse.c -- Sparse Array Operations

This file is part of STAR, the Saturn Macro Assembler.

   STAR is not distributed by the Free Software Foundation. Do not ask
them for a copy or how to obtain new releases. Instead, send e-mail to
the address below. STAR is merely covered by the GNU General Public
License.

Please send your comments, ideas, and bug reports to
Jan Brittenson <bson@ai.mit.edu>

*/


/* Copyright (C) 1988-1991 Jan Brittenson

   STAR is free software; you can redistribute it and/or modify it
under the terms of the GNU General Public License as published by the
Free Software Foundation; either version 1, or (at your option) any
later version.

   STAR is distributed in the hope that it will be useful, but WITHOUT
ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
for more details.

   You should have received a copy of the GNU General Public License
along with STAR; see the file COPYING. If not, to obtain a copy, write
to the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139,
USA, or send e-mail to bson@ai.mit.edu. */


#include <stdio.h>
#include "star.h"
#include "sparse.h"


extern char
  *malloc();


/* Allocate virgin sparse node */
static SPR_NODE *spr_alloc(spr_root)
  SPR_ROOT *spr_root;
{
  register SPR_NODE *spr_tmp;

  if(!spr_root || !spr_root->spr_create ||
     !(spr_tmp = (*spr_root->spr_create)
       (sizeof(SPR_NODE) +
	sizeof(SPR_NODE *) * spr_root->spr_mask /* + 1 - 1 */ )))

    fatal("Can't allocate SPR node");
  
  spr_root->spr_inuse++;

  bclear(spr_tmp, sizeof(SPR_NODE) +
	 sizeof(SPR_NODE *) * spr_root->spr_mask);

  return(spr_tmp);
}


/* Destroy sparse node without questions */
static void spr_free(spr_root, spr_node)
  SPR_ROOT *spr_root;
  SPR_NODE *spr_node;
{
  /* Free data */
  (*spr_root->spr_destr)(spr_node);
  
  spr_root->spr_inuse--;
}


/* Create sparse root */
SPR_ROOT *spr_open(mem_alloc, mem_free, id, nfields, nbits)
  SPR_NODE *(*mem_alloc)();
  void (*mem_free)();
  char *id;
  int nfields, nbits;
{
  register SPR_ROOT *spr_r_tmp;
  extern char *malloc();
  extern void free();
  

  if(!mem_alloc)
    mem_alloc = (SPR_NODE *(*)()) malloc;

  if(!(spr_r_tmp = (SPR_ROOT *) (*mem_alloc)(sizeof(SPR_ROOT))))
    fatal("Can't allocate SPR root");

  spr_r_tmp->spr_id     = id;

  spr_r_tmp->spr_nodd   = nfields;
  spr_r_tmp->spr_shfc   = nbits;
  spr_r_tmp->spr_mask   = (1 << nbits) - 1;

  spr_r_tmp->spr_create = mem_alloc;
  spr_r_tmp->spr_destr  = (mem_free ? mem_free : free);
  spr_r_tmp->spr_top    = (SPR_NODE *) 0;

  return(spr_r_tmp);
}


/* Destroy sparse array.
 * The function spr_handle() - if not NULL - will be applied
 * in ascending order to each consequtive value still bound.
 */
static void close_aux(root, node, to_go, spr_handle)
  SPR_ROOT *root;
  SPR_NODE *node;
  short to_go;
  void (*spr_handle)();
{
  SPR_NODE **spr_node_i;

  if(to_go)
    {
      to_go--;
      for(spr_node_i = node->spr_link;
	  spr_node_i < &node->spr_link[ root->spr_mask+1 ];
	  spr_node_i++)
	
	if(*spr_node_i)
	  close_aux(root, *spr_node_i, to_go);
    }
  else
    if(spr_handle)
      for(spr_node_i = node->spr_link;
	  spr_node_i < &node->spr_link[ root->spr_mask-1 ];
	  spr_node_i++)

	if(*spr_node_i)
	  (*spr_handle)(root, *spr_node_i);
	  
  spr_free(root, node);
}

void spr_close(spr_root, spr_handle)
  SPR_ROOT *spr_root;
  void (*spr_handle)();
{
  if(!spr_root)
    return;

  close_aux(spr_root, spr_root->spr_top, spr_root->spr_nodd-1, spr_handle);
  (*spr_root->spr_destr)(spr_root);
}


/* Unbind value.
 * This is pretty straightforward, we simply loop and
 * traverse the hierarchy.
 */
void spr_bind(spr_root, spr_index, spr_val)
  SPR_ROOT *spr_root;
  unsigned long spr_index;
  char *spr_val;
{
  register SPR_NODE *spr_node, **spr_v;
  register level;

  if(!spr_root)
    return;

  if(!(spr_node = spr_root->spr_top))
    spr_node = spr_root->spr_top = spr_alloc(spr_root);

  /* Loop and traverse */
  for(level = spr_root->spr_nodd-1; level > 0; level--)
    if(!*(spr_v = &spr_node->spr_link [ SPR_I2X(spr_root, spr_index, level) ]))
      *spr_v = spr_node = spr_alloc(spr_root);
    else
      spr_node = *spr_v;

  spr_v = &spr_node->spr_link[ SPR_I2X(spr_root, spr_index, 0) ];

  if(!*spr_v)
    spr_node->spr_inuse++;

  *spr_v = (SPR_NODE *) spr_val;
}


/* Return value.
 */
char *spr_get(spr_root, spr_index)
  SPR_ROOT *spr_root;
  unsigned long spr_index;
{
  register SPR_NODE *spr_node, **spr_v;
  register level;

  if(!spr_root)
    return(NULL);

  if(!(spr_node = spr_root->spr_top))
    spr_node = spr_root->spr_top = spr_alloc(spr_root);

  /* Loop and traverse */
  for(level = spr_root->spr_nodd-1; level > 0; level--)
    if(!*(spr_v = &spr_node->spr_link[ SPR_I2X(spr_root, spr_index, level) ]))
      return(NULL);
    else
      spr_node = *spr_v;

  return((char *) spr_node->spr_link[ SPR_I2X(spr_root, spr_index, 0) ]);
}


/* Unbind value.
 *
 * Pretty straightforward, although we take care to free
 * entirely unused nodes. To accomplish this we first locate
 * the target node using a recursive depth-first traversal,
 * unbinding the value, and then as we return free unused
 * nodes.
 *
 * Returns TRUE if a link was unbound.
 */
static unbind_aux(root, node_v, to_go, index)
  SPR_ROOT *root;
  SPR_NODE **node_v;
  short to_go;
  unsigned long index;
{
  /* First traverse */
  if(to_go)
    if(!*node_v)
      return(FALSE);
    else
      {
	if(unbind_aux(root, &(*node_v)->spr_link
		      [ SPR_I2X(root, index, to_go) ],
		      to_go - 1, index))
	  {
	    /* Something got unlinked - anything left? */
	    if(--(*node_v)->spr_inuse)
	      return(FALSE);	/* Yes. */

	    /* No, free. */
	    spr_free(root, *node_v);
	    *node_v = (SPR_NODE *) 0;
	    return(TRUE);
	  }
	return(FALSE);
      }

  /* This is the value link, unbind it */
  if(!*node_v)
    return(FALSE);
  
  *node_v = (SPR_NODE *) 0;
  return(TRUE);
}


void spr_unbind(root, index)
  SPR_ROOT *root;
  unsigned long index;
{
  if(!root)
    return;

  if(unbind_aux(root, &root->spr_top, root->spr_nodd-1, index))
    {
      root->spr_top = (SPR_NODE *) 0;
      root->spr_inuse--;
    }
}
