1 /* Copyright (c) 2013 The Chromium Authors. All rights reserved.
2 * Use of this source code is governed by a BSD-style license that can be
3 * found in the LICENSE file. */
4
5
6 /* Hashtable for XRay */
7
8 #include <stdint.h>
9 #include <stdio.h>
10 #include <stdlib.h>
11 #include <string.h>
12 #include "xray/xray_priv.h"
13
14 #if defined(XRAY)
15
16 struct XRayHashTableEntry {
17 void* data;
18 uint32_t key;
19 };
20
21
22 struct XRayHashTable {
23 int capacity;
24 int count;
25 struct XRayHashTableEntry* array;
26 };
27
28
29 XRAY_NO_INSTRUMENT void XRayHashTableGrow(struct XRayHashTable* table);
30 XRAY_NO_INSTRUMENT uint32_t XRayHashTableHashKey(uint32_t key);
31 XRAY_NO_INSTRUMENT void XRayHashTableInit(struct XRayHashTable* table,
32 int32_t capacity);
33
34 #define HASH_HISTO 1024
35 int g_hash_histo[HASH_HISTO];
36
37
38 /* Hashes a 32bit key into a 32bit value. */
XRayHashTableHashKey(uint32_t x)39 uint32_t XRayHashTableHashKey(uint32_t x) {
40 uint32_t y = x * 7919;
41 uint32_t z;
42 size_t c;
43 uint8_t* s = (uint8_t*)&y;
44 /* based on djb2 hash function */
45 uint32_t h = 5381;
46 for (c = 0; c < sizeof(y); ++c) {
47 z = s[c];
48 h = ((h << 5) + h) + z;
49 }
50 return h;
51 }
52
53
XRayHashTableGetCapacity(struct XRayHashTable * table)54 int XRayHashTableGetCapacity(struct XRayHashTable* table) {
55 return table->capacity;
56 }
57
58
XRayHashTableGetCount(struct XRayHashTable * table)59 int XRayHashTableGetCount(struct XRayHashTable* table) {
60 return table->count;
61 }
62
63
64 /* Looks up key in hashtable and returns blind data. */
XRayHashTableLookup(struct XRayHashTable * table,uint32_t key)65 void* XRayHashTableLookup(struct XRayHashTable* table, uint32_t key) {
66 uint32_t h = XRayHashTableHashKey(key);
67 uint32_t m = table->capacity - 1;
68 uint32_t j = h & m;
69 uint32_t i;
70 int z = 1;
71 for (i = 0; i < m; ++i) {
72 /* An empty entry means the {key, data} isn't in the table. */
73 if (NULL == table->array[j].data) {
74 ++g_hash_histo[0];
75 return NULL;
76 }
77 /* Search for address */
78 if (table->array[j].key == key) {
79 if (z >= HASH_HISTO)
80 z = HASH_HISTO - 1;
81 ++g_hash_histo[z];
82 return table->array[j].data;
83 }
84 j = (j + 1) & m;
85 ++z;
86 }
87 /* Table was full, and there wasn't a match. */
88 return NULL;
89 }
90
91
92 /* Inserts key & data into hash table. No duplicates. */
XRayHashTableInsert(struct XRayHashTable * table,void * data,uint32_t key)93 void* XRayHashTableInsert(struct XRayHashTable* table,
94 void* data, uint32_t key) {
95 uint32_t h = XRayHashTableHashKey(key);
96 uint32_t m = table->capacity - 1;
97 uint32_t j = h & m;
98 uint32_t i;
99 for (i = 0; i < m; ++i) {
100 /* Take the first empty entry. */
101 /* (the key,data isn't already in the table) */
102 if (NULL == table->array[j].data) {
103 void* ret;
104 float ratio;
105 table->array[j].data = data;
106 table->array[j].key = key;
107 ++table->count;
108 ret = data;
109 ratio = (float)table->count / (float)table->capacity;
110 /* Double the capacity of the symtable if we've hit the ratio. */
111 if (ratio > XRAY_SYMBOL_TABLE_MAX_RATIO)
112 XRayHashTableGrow(table);
113 return ret;
114 }
115 /* If the key is already present, return the data in the table. */
116 if (table->array[j].key == key) {
117 return table->array[j].data;
118 }
119 j = (j + 1) & m;
120 }
121 /* Table was full */
122 return NULL;
123 }
124
125
XRayHashTableAtIndex(struct XRayHashTable * table,int i)126 void* XRayHashTableAtIndex(struct XRayHashTable* table, int i) {
127 if ((i < 0) || (i >= table->capacity))
128 return NULL;
129 return table->array[i].data;
130 }
131
132
133 /* Grows the hash table by doubling its capacity, */
134 /* then re-inserts all the elements into the new table. */
XRayHashTableGrow(struct XRayHashTable * table)135 void XRayHashTableGrow(struct XRayHashTable* table) {
136 struct XRayHashTableEntry* old_array = table->array;
137 int old_capacity = table->capacity;
138 int new_capacity = old_capacity * 2;
139 int i;
140 printf("XRay: Growing a hash table...\n");
141 XRayHashTableInit(table, new_capacity);
142 for (i = 0; i < old_capacity; ++i) {
143 void* data = old_array[i].data;
144 if (NULL != data) {
145 uint32_t key = old_array[i].key;
146 XRayHashTableInsert(table, data, key);
147 }
148 }
149 XRayFree(old_array);
150 }
151
152
XRayHashTableInit(struct XRayHashTable * table,int32_t capacity)153 void XRayHashTableInit(struct XRayHashTable* table, int32_t capacity) {
154 size_t bytes;
155 if (0 != (capacity & (capacity - 1))) {
156 printf("Xray: Hash table capacity should be a power of 2!\n");
157 /* Round capacity up to next power of 2 */
158 /* see http://aggregate.org/MAGIC/ */
159 capacity--;
160 capacity |= capacity >> 1;
161 capacity |= capacity >> 2;
162 capacity |= capacity >> 4;
163 capacity |= capacity >> 8;
164 capacity |= capacity >> 16;
165 capacity++;
166 }
167 bytes = sizeof(table->array[0]) * capacity;
168 table->capacity = capacity;
169 table->count = 0;
170 table->array = (struct XRayHashTableEntry*)XRayMalloc(bytes);
171 }
172
173
174 /* Creates & inializes hash table. */
XRayHashTableCreate(int capacity)175 struct XRayHashTable* XRayHashTableCreate(int capacity) {
176 struct XRayHashTable* table;
177 table = (struct XRayHashTable*)XRayMalloc(sizeof(*table));
178 XRayHashTableInit(table, capacity);
179 memset(&g_hash_histo[0], 0, sizeof(g_hash_histo[0]) * HASH_HISTO);
180 return table;
181 }
182
183
184 /* Prints hash table performance to file; for debugging. */
XRayHashTableHisto(FILE * f)185 void XRayHashTableHisto(FILE* f) {
186 int i;
187 for (i = 0; i < HASH_HISTO; ++i) {
188 if (0 != g_hash_histo[i])
189 fprintf(f, "hash_iterations[%d] = %d\n", i, g_hash_histo[i]);
190 }
191 }
192
193
194 /* Frees hash table. */
195 /* Note: Does not free what the hash table entries point to. */
XRayHashTableFree(struct XRayHashTable * table)196 void XRayHashTableFree(struct XRayHashTable* table) {
197 XRayFree(table->array);
198 table->capacity = 0;
199 table->count = 0;
200 table->array = NULL;
201 XRayFree(table);
202 }
203
204 #endif /* XRAY */
205
206