1/*  bag.c -- ARMulator support code:  ARM6 Instruction Emulator.
2    Copyright (C) 1994 Advanced RISC Machines Ltd.
3
4    This program is free software; you can redistribute it and/or modify
5    it under the terms of the GNU General Public License as published by
6    the Free Software Foundation; either version 2 of the License, or
7    (at your option) any later version.
8
9    This program is distributed in the hope that it will be useful,
10    but WITHOUT ANY WARRANTY; without even the implied warranty of
11    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12    GNU General Public License for more details.
13
14    You should have received a copy of the GNU General Public License
15    along with this program; if not, write to the Free Software
16    Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston, MA 02110-1301, USA. */
17
18/********************************************************************/
19/* bag.c:                                                           */
20/* Offers a data structure for storing and getting pairs of number. */
21/* The numbers are stored together, put one can be looked up by     */
22/* quoting the other.  If a new pair is entered and one of the      */
23/* numbers is a repeat of a previous pair, then the previos pair    */
24/* is deleted.                                                      */
25/********************************************************************/
26
27#include "bag.h"
28#include <stdlib.h>
29
30#define HASH_TABLE_SIZE 256
31#define hash(x) (((x)&0xff)^(((x)>>8)&0xff)^(((x)>>16)&0xff)^(((x)>>24)&0xff))
32
33typedef struct hashentry
34{
35  struct hashentry *next;
36  int first;
37  int second;
38}
39Hashentry;
40
41Hashentry *lookupbyfirst[HASH_TABLE_SIZE];
42Hashentry *lookupbysecond[HASH_TABLE_SIZE];
43
44void
45addtolist (Hashentry ** add, long first, long second)
46{
47  while (*add)
48    add = &((*add)->next);
49  /* Malloc will never fail? :o( */
50  (*add) = (Hashentry *) malloc (sizeof (Hashentry));
51  (*add)->next = (Hashentry *) 0;
52  (*add)->first = first;
53  (*add)->second = second;
54}
55
56void
57killwholelist (Hashentry * p)
58{
59  Hashentry *q;
60
61  while (p)
62    {
63      q = p;
64      p = p->next;
65      free (q);
66    }
67}
68
69static void
70removefromlist (Hashentry ** p, long first)
71{
72  Hashentry *q;
73
74  while (*p)
75    {
76      if ((*p)->first == first)
77	{
78	  q = (*p)->next;
79	  free (*p);
80	  *p = q;
81	  return;
82	}
83      p = &((*p)->next);
84    }
85}
86
87void
88BAG_putpair (long first, long second)
89{
90  long junk;
91
92  if (BAG_getfirst (&junk, second) != NO_SUCH_PAIR)
93    BAG_killpair_bysecond (second);
94  addtolist (&lookupbyfirst[hash (first)], first, second);
95  addtolist (&lookupbysecond[hash (second)], first, second);
96}
97
98Bag_error
99BAG_getfirst (long *first, long second)
100{
101  Hashentry *look;
102
103  look = lookupbysecond[hash (second)];
104  while (look)
105    if (look->second == second)
106      {
107	*first = look->first;
108	return NO_ERROR;
109      }
110  return NO_SUCH_PAIR;
111}
112
113Bag_error
114BAG_getsecond (long first, long *second)
115{
116  Hashentry *look;
117
118  look = lookupbyfirst[hash (first)];
119  while (look)
120    {
121      if (look->first == first)
122	{
123	  *second = look->second;
124	  return NO_ERROR;
125	}
126      look = look->next;
127    }
128  return NO_SUCH_PAIR;
129}
130
131Bag_error
132BAG_killpair_byfirst (long first)
133{
134  long second;
135
136  if (BAG_getsecond (first, &second) == NO_SUCH_PAIR)
137    return NO_SUCH_PAIR;
138  removefromlist (&lookupbyfirst[hash (first)], first);
139  removefromlist (&lookupbysecond[hash (second)], first);
140  return NO_ERROR;
141}
142
143Bag_error
144BAG_killpair_bysecond (long second)
145{
146  long first;
147
148  if (BAG_getfirst (&first, second) == NO_SUCH_PAIR)
149    return NO_SUCH_PAIR;
150  removefromlist (&lookupbyfirst[hash (first)], first);
151  removefromlist (&lookupbysecond[hash (second)], first);
152  return NO_ERROR;
153}
154
155void
156BAG_newbag ()
157{
158  int i;
159
160  for (i = 0; i < 256; i++)
161    {
162      killwholelist (lookupbyfirst[i]);
163      killwholelist (lookupbysecond[i]);
164      lookupbyfirst[i] = lookupbysecond[i] = (Hashentry *) 0;
165    }
166}
167