#include "util.h"
#include <stdio.h>
#include <stdlib.h>
#include "tree.h"
#include "bv.h"
#include "maps.h"

/* "Maps" are structures that map objects to a set of consecutive integers. */
/* The subroutines to manipulate maps are:                                  */
/* v_map              Ditto, for bit vectors.
   v_inmap
   v_unmap
   v_new_map
   v_map_size
   v_map_last
   
   The integers associated start with the number 1 (i.e, first tree inserted
   is associated with 1).  T_map_size returns the number of associations,
   which is also the highest numbe assigned to a tree in the map.
   
   External routines crucial to this code are:
   bv_hash
   bv_eq
   
*/

UINT v_map_last;

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

VOID vent_pool_free(v) VENTPOOL v; {
     if (v == 0) return;
     vent_pool_free ( v -> lastpool );
     FREE(v);
     };

#ifndef INLINE
VENT vent_malloc(m) VMAP m;{
     VENTPOOL p = m -> cache;
     if (p -> next == VENT_POOL_SIZE) {
        p = vent_pool_new(p);
	m -> cache = p;
        }
     return &(p -> lotsa_vents[p->next++]);
     }
# endif

/* 
    Internal routine to allocate an empty map with 's' hash table slots and
    leap 't'.  All fields are initialized.
*/ 
static VMAP int_v_new_map(s,t) REGISTER UINT s; UINT t; {
    REGISTER VMAP m = (VMAP) MALLOC (sizeof * m);
    REGISTER UINT i;

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

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

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

    vent_pool_free (m -> cache);

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

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

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

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

    REGISTER VENT * old_slots;

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

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

    FREE (old_slots);
    return m;
    }

static VMAP int_vxinverse(m) VMAP m; {
    VENT * old_inverse = m -> inverse;
    UINT i;
    m -> inverse = (VENT *) MALLOC (2 * m -> max_elts * sizeof (VENT));
    
    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;
    }

VMAP v_new_map() { return int_v_new_map(243, 1215); }

UINT v_map(m,t)
     REGISTER VMAP m; BV t; {
     REGISTER UINT h;
     UINT k;
     REGISTER VENT * svent;
     REGISTER VENT * pvent;
     REGISTER VENT vent;
     
     if (m->last != 0 && bv_eq(v_unmap(m,m->last),t))
       {
	 v_map_last = m -> last;
	 return v_map_last;
       }
     h = bv_hash(t);

     if (m -> probes > 2 * m -> calls) {
	m = int_vxslots(m);
	}
     m -> calls ++;
     k = h % m -> nslots;
     pvent = &(m->slots[k]);
     svent = pvent;
	 
     while (1) {
               vent = *pvent;
	       m -> probes++;
	       if (vent == 0)
		    {
#ifndef INLINE
		    REGISTER VENT new_ent = vent_malloc(m);
#else
		    REGISTER VENT new_ent;
		    VENTPOOL p = m -> cache;
                    if (p -> next == VENT_POOL_SIZE) {
                       p = vent_pool_new(p);
	               m -> cache = p;
                       }
                    new_ent =  &(p -> lotsa_vents[p->next++]);
#endif INLINE
		    new_ent -> other.bv = 0; /* initialize this */
		    new_ent -> hval = h;
		    new_ent -> next = *svent;
		    *svent = new_ent;
		    new_ent -> ent = bv_copy(t);
		    v_map_last = ++m -> nelts;
		    if (v_map_last == m -> max_elts) m = int_vxinverse(m);
		    new_ent -> index = v_map_last;
		    m -> inverse[v_map_last] = new_ent;
		    return v_map_last;
		    }

	       else if (h == vent -> hval && bv_eq(t, vent -> ent)) {
	            v_map_last = vent -> index;
		    m->last = v_map_last;

		    if (pvent != svent) { /* swap to front */
		        *pvent = vent -> next;
			vent -> next = *svent;
			*svent = vent;
			}

	            return v_map_last;
	            }

	       pvent = &(vent -> next);
               }
     }

UINT v_inmap(m,t)
     REGISTER VMAP m; REGISTER BV t; {
     REGISTER UINT h;
     UINT k;
     REGISTER VENT * svent;
     REGISTER VENT * pvent;
     REGISTER VENT vent;
     
     if (m->last != 0 && bv_eq(v_unmap(m,m->last),t)) return m->last;

     h = bv_hash(t);
     if (m -> probes > 4 * m -> calls) m = int_vxslots(m);
     m -> calls ++;
     k = h % m -> nslots;
     pvent = &(m->slots[k]);
     svent = pvent;
	 
     while (1) {
               vent = *pvent;
	       m -> probes++;
	       if (vent == 0)
		    {
		    return 0;
		    }

	       else if (h == vent -> hval && bv_eq(t, vent -> ent)) {
		    if (pvent != svent) { /* swap to front */
		        *pvent = vent -> next;
			vent -> next = *svent;
			*svent = vent;
			}
                    m->last = vent ->index;
	            return vent -> index;
	            }

	       pvent = & (vent -> next);
               }
     }