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