daemon/HashMap.cpp

   1 /**
   2  * Copyright (C) ARM Limited 2010-2011. All rights reserved.
   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 version 2 as
   6  * published by the Free Software Foundation.
   7  */
   8
   9 #include <stdlib.h>
  10 #include "HashMap.h"
  11
  12 /*
  13  * LRU Lossy HashMap
  14  * Values are always inserted to first slot
  15  * Value hits are moved to the first slot
  16  */
  17
  18 HashMap::HashMap() {
  19         history = (int*)calloc(HASHMAP_ENTRIES * MAX_COLLISIONS, sizeof(int));
  20 }
  21
  22 HashMap::~HashMap() {
  23         free(history);
  24 }
  25
  26 int *HashMap::hashEntries(int value) {
  27         int hashCode = (value >> 24) & 0xff;
  28         hashCode = hashCode * 31 + ((value >> 16) & 0xff);
  29         hashCode = hashCode * 31 + ((value >> 8) & 0xff);
  30         hashCode = hashCode * 31 + ((value >> 0) & 0xff);
  31         hashCode &= (HASHMAP_ENTRIES-1);
  32         return &history[hashCode * MAX_COLLISIONS];
  33 }
  34
  35 /*
  36  * Exists
  37  *  Pre:  [0][1][v][3]..[n-1]
  38  *  Post: [v][0][1][3]..[n-1]
  39  * Add
  40  *  Pre:  [0][1][2][3]..[n-1]
  41  *  Post: [v][0][1][2]..[n-2]
  42  */
  43 bool HashMap::existsAdd(int value) {
  44         int *line = hashEntries(value);
  45
  46         /* exists */
  47         for (int x = 0; x < MAX_COLLISIONS; x++) {
  48                 if (line[x] == value) {
  49                         for (; x > 0; x--) {
  50                                 line[x] = line[x-1];
  51                         }
  52                         line[0] = value;
  53                         return true;
  54                 }
  55         }
  56
  57         /* add */
  58         for (int x = MAX_COLLISIONS-1; x > 0; x--) {
  59                 line[x] = line[x-1];
  60         }
  61         line[0] = value;
  62
  63         return false;
  64 }