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 */
9 #include <stdlib.h>
10 #include "HashMap.h"
12 /*
13 * LRU Lossy HashMap
14 * Values are always inserted to first slot
15 * Value hits are moved to the first slot
16 */
18 HashMap::HashMap() {
19 history = (int*)calloc(HASHMAP_ENTRIES * MAX_COLLISIONS, sizeof(int));
20 }
22 HashMap::~HashMap() {
23 free(history);
24 }
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 }
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);
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 }
57 /* add */
58 for (int x = MAX_COLLISIONS-1; x > 0; x--) {
59 line[x] = line[x-1];
60 }
61 line[0] = value;
63 return false;
64 }