libhermit/usr/xray/hashtable.c

/* Copyright (c) 2013 The Chromium Authors. All rights reserved.
 * Use of this source code is governed by a BSD-style license that can be
 * found in the LICENSE file. */


/* Hashtable for XRay */

#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "xray_priv.h"

#if defined(XRAY)

struct XRayHashTableEntry {
  void* data;
  uint32_t key;
};


struct XRayHashTable {
  int capacity;
  int count;
  struct XRayHashTableEntry* array;
};


XRAY_NO_INSTRUMENT void XRayHashTableGrow(struct XRayHashTable* table);
XRAY_NO_INSTRUMENT uint32_t XRayHashTableHashKey(uint32_t key);
XRAY_NO_INSTRUMENT void XRayHashTableInit(struct XRayHashTable* table,
    int32_t capacity);

#define HASH_HISTO 1024
int g_hash_histo[HASH_HISTO];


/* Hashes a 32bit key into a 32bit value. */
uint32_t XRayHashTableHashKey(uint32_t x) {
  uint32_t y = x * 7919;
  uint32_t z;
  size_t c;
  uint8_t* s = (uint8_t*)&y;
  /* based on djb2 hash function */
  uint32_t h = 5381;
  for (c = 0; c < sizeof(y); ++c) {
    z = s[c];
    h = ((h << 5) + h) + z;
  }
  return h;
}


int XRayHashTableGetCapacity(struct XRayHashTable* table) {
  return table->capacity;
}


int XRayHashTableGetCount(struct XRayHashTable* table) {
  return table->count;
}


/* Looks up key in hashtable and returns blind data. */
void* XRayHashTableLookup(struct XRayHashTable* table, uint32_t key) {
  uint32_t h = XRayHashTableHashKey(key);
  uint32_t m = table->capacity - 1;
  uint32_t j = h & m;
  uint32_t i;
  int z = 1;
  for (i = 0; i < m; ++i) {
    /* An empty entry means the {key, data} isn't in the table. */
    if (NULL == table->array[j].data) {
      ++g_hash_histo[0];
      return NULL;
    }
    /* Search for address */
    if (table->array[j].key == key) {
      if (z >= HASH_HISTO)
        z = HASH_HISTO - 1;
      ++g_hash_histo[z];
      return table->array[j].data;
    }
    j = (j + 1) & m;
    ++z;
  }
  /* Table was full, and there wasn't a match. */
  return NULL;
}


/* Inserts key & data into hash table.  No duplicates. */
void* XRayHashTableInsert(struct XRayHashTable* table,
                          void* data, uint32_t key) {
  uint32_t h = XRayHashTableHashKey(key);
  uint32_t m = table->capacity - 1;
  uint32_t j = h & m;
  uint32_t i;
  for (i = 0; i < m; ++i) {
    /* Take the first empty entry. */
    /* (the key,data isn't already in the table) */
    if (NULL == table->array[j].data) {
      void* ret;
      float ratio;
      table->array[j].data = data;
      table->array[j].key = key;
      ++table->count;
      ret = data;
      ratio = (float)table->count / (float)table->capacity;
      /* Double the capacity of the symtable if we've hit the ratio. */
      if (ratio > XRAY_SYMBOL_TABLE_MAX_RATIO)
        XRayHashTableGrow(table);
      return ret;
    }
    /* If the key is already present, return the data in the table. */
    if (table->array[j].key == key) {
      return table->array[j].data;
    }
    j = (j + 1) & m;
  }
  /* Table was full */
  return NULL;
}


void* XRayHashTableAtIndex(struct XRayHashTable* table, int i) {
  if ((i < 0) || (i >= table->capacity))
    return NULL;
  return table->array[i].data;
}


/* Grows the hash table by doubling its capacity, */
/* then re-inserts all the elements into the new table. */
void XRayHashTableGrow(struct XRayHashTable* table) {
  struct XRayHashTableEntry* old_array = table->array;
  int old_capacity = table->capacity;
  int new_capacity = old_capacity * 2;
  int i;
  printf("XRay: Growing a hash table...\n");
  XRayHashTableInit(table, new_capacity);
  for (i = 0; i < old_capacity; ++i) {
    void* data = old_array[i].data;
    if (NULL != data) {
      uint32_t key = old_array[i].key;
      XRayHashTableInsert(table, data, key);
    }
  }
  XRayFree(old_array);
}


void XRayHashTableInit(struct XRayHashTable* table, int32_t capacity) {
  size_t bytes;
  if (0 != (capacity & (capacity - 1))) {
    printf("Xray: Hash table capacity should be a power of 2!\n");
    /* Round capacity up to next power of 2 */
    /* see http://aggregate.org/MAGIC/  */
    capacity--;
    capacity |= capacity >> 1;
    capacity |= capacity >> 2;
    capacity |= capacity >> 4;
    capacity |= capacity >> 8;
    capacity |= capacity >> 16;
    capacity++;
  }
  bytes = sizeof(table->array[0]) * capacity;
  table->capacity = capacity;
  table->count = 0;
  table->array = (struct XRayHashTableEntry*)XRayMalloc(bytes);
}


/* Creates & inializes hash table. */
struct XRayHashTable* XRayHashTableCreate(int capacity) {
  struct XRayHashTable* table;
  table = (struct XRayHashTable*)XRayMalloc(sizeof(*table));
  XRayHashTableInit(table, capacity);
  memset(&g_hash_histo[0], 0, sizeof(g_hash_histo[0]) * HASH_HISTO);
  return table;
}


/* Prints hash table performance to file; for debugging. */
void XRayHashTableHisto(FILE* f) {
  int i;
  for (i = 0; i < HASH_HISTO; ++i) {
    if (0 != g_hash_histo[i])
      fprintf(f, "hash_iterations[%d] = %d\n", i, g_hash_histo[i]);
  }
}


/* Frees hash table. */
/* Note: Does not free what the hash table entries point to. */
void XRayHashTableFree(struct XRayHashTable* table) {
  XRayFree(table->array);
  table->capacity = 0;
  table->count = 0;
  table->array = NULL;
  XRayFree(table);
}

#endif  /* XRAY */