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
16struct XRayHashTableEntry {
17  void* data;
18  uint32_t key;
19};
20
21
22struct XRayHashTable {
23  int capacity;
24  int count;
25  struct XRayHashTableEntry* array;
26};
27
28
29XRAY_NO_INSTRUMENT void XRayHashTableGrow(struct XRayHashTable* table);
30XRAY_NO_INSTRUMENT uint32_t XRayHashTableHashKey(uint32_t key);
31XRAY_NO_INSTRUMENT void XRayHashTableInit(struct XRayHashTable* table,
32    int32_t capacity);
33
34#define HASH_HISTO 1024
35int g_hash_histo[HASH_HISTO];
36
37
38/* Hashes a 32bit key into a 32bit value. */
39uint32_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
54int XRayHashTableGetCapacity(struct XRayHashTable* table) {
55  return table->capacity;
56}
57
58
59int XRayHashTableGetCount(struct XRayHashTable* table) {
60  return table->count;
61}
62
63
64/* Looks up key in hashtable and returns blind data. */
65void* 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. */
93void* 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
126void* 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. */
135void 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
153void 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. */
175struct 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. */
185void 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. */
196void 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