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