Commit | Line | Data |
---|---|---|
c906108c SS |
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., 59 Temple Place - Suite 330, Boston, MA 02111-1307, 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 | ||
29 | #define HASH_TABLE_SIZE 256 | |
30 | #define hash(x) (((x)&0xff)^(((x)>>8)&0xff)^(((x)>>16)&0xff)^(((x)>>24)&0xff)) | |
31 | ||
32 | typedef struct hashentry { | |
33 | struct hashentry *next; | |
34 | int first; | |
35 | int second; | |
36 | } Hashentry; | |
37 | ||
38 | Hashentry *lookupbyfirst[HASH_TABLE_SIZE]; | |
39 | Hashentry *lookupbysecond[HASH_TABLE_SIZE]; | |
40 | ||
41 | void addtolist(Hashentry **add, long first, long second) { | |
42 | while (*add) add = &((*add)->next); | |
43 | /* Malloc will never fail? :o( */ | |
44 | (*add) = (Hashentry *) malloc(sizeof(Hashentry)); | |
45 | (*add)->next = (Hashentry *) 0; | |
46 | (*add)->first = first; | |
47 | (*add)->second = second; | |
48 | } | |
49 | ||
50 | void killwholelist(Hashentry *p) { | |
51 | Hashentry *q; | |
52 | ||
53 | while (p) { | |
54 | q = p; | |
55 | p = p->next; | |
56 | free(q); | |
57 | } | |
58 | } | |
59 | ||
60 | void removefromlist(Hashentry **p, long first, long second) { | |
61 | Hashentry *q; | |
62 | ||
63 | while (*p) { | |
64 | if ((*p)->first == first) { | |
65 | q = (*p)->next; | |
66 | free(*p); | |
67 | *p = q; | |
68 | return; | |
69 | } | |
70 | p = &((*p)->next); | |
71 | } | |
72 | } | |
73 | ||
74 | void BAG_putpair(long first, long second) { | |
75 | long junk; | |
76 | ||
77 | if (BAG_getfirst(&junk, second) != NO_SUCH_PAIR) | |
78 | BAG_killpair_bysecond(second); | |
79 | addtolist(&lookupbyfirst[hash(first)], first, second); | |
80 | addtolist(&lookupbysecond[hash(second)], first, second); | |
81 | } | |
82 | ||
83 | Bag_error BAG_getfirst(long *first, long second) { | |
84 | Hashentry *look; | |
85 | ||
86 | look = lookupbysecond[hash(second)]; | |
87 | while(look) if (look->second == second) { | |
88 | *first = look->first; | |
89 | return NO_ERROR; | |
90 | } | |
91 | return NO_SUCH_PAIR; | |
92 | } | |
93 | ||
94 | Bag_error BAG_getsecond(long first, long *second) { | |
95 | Hashentry *look; | |
96 | ||
97 | look = lookupbyfirst[hash(first)]; | |
98 | while(look) { | |
99 | if (look->first == first) { | |
100 | *second = look->second; | |
101 | return NO_ERROR; | |
102 | } | |
103 | look = look->next; | |
104 | } | |
105 | return NO_SUCH_PAIR; | |
106 | } | |
107 | ||
108 | Bag_error BAG_killpair_byfirst(long first) { | |
109 | long second; | |
110 | ||
111 | if (BAG_getsecond(first, &second) == NO_SUCH_PAIR) | |
112 | return NO_SUCH_PAIR; | |
113 | removefromlist(&lookupbyfirst[hash(first)], first, second); | |
114 | removefromlist(&lookupbysecond[hash(second)], first, second); | |
115 | return NO_ERROR; | |
116 | } | |
117 | ||
118 | Bag_error BAG_killpair_bysecond(long second) { | |
119 | long first; | |
120 | ||
121 | if (BAG_getfirst(&first, second) == NO_SUCH_PAIR) | |
122 | return NO_SUCH_PAIR; | |
123 | removefromlist(&lookupbyfirst[hash(first)], first, second); | |
124 | removefromlist(&lookupbysecond[hash(second)], first, second); | |
125 | return NO_ERROR; | |
126 | } | |
127 | ||
128 | void BAG_newbag() { | |
129 | int i; | |
130 | ||
131 | for (i = 0; i < 256; i++) { | |
132 | killwholelist(lookupbyfirst[i]); | |
133 | killwholelist(lookupbysecond[i]); | |
134 | lookupbyfirst[i] = lookupbysecond[i] = (Hashentry *) 0; | |
135 | } | |
136 | } | |
137 | ||
138 | ||
139 | ||
140 | ||
141 |