| /* 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; |
| } |
| } |