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., 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
  33 typedef struct hashentry
  34 {
  35   struct hashentry *next;
  36   int first;
  37   int second;
  38 }
  39 Hashentry;
  40
  41 Hashentry *lookupbyfirst[HASH_TABLE_SIZE];
  42 Hashentry *lookupbysecond[HASH_TABLE_SIZE];
  43
  44 void
  45 addtolist (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
  56 void
  57 killwholelist (Hashentry * p)
  58 {
  59   Hashentry *q;
  60
  61   while (p)
  62     {
  63       q = p;
  64       p = p->next;
  65       free (q);
  66     }
  67 }
  68
  69 static void
  70 removefromlist (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
  87 void
  88 BAG_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
  98 Bag_error
  99 BAG_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
 113 Bag_error
 114 BAG_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
 131 Bag_error
 132 BAG_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
 143 Bag_error
 144 BAG_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
 155 void
 156 BAG_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 }