/* bag.c -- ARMulator support code: ARM6 Instruction Emulator.
|
/* bag.c -- ARMulator support code: ARM6 Instruction Emulator.
|
Copyright (C) 1994 Advanced RISC Machines Ltd.
|
Copyright (C) 1994 Advanced RISC Machines Ltd.
|
|
|
This program is free software; you can redistribute it and/or modify
|
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
|
it under the terms of the GNU General Public License as published by
|
the Free Software Foundation; either version 2 of the License, or
|
the Free Software Foundation; either version 2 of the License, or
|
(at your option) any later version.
|
(at your option) any later version.
|
|
|
This program is distributed in the hope that it will be useful,
|
This program is distributed in the hope that it will be useful,
|
but WITHOUT ANY WARRANTY; without even the implied warranty of
|
but WITHOUT ANY WARRANTY; without even the implied warranty of
|
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
GNU General Public License for more details.
|
GNU General Public License for more details.
|
|
|
You should have received a copy of the GNU General Public License
|
You should have received a copy of the GNU General Public License
|
along with this program; if not, write to the Free Software
|
along with this program; if not, write to the Free Software
|
Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston, MA 02110-1301, USA. */
|
Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston, MA 02110-1301, USA. */
|
|
|
/********************************************************************/
|
/********************************************************************/
|
/* bag.c: */
|
/* bag.c: */
|
/* Offers a data structure for storing and getting pairs of number. */
|
/* Offers a data structure for storing and getting pairs of number. */
|
/* The numbers are stored together, put one can be looked up by */
|
/* 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 */
|
/* 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 */
|
/* numbers is a repeat of a previous pair, then the previos pair */
|
/* is deleted. */
|
/* is deleted. */
|
/********************************************************************/
|
/********************************************************************/
|
|
|
#include "bag.h"
|
#include "bag.h"
|
#include <stdlib.h>
|
#include <stdlib.h>
|
|
|
#define HASH_TABLE_SIZE 256
|
#define HASH_TABLE_SIZE 256
|
#define hash(x) (((x)&0xff)^(((x)>>8)&0xff)^(((x)>>16)&0xff)^(((x)>>24)&0xff))
|
#define hash(x) (((x)&0xff)^(((x)>>8)&0xff)^(((x)>>16)&0xff)^(((x)>>24)&0xff))
|
|
|
typedef struct hashentry
|
typedef struct hashentry
|
{
|
{
|
struct hashentry *next;
|
struct hashentry *next;
|
int first;
|
int first;
|
int second;
|
int second;
|
}
|
}
|
Hashentry;
|
Hashentry;
|
|
|
Hashentry *lookupbyfirst[HASH_TABLE_SIZE];
|
Hashentry *lookupbyfirst[HASH_TABLE_SIZE];
|
Hashentry *lookupbysecond[HASH_TABLE_SIZE];
|
Hashentry *lookupbysecond[HASH_TABLE_SIZE];
|
|
|
void
|
void
|
addtolist (Hashentry ** add, long first, long second)
|
addtolist (Hashentry ** add, long first, long second)
|
{
|
{
|
while (*add)
|
while (*add)
|
add = &((*add)->next);
|
add = &((*add)->next);
|
/* Malloc will never fail? :o( */
|
/* Malloc will never fail? :o( */
|
(*add) = (Hashentry *) malloc (sizeof (Hashentry));
|
(*add) = (Hashentry *) malloc (sizeof (Hashentry));
|
(*add)->next = (Hashentry *) 0;
|
(*add)->next = (Hashentry *) 0;
|
(*add)->first = first;
|
(*add)->first = first;
|
(*add)->second = second;
|
(*add)->second = second;
|
}
|
}
|
|
|
void
|
void
|
killwholelist (Hashentry * p)
|
killwholelist (Hashentry * p)
|
{
|
{
|
Hashentry *q;
|
Hashentry *q;
|
|
|
while (p)
|
while (p)
|
{
|
{
|
q = p;
|
q = p;
|
p = p->next;
|
p = p->next;
|
free (q);
|
free (q);
|
}
|
}
|
}
|
}
|
|
|
static void
|
static void
|
removefromlist (Hashentry ** p, long first)
|
removefromlist (Hashentry ** p, long first)
|
{
|
{
|
Hashentry *q;
|
Hashentry *q;
|
|
|
while (*p)
|
while (*p)
|
{
|
{
|
if ((*p)->first == first)
|
if ((*p)->first == first)
|
{
|
{
|
q = (*p)->next;
|
q = (*p)->next;
|
free (*p);
|
free (*p);
|
*p = q;
|
*p = q;
|
return;
|
return;
|
}
|
}
|
p = &((*p)->next);
|
p = &((*p)->next);
|
}
|
}
|
}
|
}
|
|
|
void
|
void
|
BAG_putpair (long first, long second)
|
BAG_putpair (long first, long second)
|
{
|
{
|
long junk;
|
long junk;
|
|
|
if (BAG_getfirst (&junk, second) != NO_SUCH_PAIR)
|
if (BAG_getfirst (&junk, second) != NO_SUCH_PAIR)
|
BAG_killpair_bysecond (second);
|
BAG_killpair_bysecond (second);
|
addtolist (&lookupbyfirst[hash (first)], first, second);
|
addtolist (&lookupbyfirst[hash (first)], first, second);
|
addtolist (&lookupbysecond[hash (second)], first, second);
|
addtolist (&lookupbysecond[hash (second)], first, second);
|
}
|
}
|
|
|
Bag_error
|
Bag_error
|
BAG_getfirst (long *first, long second)
|
BAG_getfirst (long *first, long second)
|
{
|
{
|
Hashentry *look;
|
Hashentry *look;
|
|
|
look = lookupbysecond[hash (second)];
|
look = lookupbysecond[hash (second)];
|
while (look)
|
while (look)
|
if (look->second == second)
|
if (look->second == second)
|
{
|
{
|
*first = look->first;
|
*first = look->first;
|
return NO_ERROR;
|
return NO_ERROR;
|
}
|
}
|
return NO_SUCH_PAIR;
|
return NO_SUCH_PAIR;
|
}
|
}
|
|
|
Bag_error
|
Bag_error
|
BAG_getsecond (long first, long *second)
|
BAG_getsecond (long first, long *second)
|
{
|
{
|
Hashentry *look;
|
Hashentry *look;
|
|
|
look = lookupbyfirst[hash (first)];
|
look = lookupbyfirst[hash (first)];
|
while (look)
|
while (look)
|
{
|
{
|
if (look->first == first)
|
if (look->first == first)
|
{
|
{
|
*second = look->second;
|
*second = look->second;
|
return NO_ERROR;
|
return NO_ERROR;
|
}
|
}
|
look = look->next;
|
look = look->next;
|
}
|
}
|
return NO_SUCH_PAIR;
|
return NO_SUCH_PAIR;
|
}
|
}
|
|
|
Bag_error
|
Bag_error
|
BAG_killpair_byfirst (long first)
|
BAG_killpair_byfirst (long first)
|
{
|
{
|
long second;
|
long second;
|
|
|
if (BAG_getsecond (first, &second) == NO_SUCH_PAIR)
|
if (BAG_getsecond (first, &second) == NO_SUCH_PAIR)
|
return NO_SUCH_PAIR;
|
return NO_SUCH_PAIR;
|
removefromlist (&lookupbyfirst[hash (first)], first);
|
removefromlist (&lookupbyfirst[hash (first)], first);
|
removefromlist (&lookupbysecond[hash (second)], first);
|
removefromlist (&lookupbysecond[hash (second)], first);
|
return NO_ERROR;
|
return NO_ERROR;
|
}
|
}
|
|
|
Bag_error
|
Bag_error
|
BAG_killpair_bysecond (long second)
|
BAG_killpair_bysecond (long second)
|
{
|
{
|
long first;
|
long first;
|
|
|
if (BAG_getfirst (&first, second) == NO_SUCH_PAIR)
|
if (BAG_getfirst (&first, second) == NO_SUCH_PAIR)
|
return NO_SUCH_PAIR;
|
return NO_SUCH_PAIR;
|
removefromlist (&lookupbyfirst[hash (first)], first);
|
removefromlist (&lookupbyfirst[hash (first)], first);
|
removefromlist (&lookupbysecond[hash (second)], first);
|
removefromlist (&lookupbysecond[hash (second)], first);
|
return NO_ERROR;
|
return NO_ERROR;
|
}
|
}
|
|
|
void
|
void
|
BAG_newbag ()
|
BAG_newbag ()
|
{
|
{
|
int i;
|
int i;
|
|
|
for (i = 0; i < 256; i++)
|
for (i = 0; i < 256; i++)
|
{
|
{
|
killwholelist (lookupbyfirst[i]);
|
killwholelist (lookupbyfirst[i]);
|
killwholelist (lookupbysecond[i]);
|
killwholelist (lookupbysecond[i]);
|
lookupbyfirst[i] = lookupbysecond[i] = (Hashentry *) 0;
|
lookupbyfirst[i] = lookupbysecond[i] = (Hashentry *) 0;
|
}
|
}
|
}
|
}
|
|
|
