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. */ 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 54 int XRayHashTableGetCapacity(struct XRayHashTable* table) { 55 return table->capacity; 56 } 57 58 59 int XRayHashTableGetCount(struct XRayHashTable* table) { 60 return table->count; 61 } 62 63 64 /* Looks up key in hashtable and returns blind data. */ 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. */ 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 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. */ 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 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. */ 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. */ 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. */ 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
