1  /* Copyright (C) 2021-2023 Free Software Foundation, Inc.
       2     Contributed by Oracle.
       3  
       4     This file is part of GNU Binutils.
       5  
       6     This program is free software; you can redistribute it and/or modify
       7     it under the terms of the GNU General Public License as published by
       8     the Free Software Foundation; either version 3, or (at your option)
       9     any later version.
      10  
      11     This program is distributed in the hope that it will be useful,
      12     but WITHOUT ANY WARRANTY; without even the implied warranty of
      13     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
      14     GNU General Public License for more details.
      15  
      16     You should have received a copy of the GNU General Public License
      17     along with this program; if not, write to the Free Software
      18     Foundation, 51 Franklin Street - Fifth Floor, Boston,
      19     MA 02110-1301, USA.  */
      20  
      21  /*
      22   *	Dbe Cache Map implementation.
      23   *
      24   *    Simple Cache Map makes the following assumptions:
      25   *    - Cache Map is used for very fast but not guaranteed mapping;
      26   *    - No Relations can be used;
      27   *    - all objects used as keys or values has to be managed
      28   *      outside CacheMap (f.e. deletion);
      29   */
      30  
      31  #ifndef _DbeCacheMap_h
      32  #define _DbeCacheMap_h
      33  
      34  #include <Map.h>
      35  
      36  template <typename Key_t, class ITEM>
      37  class DbeCacheMap : public Map<Key_t, ITEM *>
      38  {
      39  public:
      40  
      41    DbeCacheMap (int _size = DefaultSize)
      42    { // _size should be 2 ** N
      43      size = _size;
      44      table = new DbeCache_T[size];
      45      memset (table, 0, size * sizeof (DbeCache_T));
      46    };
      47  
      48    ~DbeCacheMap ()
      49    {
      50      delete[] table;
      51    };
      52  
      53    void
      54    put (Key_t key, ITEM *val)
      55    {
      56      int ind = get_hash (key);
      57      table[ind].key = key;
      58      table[ind].value = val;
      59    };
      60  
      61    ITEM *
      62    get (Key_t key)
      63    {
      64      int ind = get_hash (key);
      65      if (table[ind].key == key)
      66        return table[ind].value;
      67      return (ITEM *) NULL;
      68    };
      69  
      70    ITEM *
      71    remove (Key_t key)
      72    {
      73      int ind = get_hash (key);
      74      ITEM *v = table[ind].value;
      75      table[ind].value = (ITEM *) NULL;
      76      return v;
      77    };
      78  
      79    ITEM *
      80    get (Key_t /* key */, typename Map<Key_t, ITEM *>::Relation /* rel */)
      81    {
      82      return (ITEM *) NULL;
      83    };
      84  
      85  private:
      86  
      87    enum
      88    {
      89      DefaultSize     = (1 << 13)
      90    };
      91  
      92    typedef struct DbeCache_S
      93    {
      94      Key_t key;
      95      ITEM *value;
      96    } DbeCache_T;
      97    DbeCache_T *table;
      98    int size;
      99  
     100    int
     101    get_hash (Key_t key)
     102    {
     103      unsigned long long h = (unsigned long long) key;
     104      h ^= (h >> 20) ^ (h >> 12);
     105      return (h ^ (h >> 7) ^ (h >> 4)) & (size - 1);
     106    }
     107  };
     108  
     109  #endif