bag.c   [plain text]

/*  bag.c -- ARMulator support code:  ARM6 Instruction Emulator.
    Copyright (C) 1994 Advanced RISC Machines Ltd.
 
    This program 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 2 of the License, or
    (at your option) any later version.
 
    This program 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 this program; if not, write to the Free Software
    Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */

/********************************************************************/
/* bag.c:                                                           */
/* Offers a data structure for storing and getting pairs of number. */
/* The numbers are stored together, put one can be looked up by     */
/* quoting the other.  If a new pair is entered and one of the      */
/* numbers is a repeat of a previous pair, then the previos pair    */
/* is deleted.                                                      */
/********************************************************************/

#include "bag.h"
#include <stdlib.h>

#define HASH_TABLE_SIZE 256
#define hash(x) (((x)&0xff)^(((x)>>8)&0xff)^(((x)>>16)&0xff)^(((x)>>24)&0xff))

typedef struct hashentry
{
  struct hashentry *next;
  int first;
  int second;
}
Hashentry;

Hashentry *lookupbyfirst[HASH_TABLE_SIZE];
Hashentry *lookupbysecond[HASH_TABLE_SIZE];

void
addtolist (Hashentry ** add, long first, long second)
{
  while (*add)
    add = &((*add)->next);
  /* Malloc will never fail? :o( */
  (*add) = (Hashentry *) malloc (sizeof (Hashentry));
  (*add)->next = (Hashentry *) 0;
  (*add)->first = first;
  (*add)->second = second;
}

void
killwholelist (Hashentry * p)
{
  Hashentry *q;

  while (p)
    {
      q = p;
      p = p->next;
      free (q);
    }
}

static void
removefromlist (Hashentry ** p, long first)
{
  Hashentry *q;

  while (*p)
    {
      if ((*p)->first == first)
	{
	  q = (*p)->next;
	  free (*p);
	  *p = q;
	  return;
	}
      p = &((*p)->next);
    }
}

void
BAG_putpair (long first, long second)
{
  long junk;

  if (BAG_getfirst (&junk, second) != NO_SUCH_PAIR)
    BAG_killpair_bysecond (second);
  addtolist (&lookupbyfirst[hash (first)], first, second);
  addtolist (&lookupbysecond[hash (second)], first, second);
}

Bag_error
BAG_getfirst (long *first, long second)
{
  Hashentry *look;

  look = lookupbysecond[hash (second)];
  while (look)
    if (look->second == second)
      {
	*first = look->first;
	return NO_ERROR;
      }
  return NO_SUCH_PAIR;
}

Bag_error
BAG_getsecond (long first, long *second)
{
  Hashentry *look;

  look = lookupbyfirst[hash (first)];
  while (look)
    {
      if (look->first == first)
	{
	  *second = look->second;
	  return NO_ERROR;
	}
      look = look->next;
    }
  return NO_SUCH_PAIR;
}

Bag_error
BAG_killpair_byfirst (long first)
{
  long second;

  if (BAG_getsecond (first, &second) == NO_SUCH_PAIR)
    return NO_SUCH_PAIR;
  removefromlist (&lookupbyfirst[hash (first)], first);
  removefromlist (&lookupbysecond[hash (second)], first);
  return NO_ERROR;
}

Bag_error
BAG_killpair_bysecond (long second)
{
  long first;

  if (BAG_getfirst (&first, second) == NO_SUCH_PAIR)
    return NO_SUCH_PAIR;
  removefromlist (&lookupbyfirst[hash (first)], first);
  removefromlist (&lookupbysecond[hash (second)], first);
  return NO_ERROR;
}

void
BAG_newbag ()
{
  int i;

  for (i = 0; i < 256; i++)
    {
      killwholelist (lookupbyfirst[i]);
      killwholelist (lookupbysecond[i]);
      lookupbyfirst[i] = lookupbysecond[i] = (Hashentry *) 0;
    }
}