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 {
  34   struct hashentry *next;
  35   int first;
  36   int second;
  37 }
  38 Hashentry;
  39
  40 Hashentry *lookupbyfirst[HASH_TABLE_SIZE];
  41 Hashentry *lookupbysecond[HASH_TABLE_SIZE];
  42
  43 void
  44 addtolist (Hashentry ** add, long first, long second)
  45 {
  46   while (*add)
  47     add = &((*add)->next);
  48   /* Malloc will never fail? :o( */
  49   (*add) = (Hashentry *) malloc (sizeof (Hashentry));
  50   (*add)->next = (Hashentry *) 0;
  51   (*add)->first = first;
  52   (*add)->second = second;
  53 }
  54
  55 void
  56 killwholelist (Hashentry * p)
  57 {
  58   Hashentry *q;
  59
  60   while (p)
  61     {
  62       q = p;
  63       p = p->next;
  64       free (q);
  65     }
  66 }
  67
  68 void
  69 removefromlist (Hashentry ** p, long first, long second)
  70 {
  71   Hashentry *q;
  72
  73   while (*p)
  74     {
  75       if ((*p)->first == first)
  76         {
  77           q = (*p)->next;
  78           free (*p);
  79           *p = q;
  80           return;
  81         }
  82       p = &((*p)->next);
  83     }
  84 }
  85
  86 void
  87 BAG_putpair (long first, long second)
  88 {
  89   long junk;
  90
  91   if (BAG_getfirst (&junk, second) != NO_SUCH_PAIR)
  92     BAG_killpair_bysecond (second);
  93   addtolist (&lookupbyfirst[hash (first)], first, second);
  94   addtolist (&lookupbysecond[hash (second)], first, second);
  95 }
  96
  97 Bag_error
  98 BAG_getfirst (long *first, long second)
  99 {
 100   Hashentry *look;
 101
 102   look = lookupbysecond[hash (second)];
 103   while (look)
 104     if (look->second == second)
 105       {
 106         *first = look->first;
 107         return NO_ERROR;
 108       }
 109   return NO_SUCH_PAIR;
 110 }
 111
 112 Bag_error
 113 BAG_getsecond (long first, long *second)
 114 {
 115   Hashentry *look;
 116
 117   look = lookupbyfirst[hash (first)];
 118   while (look)
 119     {
 120       if (look->first == first)
 121         {
 122           *second = look->second;
 123           return NO_ERROR;
 124         }
 125       look = look->next;
 126     }
 127   return NO_SUCH_PAIR;
 128 }
 129
 130 Bag_error
 131 BAG_killpair_byfirst (long first)
 132 {
 133   long second;
 134
 135   if (BAG_getsecond (first, &second) == NO_SUCH_PAIR)
 136     return NO_SUCH_PAIR;
 137   removefromlist (&lookupbyfirst[hash (first)], first, second);
 138   removefromlist (&lookupbysecond[hash (second)], first, second);
 139   return NO_ERROR;
 140 }
 141
 142 Bag_error
 143 BAG_killpair_bysecond (long second)
 144 {
 145   long first;
 146
 147   if (BAG_getfirst (&first, second) == NO_SUCH_PAIR)
 148     return NO_SUCH_PAIR;
 149   removefromlist (&lookupbyfirst[hash (first)], first, second);
 150   removefromlist (&lookupbysecond[hash (second)], first, second);
 151   return NO_ERROR;
 152 }
 153
 154 void
 155 BAG_newbag ()
 156 {
 157   int i;
 158
 159   for (i = 0; i < 256; i++)
 160     {
 161       killwholelist (lookupbyfirst[i]);
 162       killwholelist (lookupbysecond[i]);
 163       lookupbyfirst[i] = lookupbysecond[i] = (Hashentry *) 0;
 164     }
 165 }