sim/arm/bag.c

   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