#include "util.h"
#include "gmap.h"

#undef INLINE

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;
     }

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

GENT gent_malloc(m) GMAP m;{
     GENTPOOL p = m -> cache;
     GENT e;
     if (m -> freelist == 0) {
       if (p -> next == GENT_POOL_SIZE) {
	 p = gent_pool_new(p);
	 m -> cache = p;
       }
       e = &(p -> lotsa_gents[p->next++]);
       e -> index = 0;
       e -> other = 0;
       return e;
     }
     else {
       e = m -> freelist;
       m -> freelist = e -> next;
       e -> other = 0;
       return e;
     }
   }

/* 
    Internal routine to allocate an empty map with 's' hash table slots and
    leap 't'.  All fields are initialized.
*/ 
GMAP int_g_new_map(hasher, freer, copier, tester, s, t)
    UINT (*hasher)();
    UINT (*freer)();
    CELL (*copier)();
    UINT (*tester)();
    REGISTER 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 -> total_probes = 0;

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

    return m;
    }
    
/*
    Internal routines to free maps
*/
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);
    }

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;
     }

/*
    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 -> total_probes = m -> total_probes + m -> probes;
    m -> probes = 0;

    for (i = 0; i < n; i++) {
        REGISTER GENT j = old_slots[i];
	while (j != (GENT) 0) {
	    REGISTER GENT k = j -> next;
	    remap(m,j);
	    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(h,f,c,t)
    UINT (*h)();
    UINT (*f)();
    CELL (*c)();
    UINT (*t)();
	{ return int_g_new_map(h,f,c,t,243, 1215); }

UINT g_map(m,t)
     REGISTER GMAP m; CELL t; {
     REGISTER UINT h = (m->hasher)(t);
     UINT k;
     REGISTER GENT * sgent;
     REGISTER GENT * pgent;
     REGISTER GENT gent;
     UINT g_map_last;
     
     if (m -> probes > 5 * 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)
		    {
		    REGISTER GENT new_ent = gent_malloc(m);
		    new_ent -> hval = h;
		    new_ent -> next = *sgent;
		    *sgent = new_ent;
		    new_ent -> ent = (m -> copier)(t);

		    if (new_ent -> index == 0) 
		      g_map_last = ++m -> nelts;
		    else
		      g_map_last = new_ent -> index;

		    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(m,t)
     REGISTER GMAP m; REGISTER CELL t; {
     REGISTER UINT h = (m->hasher)(t);
     UINT k;
     REGISTER GENT * sgent;
     REGISTER GENT * pgent;
     REGISTER GENT gent;
     
     if (m -> probes > 10 * 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);
               }
     }


g_delent(m,i) GMAP m; UINT i;
{
  GENT bucket = m -> inverse[i];
  if (bucket == 0) return;
  {
    UINT h = bucket -> hval;
    UINT k = h % m -> nslots;
    REGISTER GENT * pgent = &(m->slots[k]);
    REGISTER GENT gent = *pgent;
    
    while (gent -> index != i) {
      pgent = &(gent -> next);
      gent = *pgent;
    }
    /* pgent is now the address of the pointer to the bucket */
    *pgent = gent -> next;
    gent -> next = m -> freelist;
    m -> freelist = gent;
    m -> inverse[i] = 0;
  }
}

#ifdef TEST
#include <stdio.h>

UINT h(x) UINT x; { return x; }
UINT c(x) UINT x; { return x; }
UINT t(x,y) UINT x,y; { return x == y; }
f(x) UINT x; { return; }

     main() {
       char buffer[256];
       UINT x,i;
       GMAP m = g_new_map(h,f,c,t);
       int iterating = 1;
       
while (iterating)  {
  printf("Add x, Remove i, Look x, Index i, Dump, Quit\n");
  scanf("%s", buffer);
  switch(buffer[0]) {
  case 'a': case 'A':
    scanf("%d",&x);
    i = g_map(m,x);
    if (i ==0)
      printf("%d is not in the map (an error!)\n",x);
    else
      printf("%d is at %d\n",x,i);
    break;
  case 'r': case 'R':
    scanf("%d",&i);
    if (i > 0 && i <= g_map_size(m) && g_valid_index(m,i)) {
      g_delent(m,i);
    }
    else {
      printf("%d is an invalid map index\n", i);
    }
    break;
  case 'l': case 'L':
    scanf("%d",&x);
    i = g_inmap(m,x);
    if (i ==0)
      printf("%d is not in the map\n",x);
    else
      printf("%d is at %d\n",x,i);
    break;
  case 'i': case 'I':
    scanf("%d",&i);
    if (i > 0 && i <= g_map_size(m) && g_valid_index(m,i))
      printf("%d %d\n", i,g_unmap(m,i));
    else
      printf("%d ----\n",i);
    break;
  case 'd': case 'D':
    for (i = 1; i <= g_map_size(m); i++) {
      if (g_valid_index(m,i))
	printf("%d %d\n", i,g_unmap(m,i));
      else
	printf("%d ----\n",i);
    }
    break;
  case 'q': case 'Q':
    iterating = 0;    
    break;
  }
}
     }
#endif