#include <stdlib.h>
#include "util.h"
#include "gmap.h"

UINT g_map_last;

GENTPOOL gent_pool_new(v) GENTPOOL v; {
     GENTPOOL new_v = (GENTPOOL) MALLOC (sizeof * new_v);
     new_v -> lastpool = v;
     new_v -> next = 0;
     return new_v;
     }

VOID gent_pool_free(v) GENTPOOL v; {
     if (v == 0) return;
     gent_pool_free ( v -> lastpool );
     FREE(v);
     };

#ifndef INLINE
GENT gent_malloc(m) GMAP m;{
     GENTPOOL p = m -> cache;
     if (p -> next == GENT_POOL_SIZE) {
        p = gent_pool_new(p);
	m -> cache = p;
        }
     return &(p -> lotsa_gents[p->next++]);
     }
# endif

/* 
    Internal routine to allocate an empty map with 's' hash table slots and
    leap 't'.  All fields are initialized.
*/ 
static GMAP int_g_new_map(
    UINT (*hasher)(),
    void (*freer)(),
    CELL (*copier)(),
    UINT (*tester)(),
    UINT s, UINT t) {
    REGISTER GMAP m = (GMAP) MALLOC (sizeof * m);
    REGISTER UINT i;

    m -> hasher = hasher;
    m -> freer = freer;
    m -> copier = copier;
    m -> tester = tester;

    m -> nslots = s;
    m -> max_elts   = t;
    m -> nelts  = 0;
    m -> calls = 0;
    m -> probes = 0;

    m -> slots   = (GENT *) MALLOC (s * (sizeof(GENT)));
    m -> inverse = (GENT *) MALLOC (t * (sizeof(GENT)));
    
    m -> cache = gent_pool_new((GENTPOOL)0);
    
    for (i = 0 ; i < s; i++) {
        m -> slots[i] = (GENT) 0;
        }

    return m;
    }
    
/*
    Internal routines to free maps
*/
static VOID int_g_free_map(m) GMAP m; {
    UINT i;
    for (i = 1; i <= m -> nelts; i ++) {
        (m->freer)(m -> inverse[i] -> ent);
        }

    gent_pool_free (m -> cache);

    FREE (m -> slots);
    FREE (m -> inverse);
    FREE (m);
    }

#ifndef INLINE
static GMAP remap(m,e)
     REGISTER GMAP m; REGISTER GENT e; {
     REGISTER GENT * where = &(m -> slots[e -> hval % m -> nslots]);
     while (*where != (GENT) 0) where = &((*where) -> next);
     e -> next = 0;
     *where = e;
     }
#endif

/*
    Internal routine to make a duplicate map with more hash slots.
*/

static GMAP int_vxslots(m) GMAP m; {
    REGISTER UINT n;
    REGISTER UINT l;
    REGISTER UINT i;

    REGISTER GENT * old_slots;

    if (m -> nelts <= m -> nslots) {
       n = m -> nslots;
       l = n + m -> nelts;
       }

    else {
       n = m -> nslots;
       l = m -> nelts;
       }
    
    old_slots = m -> slots;
    m -> slots = (GENT *) MALLOC (l * sizeof (GENT));
    for (i = 0; i < l; i++) m -> slots[i] = (GENT) 0;
    
    m -> nslots = l;
    m -> probes = 0;

    for (i = 0; i < n; i++) {
        REGISTER GENT j = old_slots[i];
	while (j != (GENT) 0) {
	    REGISTER GENT k = j -> next;
#ifdef INLINE
            REGISTER GENT * where = &(m -> slots[j -> hval % m -> nslots]);
            while (*where != (GENT) 0) where = &((*where) -> next);
            j -> next = 0;
            *where = j;
#else
	    remap(m,j);
#endif
	    j = k;
	    }
        }

    FREE (old_slots);
    return m;
    }

static GMAP int_vxinverse(m) GMAP m; {
    GENT * old_inverse = m -> inverse;
    UINT i;
    m -> inverse = (GENT *) MALLOC (2 * m -> max_elts * sizeof (GENT));
    
    for (i = 0; i < m -> max_elts; i++) {
        m -> inverse[i] = old_inverse[i];
        }
    FREE (old_inverse);
    m -> max_elts += m -> max_elts;
    return m;
    }

GMAP g_new_map(
    UINT (*h)(),
    void (*f)(),
    CELL (*c)(),
    UINT (*t)())
	{ return int_g_new_map(h,f,c,t,243, 1215); }

UINT g_map(GMAP m, CELL t) {
     REGISTER UINT h = (m->hasher)(t);
     UINT k;
     REGISTER GENT * sgent;
     REGISTER GENT * pgent;
     REGISTER GENT gent;
     
     if (m -> probes > 2 * m -> calls) {
	int_vxslots(m);
	}
     m -> calls ++;
     k = h % m -> nslots;
     pgent = &(m->slots[k]);
     sgent = pgent;
	 
     while (1) {
               gent = *pgent;
	       m -> probes++;
	       if (gent == 0)
		    {
#ifndef INLINE
		    REGISTER GENT new_ent = gent_malloc(m);
#else
		    REGISTER GENT new_ent;
		    GENTPOOL p = m -> cache;
                    if (p -> next == GENT_POOL_SIZE) {
                       p = gent_pool_new(p);
	               m -> cache = p;
                       }
                    new_ent =  &(p -> lotsa_gents[p->next++]);
#endif INLINE
		    new_ent -> hval = h;
		    new_ent -> next = *sgent;
		    *sgent = new_ent;
		    new_ent -> ent = (m -> copier)(t);
		    g_map_last = ++m -> nelts;
		    if (g_map_last == m -> max_elts) int_vxinverse(m);
		    new_ent -> index = g_map_last;
		    m -> inverse[g_map_last] = new_ent;
		    return g_map_last;
		    }

	       else if (h == gent -> hval && (m->tester)(t, gent -> ent)) {	       
	            g_map_last = gent -> index;

		    if (pgent != sgent) { /* swap to front */
		        *pgent = gent -> next;
			gent -> next = *sgent;
			*sgent = gent;
			}

	            return g_map_last;
	            }

	       pgent = &(gent -> next);
               }
     }

UINT g_inmap(GMAP m, CELL t) {
     REGISTER UINT h = (m->hasher)(t);
     UINT k;
     REGISTER GENT * sgent;
     REGISTER GENT * pgent;
     REGISTER GENT gent;
     
     if (m -> probes > 4 * m -> calls) m = int_vxslots(m);
     m -> calls ++;
     k = h % m -> nslots;
     pgent = &(m->slots[k]);
     sgent = pgent;
	 
     while (1) {
               gent = *pgent;
	       m -> probes++;
	       if (gent == 0)
		    {
		    return 0;
		    }

	       else if (h == gent -> hval && (m->tester)(t, gent -> ent)) {
		    if (pgent != sgent) { /* swap to front */
		        *pgent = gent -> next;
			gent -> next = *sgent;
			*sgent = gent;
			}

	            return gent -> index;
	            }

	       pgent = & (gent -> next);
               }
     }