/*
 *   Pure Data Packet. Hash class
 *   Copyright (c) by Tom Schouten <tom@zwizwa.be>
 *
 *   This program 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 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 General Public License
 *   along with this program; if not, write to the Free Software
 *   Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 *
 */



#include <pf/hash.h>
#include <pf/list.h>
#include <pf/symbol.h>
#include <pf/mem.h>

/* most of the keys will be symbols, 
   so scale down to log2 roundup of symbol size 

   the following code returns 24 on my system (Debian Sarge 2003/02/29)
   so 16 (log2(sizeof(pf_symbol_t))) seems to be a good value for round-down

   void *s1 = pf_alloc(sizeof(pf_symbol_t));
   void *s2 = pf_alloc(sizeof(pf_symbol_t));
   pf_post("%d", (s2 - s1));
*/

#define HASH_SHIFT 4

static inline int index_from_pointer(pf_hash_t *x, void *key)
{
    unsigned int knuth_magic = 2654435761U; /* see http://www.concentric.net/~Ttwang/tech/inthash.htm */
    unsigned int k = ((unsigned int)key) >> HASH_SHIFT;
    k *= knuth_magic;
    k &= (1 << x->logsize) - 1;
    return k;
}


pf_hash_t *pf_hash_new(unsigned int logsize){
    int i;
    unsigned int size = 1<<logsize;
    pf_hash_t *x = pf_alloc(sizeof(*x));
    x->elements = 0;
    x->logsize = logsize;
    x->table = pf_alloc(sizeof(pf_list_t) * size);
    i = size;
    while (i--) x->table[i] = pf_list_new();
    return x;
}
void pf_hash_free(pf_hash_t *x)
{
    int i = 1 << (x->logsize);
    while (i--) pf_stack_free(x->table[i]);
    pf_dealloc(x->table);
}
static inline pf_list_t *get_bucket(pf_hash_t *h, void *key)
{
    return h->table[index_from_pointer(h, key)];
}



/* iterate over collision list until m returns nonzero */
static inline void *apply_bucket(pf_list_t *l, pf_method_hash_t m, void *data)
{
    void *retval = 0;
    pf_atom_t *a = l->first;
    while (a){
	PF_ASSERT(a->t == a_list);
	pf_list_t *pair = a->w.w_list;
	PF_ASSERT(pair->last->t == a_pointer);
	if (retval = m(pair->last->w.w_pointer, pair->first, data)) break;
	a = a->next;
    }
    return retval;
}

static inline pf_atom_t *lookup_bucket(void *key, pf_atom_t *val, void *data)
{
    return (key == data) ? val : 0;
}

/* map a key to an atom */
pf_atom_t *pf_hash_lookup(pf_hash_t *h, void *key){
    pf_list_t *bucket = get_bucket(h, key);
    return (pf_atom_t *)apply_bucket(bucket, (pf_method_hash_t)lookup_bucket, (void *)key);
}

/* hash entries are stored as a (atom, key) pair */
void pf_hash_add(pf_hash_t *h, void *key, pf_atom_t *a)
{
    PF_ASSERT(!pf_hash_lookup(h, key)); // check it's not in there yet
    pf_list_t *bucket = get_bucket(h, key);
    pf_list_t *pair = pf_list_new();
    pf_list_push_pointer(pair, key);
    pf_list_push_atom(pair, a);
    pf_list_push(bucket, a_list, (pf_word_t)pair);
    h->elements++;
}


/* apply a function to all key,value pairs until it returns
   nonzero */
void *pf_hash_apply(pf_hash_t *h, pf_method_hash_t m, void *data)
{
    void *retval;
    unsigned int i = 1 << (h->logsize);
    while (i--){
	pf_list_t *bucket = h->table[i];
	if (retval = apply_bucket(bucket, m, data)) return retval;
    }
    return 0;
}




pf_list_t *pf_hash_keys(pf_hash_t *h)
{
    pf_list_t *keys = pf_list_new();
    return keys;
}

void pf_hash_rehash(pf_hash_t *h, int logsize)
{
    
}



/* this doesn't do anything really.. just for testing */
void pf_hash_setup(void)
{

}