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