/*********************************************************************
 *
 * Copyright (C) 2001-2002,  Simon Kagstrom
 *
 * Filename:      hash_test.c
 * Description:   A sample program to demonstrate the usage of the
 *                generic hash table.
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Library General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 *
 * This program 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.
 *
 * You should have received a copy of the GNU Library General Public
 * License along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
 * 02111-1307, USA.
 *
 * $Id: hash_test.c 8461 2006-06-04 08:13:06Z ska $
 *
 ********************************************************************/

#include <stdlib.h> /* malloc */
#include <time.h>   /* time */
#include <errno.h>  /* errno */
#include <stdio.h>  /* perror etc */

#include "ght_hash_table.h" /* Include the generic hash table */

void fn(void *data, const void *key)
{
  free(data);
}

int main(int argc, char *argv[])
{
  ght_hash_table_t *p_table;
  ght_hash_table_t *p_table2;
  ght_iterator_t iterator;
  int i_loops = 100000;
  int i_removed = 0;
  const void *p_key;
  void *p_e;
  int i;

  /* Initialise the random seed */
  srand(1000);

  if (argc > 1)
    {
      /* Create two hash table with move to front heuristics, specifying the size for one. Both use automatic rehashing  */
      p_table = ght_create(atoi(argv[1]));
      ght_set_rehash(p_table, TRUE);
      ght_set_heuristics(p_table, GHT_HEURISTICS_MOVE_TO_FRONT);

      if (argc > 2)
	i_loops = atoi(argv[2]);

      p_table2 = ght_create(5000);

      ght_set_rehash(p_table2, TRUE);
      ght_set_heuristics(p_table2, GHT_HEURISTICS_MOVE_TO_FRONT);
    }
  else
    {
      /* Create two hash table with transpose heuristics, size
	 5000. Hash function is one_at_a_time_hash (default with NULL).
      */
      p_table = ght_create(5000);
      ght_set_rehash(p_table, FALSE);
      ght_set_heuristics(p_table, GHT_HEURISTICS_TRANSPOSE);

      p_table2 = ght_create(5000);
      ght_set_rehash(p_table2, FALSE);
      ght_set_heuristics(p_table2, GHT_HEURISTICS_TRANSPOSE);
    }

  /* This is a bounded bucket implementation */
  ght_set_bounded_buckets(p_table, 3, fn);

  /* Enter lots of stuff to the tables. */
  for (i=0; i<i_loops; i++)
    {
      int *p_entry_data;

      /* Allocate data for the entry as well (in this case an integer,
	 more often some structure).
      */
      if ( !(p_entry_data = (int*)malloc(sizeof(int))) )
	{
	  perror("malloc");
	  return -errno;
	}

      /* Set the data for the key and the entry */
      *p_entry_data = i_loops-i;

      /* Insert into table1 or table2 at random */
      if (rand()%2 == 1)
	{
	  if (ght_insert(p_table2,
			 p_entry_data,
			 sizeof(int), &i) < 0)
	    fprintf(stderr, "ERROR: Could not insert into table\n");
	}
      else
	{
	  if (ght_insert(p_table,
			 p_entry_data,
			 sizeof(int), &i) < 0)
	    fprintf(stderr, "ERROR: Could not insert into table\n");
	}

      /* If we didn't use automatic rehashing here, we could do a
       * manual rehash by using something like:
       *
       * if (p_table->i_items > p_table->i_size*2)
       *   ght_he_rehash(p_he);
       */
    }
  printf("Inserted %d elements.\n", i_loops);

  /* Get the same stuff FROM the table */
  for (i=0; i<i_loops; i++)
    {
      int *p_he;
      int i_key_data;

      /* Here we create a key for temporary usage (with one of the
	 numbers used previously)
      */
      i_key_data = rand()%i_loops;

      /* Get some element from one of the hash tables */
      if (rand()%2 == 1)
	p_he = (int*)ght_get(p_table,
			     sizeof(int), &i_key_data);
      else
	p_he = (int*)ght_get(p_table2,
			     sizeof(int), &i_key_data);

      /* Check if anything was found (might be in the other table) */
      if (p_he)
	{
	  /* Check if it's correct */
	  if (*p_he != i_loops-i_key_data)
	    {
	      printf("Found %d for key %d. WRONG!\n", *p_he, i_key_data);
	      return -1;
	    }
	}
    }

#ifdef USE_PROFILING
  printf("Hash table 1:\n");
  ght_print(p_table); /* Do not rely on this function, only available when built without optimization */
  printf("Hash table 2:\n");
  ght_print(p_table2);
  printf("\n");
#endif
  printf("Fetched %d elements. All tested OK\n", i_loops);

  /* Remove the same stuff FROM the table */
  for (i=0; i<i_loops; i++)
    {
      int *p_he;
      int i_key_data;

      /* Again, use a temporary (non-allocated) key */
      i_key_data = rand()%i_loops;

      /* Remove an element from one of the hash tables */
      if (rand()%2 == 1)
	p_he = (int*)ght_remove(p_table,
				sizeof(int), &i_key_data);
      else
	p_he = (int*)ght_remove(p_table2,
				sizeof(int), &i_key_data);

      /* Check if something could be removed */
      if (p_he)
	{
	  if (*p_he != i_loops-i_key_data)
	    {
	      printf("Found %d for key %d. WRONG!\n", *p_he, i_key_data);
	      return -1;
	    }

	  free(p_he);
	  p_he = NULL;
	  i_removed++;
	}
    }
  printf("Removed %d elements. All tested OK\n", i_removed);

#ifdef USE_PROFILING
  printf("Hash table 1:\n");
  ght_print(p_table);
  printf("Hash table 2:\n");
  ght_print(p_table2);
  printf("\n");
#endif


  /* Finally, remove the hash tables and all data within them (this
     will take some time if the tables are large). */
  printf("Finalizing the hash tables (remove all data)...\n");

  /* Free the entry data in the tables */
  for(p_e = ght_first(p_table, &iterator, &p_key); p_e; p_e = ght_next(p_table, &iterator, &p_key))
    {
      void *p;

      /* Remove the current entry from the table as well (will be done
       * in ght_finalize below so this is not strictly necessary).
       */
      p = ght_remove(p_table, sizeof(int), p_key);
      if (!p)
	printf("Removing the current iterated entry failed! This is a BUG\n");

      free(p_e);
    }
  for(p_e = ght_first(p_table2, &iterator, &p_key); p_e; p_e = ght_next(p_table2, &iterator, &p_key))
    {
      free(p_e);
    }

  /* Free the tables */
  ght_finalize(p_table);
  ght_finalize(p_table2);
  printf("Finalizing done\n");

  return 0;
}