Subversion Repositories openrisc_2011-10-31

/*  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., 51 Franklin Street - Fifth Floor, Boston, MA 02110-1301, 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;

    }

}