/*
 * Lista doblemente ligada con una hash para hacerlo mucho mas rapido
 * el hashing es sencillo y con pocas colisiones pero limitado a no mas de 1 kb , despues habra colisiones
 * el hash ayuda a comparar la cadena mas rapido...
 *
 * en el nodo usa 'data' para buscar y almacena en 'content' los mismos datos pero al reves 
 * haciendo alusion de que en el nodo puedes meter lo que quieras
 *
 * tiene una 'interfaz' de comandos.
 *
 * al ejecutarse aparecera la 'shell'
 *
 * >
 *
 * los comandos son i , b, d y q
 *
 * i = inserta
 * b = busca
 * d = dump
 * q = quit
 * como los insertas seria:
 * > i dato1
 * > i dato2
 * > b dato1
 * > d
 *
 * Eduardo Ruiz Duarte
 * beck@math.co.ro
 */
#include <sys/types.h>		/* para size_t */
#include <string.h>		/* para malloc , calloc , strlen */
#include <unistd.h>		/* para read */
#include <stdio.h>		/* para NULL, stderr, stdout */
#include <stdlib.h>		/* nunca falta :p */
#define DATA_STORE 32		/* maximo alojaremos estos bytes */
struct nodo
{
  char data[DATA_STORE];	/* aqui se almacena el dato
				 * con el cual se buscara */
  char content[DATA_STORE];	/* aqui se almacena el
				 * contenido del nodo que se
				 * buscara usando 'data' */
  int hash;			/* aqui esta el hash de data que hara de la
				 * busqueda algo mas rapido */
  struct nodo *anterior;	/* nodo anterior */
  struct nodo *siguiente;	/* nodo siguiente */
  char init_flag;		/* indica si es el nodo inicial  (si, si tiene una razon de ser , 'anterior' en el inicial no es NULL aqui) */
};

/* ultimo nodo alojado , para efectos de free() */
struct nodo *ultimo = NULL;

int
hash_rapidin (void *data, size_t len)
{
  int *h, f = 0, x = 0, r, l = len / sizeof (int) , i = 0;
  void *t;
  r = len % sizeof (int);
  t = data + r;
  h = t;
 l = (l == 0) ? 1 : l;
  while (i != l)
    {
      x ^= h[i] ^ ((~h[(i + 1) % l]) + (i+h[i]+17));
      i++;
    }
  if (r > 0)
    {
      memcpy (&f, data, r);
      x *=  f;
      printf ("hash=%x\n", x);
    }
  return x;
}

int
dump (struct nodo *x)
{
  while (x != NULL)
    {
      if (x->hash != 0)
	printf
	  ("data=%s\tcontent=%s\there=%p\thash=%x\tbefore=%p\tnext=%p\n",
	   x->data, x->content, x, x->hash, x->anterior, x->siguiente);
      x = x->siguiente;
    }
  printf ("Last=%p\n", ultimo);
  return 0;
}

int
destroy (void)
{
  printf ("Last node was %p\n", ultimo);
  while (!ultimo->init_flag)
    {
      ultimo = ultimo->anterior;
      if (ultimo == NULL)
	break;
      printf ("freeing %p\n", ultimo);
      free (ultimo->siguiente);
    }
  return 0;
}

int
inserta (struct nodo *x, void *data, size_t length)
{
  struct nodo *t, *anterior;
  int i;
  t = x;
  /*
   * nos movemos a donde el nodo siguiente sea null (es donde es el
   * ultimo)
   */
  if (ultimo == NULL)
    while (t->siguiente != NULL)
      {
	t = t->siguiente;
	printf ("%p ISN'T available\n", t);
      }
  else
    t = ultimo;
  /*
   * en el nodo null alojamos memoria para comenzar a introducir datos
   * ahi
   */
  anterior = t;
  t->siguiente = calloc (1, sizeof (struct nodo));
  /* hacemos del nodo siguiente el nodo actual en el que trabajaremos */
  t = t->siguiente;
  printf ("%p IS available,Last=%p\n", t, ultimo);
  ultimo = t;

  /*
   * si caben los datos que queremos meter en nuestra variable de
   * tamanio estatico entonces:
   */
  if (length - 1 < DATA_STORE)
    {
      /*
       * copiamos datos a 'data' sin el \n en del nodo actual el cual es el que
       * nos identifica como la 'clave' de busqueda
       */
      memcpy (&t->data, data, length - 1);
      /*
       * tambien copiamos al contenido del nodo 'data' pero al
       * reves en 'content' sin el \n
       */
      for (i = length - 1; i >= 0; i--)
	t->content[length - i - 1] = *(char *) (data + i - 1);
      /* metemos en el nodo actual el hash de 'data' */
      t->hash = hash_rapidin (data, length);
      /* indicamos en el nodo actual quien es el nodo anterior */
      t->anterior = anterior;
      /* si el ultimo es null significa que somos el primer nodo en alojarse */
      if (ultimo == NULL)
	t->init_flag = 1;

      printf ("Last is %p\n", ultimo);
      return 0;
    }
  else
    {
      fprintf (stderr, "Data len must be less than %d\n", DATA_STORE);
      return 1;
    }
  return 0;
}

int
busca (struct nodo *x, void *data, size_t length)
{
  /* calculamos hash de lo que queremos buscar */
  int h = hash_rapidin (data, length);
  /* comenzamos a trabajar en el inicio de la lista */
  struct nodo *t = x;
  do
    {
      printf ("%p has %x\n", t, t->hash);
      /*
       * comparamos el hash del nodo actual con el hash de lo que
       * queremos buscar
       */
      if ((t->hash == h)&(h>0))
	{
	  fprintf (stderr, "Found %s with hash %x at %p\nContent: %s\n",
		   (char *) data, t->hash, t, t->content);
	  return 0;
	}
      /*
       * nos movemos al siguiente nodo porque el actual no
       * coincidia el hash
       */
      t = t->siguiente;
      /*
       * si es null el actual significa que ya llegamos al fin de
       * la lista y no encontramos nada
       */
      if (t == NULL)
	break;
    }
  while (1);
/* si estamos aqui es que no encontro nada */
printf("Not found\n");
  return -1;
}

/* interfaz chafa de uso de las funciones anteriores */
int
main (void)
{
  char buf[64], *hdl, cmd, f = 0;
  struct nodo principal;
  memset (&principal, 0, sizeof (struct nodo));
  memset (&buf, 0, sizeof (buf));
  while (1)
    {
      fprintf (stderr, "> ");
      read (0, &buf, sizeof (buf));
      cmd = buf[0];
      hdl = (char *) (buf + 2);
      switch (cmd)
	{
	case 'd':
	  printf ("Dumping all\n");
	  dump (&principal);
	  break;
	case 'b':
	  printf ("Searching for %s\n", hdl);
	  f = 1;
	  busca (&principal, hdl, strlen (hdl));
	  break;
	case 'i':
	  printf ("Inserting %s\n", hdl);
	  f = 1;
	  inserta (&principal, hdl, strlen (hdl));
	  break;
	case 'q':
	  printf ("quit\n");
	  destroy ();
	  exit (1);
	default:
	  if (!f)
	    if (buf[0] != 0xa)
	      {
		printf
		  ("Command not found\nUse: i <string> to insert,  b <string> to search, d to dump all data or q to quit\nbeck@math.co.ro\n");
		f = 0;
	      }
	}
      f = 0;
      memset (&buf, 0, sizeof (buf));
    }

  return 0;

}