native_client_sdk/src/libraries/xray/hashtable.c

   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