trace_hashtable.c 6.11 KB
Newer Older
1
/*******************************************************************************
nikaeinn's avatar
nikaeinn committed
2 3
    OpenAirInterface
    Copyright(c) 1999 - 2014 Eurecom
4

nikaeinn's avatar
nikaeinn committed
5 6 7 8
    OpenAirInterface is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.
9 10


nikaeinn's avatar
nikaeinn committed
11 12 13 14
    OpenAirInterface is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.
15

nikaeinn's avatar
nikaeinn committed
16 17 18 19
    You should have received a copy of the GNU General Public License
    along with OpenAirInterface.The full GNU General Public License is
    included in this distribution in the file called "COPYING". If not,
    see <http://www.gnu.org/licenses/>.
20 21

  Contact Information
nikaeinn's avatar
nikaeinn committed
22 23
  OpenAirInterface Admin: openair_admin@eurecom.fr
  OpenAirInterface Tech : openair_tech@eurecom.fr
24
  OpenAirInterface Dev  : openair4g-devel@lists.eurecom.fr
nikaeinn's avatar
nikaeinn committed
25

ghaddab's avatar
ghaddab committed
26
  Address      : Eurecom, Campus SophiaTech, 450 Route des Chappes, CS 50193 - 06904 Biot Sophia Antipolis cedex, FRANCE
27 28 29 30 31 32 33 34 35

*******************************************************************************/

/*! \file hashtable.c
* \brief A 'C' implementation of a hashtable
* \author S. Gashaw,  N. Nikaein, J. Harri
* \date 2014
* \version 0.1
* \company EURECOM
36
* \email:
37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63
* \note
* \warning
*/

#include <stdio.h>
#include "trace_hashtable.h"
#include <stdlib.h>
#include <string.h>
#include "omg.h"

/*Global variables*/
node_info **list_head;
hash_table_t **table;

// hash table operations
/**
 * Fuction to create a new hash table
 * @param mode hash_table_mode which the hash table should follow
 * @returns hash_table_t object which references the hash table
 * @returns NULL when no memory
 */
void
create_new_table (int node_type)
{
  if(table==NULL)
    table = (hash_table_t **) calloc (MAX_NUM_NODE_TYPES, sizeof (hash_table_t*));

64 65 66 67 68 69
  table[node_type]=(hash_table_t *) calloc (MAX_NUM_NODE_TYPES, sizeof (hash_table_t));

  if (table == NULL || table[node_type]==NULL) {
    LOG_E (OMG, "--------table creation failed--------\n");
    exit (-1);
  }
70 71 72 73 74 75 76

  table[node_type]->key_len = LEN;
  table[node_type]->key_count = 0;
  table[node_type]->ratio = RATIO;

  table[node_type]->data_store =
    (node_container **) calloc (LEN, sizeof (node_container *));
77 78 79 80 81 82

  if (table[node_type]->data_store == NULL) {
    free (table[node_type]);
    LOG_E (OMG, "table creation failed \n");
    exit (-1);
  }
83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102

  //for (i = 0; i < LEN; i++)
  // table->data_store[i] = NULL;
}




/**
 * Function to add a key - value pair to the hash table, use HT_ADD macro
 * @param table hash table to add element to
 * @param key pointer to the key for the hash table
 * @param key_len length of the key in bytes
 * @param value pointer to the value to be added against the key
 * @param value_len length of the value in bytes
 * @returns 0 on sucess
 * @returns -1 when no memory
 */
void
hash_table_add (hash_table_t * t_table, node_data * node,
103
                node_container * value)
104 105 106 107 108 109
{
  hash_table_t *my_table = t_table;
  node_data *new_node = node;
  int key = new_node->gid;
  int hash_val = hash (&key, my_table->key_len);

110 111 112 113 114 115
  //resize check

  if (value == NULL) {
    //create new container for this node

    my_table->key_count++;
116

117 118 119 120 121 122
    node_container *new_c =
      (node_container *) calloc (1, sizeof (node_container));

    if (!new_c) {
      LOG_E (OMG, "node block creation failed\n");
      exit (-1);
123
    }
124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141

    new_c->gid = new_node->gid;
    new_c->next = new_node;
    new_c->end = new_c->next;
    new_c->next_c = NULL;

    if (my_table->data_store[hash_val] == NULL)
      my_table->data_store[hash_val] = new_c;
    else {
      node_container *temp1, *save;
      temp1 = my_table->data_store[hash_val];

      while (temp1 != NULL) {
        save = temp1;
        temp1 = temp1->next_c;
      }

      save->next_c = new_c;
142 143
    }

144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173
  } else {
    node_container *my_c = value;

    //put node data according to time
    if (my_c->gid == new_node->gid) {
      if (my_c->next->time > new_node->time) {
        new_node->next = my_c->next;
        my_c->next = new_node;
        return;
      }

      if (my_c->end->time <= new_node->time) {
        my_c->end->next = new_node;
        my_c->end = new_node;
        return;
      }

      node_data *temp = my_c->next;
      node_data *ptr = temp->next;

      while (ptr != NULL && ptr->time <= new_node->time) {
        temp = ptr;
        ptr = ptr->next;
      }

      temp->next = new_node;
      new_node->next = ptr;
    }
  }

174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190

}

/**
 * Function to lookup a key in a particular table
 * @param table table to look key in
 * @param key pointer to key to be looked for
 * @param key_len size of the key to be searched
 * @returns NULL when key is not found in the hash table
 * @returns void* pointer to the value in the table
 */
node_container *
hash_table_lookup (hash_table_t * table, int id)
{
  hash_table_t *my_table = table;
  int key = id;
  int hash_value_of_id = hash (&key, my_table->key_len);
191

192 193 194 195 196
  if (my_table->data_store[hash_value_of_id] == NULL)
    return NULL;

  node_container *temp = my_table->data_store[hash_value_of_id];

197 198 199 200 201 202
  while (temp != NULL) {
    if (temp->gid == id)
      break;

    temp = temp->next_c;
  }
203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221

  return temp;
}





/**
 * Function that returns a hash value for a given key and key_len
 * @param key pointer to the key
 * @param key_len length of the key
 * @param max_key max value of the hash to be returned by the function
 * @returns hash value belonging to [0, max_key)
 */
uint16_t
hash (int *key, int len)
{
  uint16_t *ptr = (uint16_t *) key;
222
  uint16_t hash = 0xbabe; // WHY NOT
223
  size_t i = 0;
224 225 226 227 228 229

  for (; i < (sizeof (key) / 2); i++) {
    hash ^= (i << 4 ^ *ptr << 8 ^ *ptr);
    ptr++;
  }

230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245
  hash = hash % len;
  return hash;
}


/**
 * Function to resize the hash table store house
 * @param table hash table to be resized
 * @param len new length of the hash table
 * @returns -1 when no elements in hash table
 * @returns -2 when no emmory for new store house
 * @returns 0 when sucess
 */
int
hash_table_resize ()
{
246
  return 0; // FIXME
247
}