#include <ctype.h>
#include <stdio.h>


#define PANIC_FILE stderr
 
#include "tmp/c.h"
#include "utils/log.h"
    
#include "assoc.h"

int* H_getmem();


#define LOWER(ch) (isupper(ch)? tolower(ch) : (ch))

/************************************************************************\
**************************************************************************
**									**
**  This package uses hash tables to implement an associative memory,	**
**  or "name table".  See also "assoc.h" and "assoc_internals.h".	**
**									**
**  The user may associate names, also called "index strings" with	**
**  packets of memory, called "mem_cell"s, which come in fixed sizes.	**
**  Then if you know the name, you can look up the mem_cell or vice	**
**  versa.								**
**									**
**  The collision recovery mechanism is a nifty little scheme           **
**  of my own invention, which I call "linear-congruential rehash",	**
**  which means "add one and multiply by three".			**
**									**
**  The orbit of the rehash function touches exactly half the entries	**
**  in the table, and the table is never allowed to be over half full,  **
**  so there will always be an empty slot for a new entry.		**
**  Removing entries is a little bit tricky. Since the lookup mechanism **
**  stops and reports failure when it comes to an empty slot in the 	**
**  rehash orbit for the value searched for, when an entry is removed,	**
**  the values in the same orbit which are there as a result of a 	**
**  collision must be backed up to fill the evacuated slot.  		**
**  The entry number is also there for removing entries.  It provides a **
**  reference back to the slot which points to the entry.		**
**                                                                      **
**  We assume that our machine uses two's complement arithmetic.	**
**  $Header: /usr/local/dev/postgres/mastertree/src/utils/fmgr/RCS/assoc.c,v 1.8 1991/11/09 01:53:44 mer Exp $								**
**************************************************************************
\************************************************************************/

/**************************************************************************
**
**  An entry looks like this:
**
**
**  [pointers]      [pointees]
**
**  		------------------
**  mem	     -> |  entry number  |  index of entry into hash table.
**  		------------------
**  mem_cell ->	|	         |
**  (slot)	|		 |
**		| user's goodies |  of size table->value_size
**	        |		 |
**		------------------
**  string   -> |		 |
**		|  index string  |
**		|		 |
**		|		 |
**		------------------
**
**
**  See string_from_cell(), cell_from_string(), mem_from_cell(), and
**  cell_from_mem().. all macros.
**
\*************************************************************************/







/* N.B. The routine assoc() depends on the fact that if a table is less
** than half full, the rehash orbit will always find an empty slot.
** This rehash will hit exactly half the slots before it repeats, provided
** that the table length is a power of two.
*/
#define REHASH(hash,table) (((hash+1)*3) & table -> mask)




/**** factory-procedure, makes new tables. ****/

assoc_mem
new_assoc_mem(value_size)
  int value_size; /* storage size of values to be in assoc mem */
{
  register assoc_mem table;

  table = (assoc_mem) H_getmem(sizeof (struct assoc_mem_rec));

  table->value_size = value_size;
  table->entries = 0;
  table->size = INIT_TABLE_SIZE;
  table->size_div_2 = table->size / 2;
  table->mask = table->size -1;
  table->array = (hash_table *)H_getmem(table->size * (sizeof (mem_cell)));

  return table;
}



/* Associates a name with a new mem_cell, or return pointers to previously
** associated cell.  Initializes new cells to all zero, so you may determine 
** whether or not a cell is new by smudging a "virgin-bit" when you
** first obtain a new cell.  If you get a cell from assoc() with a
** fresh new virgin bit, then the cell must be a new one.
*/


mem_cell
assoc( string, table)
  register char* string;
  register assoc_mem table;
{ /* assoc */

  int length;
  int hashval;

  register int   rehash;
  register entry assoc_value;

  /* This is essential.  See assoc_internals.h */
  if (table->entries >= table->size_div_2 - 1)
    H_expand_table(table);

  hash(string, table->mask, &length, &hashval);
  rehash = hashval;

 look_at_slot:
  {  register entry * slot = &((*(table->array))[rehash]);

     assoc_value = *slot;

     if ( (assoc_value) == 0)
       /* Nothing else has hashed to this slot. 
	  We will put our string here. */
       { 
	 *slot =  cell_from_mem(
		    (entry) H_getmem(table->value_size + length + sizeof('\0')
				     + sizeof(entry*)));

	 *(mem_from_cell(*slot)) = rehash;
	 assoc_value = *slot;
	 strcpy(string_from_cell(assoc_value, table), string);
	 table->entries++;
	 return assoc_value;		/* <=========== */
       }
	
     if (strcmp( string_from_cell(assoc_value,table), string) != 0)
       {				/* Oops.. collision. */
	 rehash = REHASH(rehash,table);
	 goto look_at_slot;		/* <=========== */
       }
     else return assoc_value;		/* <=========== */

   }
    

  


}					/* end assoc */

/* Like assoc, except for non-null-terminated strings */
mem_cell
assocn( string, length, table)
  register char* string;
  register assoc_mem table;
  register int length;
{ /* assocn */

  int hashval;

  register int   rehash;
  register entry assoc_value;

  /* This is essential.  See assoc_internals.h */
  if (table->entries >= table->size_div_2 - 1)
    H_expand_table(table);

  hashn(string, table->mask, length, &hashval);
  rehash = hashval;

 look_at_slot:
  {  register entry * slot = &((*(table->array))[rehash]);

     assoc_value = *slot;

     if ( (assoc_value) == 0)
       /* Nothing else has hashed to this slot. 
	  We will put our string here. */
       { 
	 *slot =  cell_from_mem(
		    (entry) H_getmem(table->value_size + length + sizeof('\0')
				     + sizeof(entry*)));

	 *(mem_from_cell(*slot)) = rehash;
	 assoc_value = *slot;
	 strncpy(string_from_cell(assoc_value, table), string, length);
	 table->entries++;
	 return assoc_value;		/* <=========== */
       }
	
     if (lstrncmp( string_from_cell(assoc_value,table), string, length) != 0)
       {				/* Oops.. collision. */
	 rehash = REHASH(rehash,table);
	 goto look_at_slot;		/* <=========== */
       }
     else return assoc_value;		/* <=========== */

   }
    

}					/* end assocn */
/* Like assoc, except for non-null-terminated strings, and folds cases. */
mem_cell
assocnf( string, length, table)
  register char* string;
  register assoc_mem table;
  register int length;
{ /* assocn */

  int hashval;

  register int   rehash;
  register entry assoc_value;

  /* This is essential.  See assoc_internals.h */
  if (table->entries >= table->size_div_2 - 1)
    H_expand_table(table);

  hashnf(string, table->mask, length, &hashval);
  rehash = hashval;

 look_at_slot:
  {  register entry * slot = &((*(table->array))[rehash]);

     assoc_value = *slot;

     if ( (assoc_value) == 0)
       /* Nothing else has hashed to this slot. 
	  We will put our string here. */
       { 
	 *slot =  cell_from_mem(
		    (entry) H_getmem(table->value_size + length + sizeof('\0')
				     + sizeof(entry*)));

	 *(mem_from_cell(*slot)) = rehash;
	 assoc_value = *slot;
	 strncpy(string_from_cell(assoc_value, table), string, length);
	 table->entries++;
	 return assoc_value;		/* <=========== */
       }
	
     if (lstrncmpf( string_from_cell(assoc_value,table), string, length) != 0)
       {				/* Oops.. collision. */
	 rehash = REHASH(rehash,table);
	 goto look_at_slot;		/* <=========== */
       }
     else return assoc_value;		/* <=========== */

   }
    
}					/* end assocnf */

/* returns 0 iff a null-terminated string and counted string compare */
static
lstrncmp(nullterm, counted, len)
  char* nullterm;
  char* counted;
{
                
  while( *nullterm && len && *nullterm++ == *counted++)
    len--;
  return !(len == 0 && *nullterm == 0);
}

/* returns 0 iff a null-terminated string and counted string compare */
/* folds cases */
static
lstrncmpf(nullterm, counted, len)
  char* nullterm;
  char* counted;
{
                
  while( *nullterm && len && LOWER(*nullterm) == LOWER(*counted))
    {
      len--;
      nullterm++; counted++;
    }
  return !(len == 0 && *nullterm == 0);
}



/* Look up the mem_cell associated with a given name. */
/* Returns NULL if not found.			      */

mem_cell
assoc_lookup( string, table)
  register char* string;
  register assoc_mem table;
{
  register entry retval;
  int length;
  int hashval;

  if (table == (assoc_mem) NULL) {
     elog(NOTICE, "assoc_lookup for %s called with NULL assoc_mem table.", string);
     return ((mem_cell) NULL);
  }

  hash(string, table->mask, &length, &hashval);

  { register int  rehash = hashval;
    register int * assoc_value = 0;

    look_at_slot:
	{  entry * slot = &((*(table->array))[rehash]);

	   assoc_value = *slot;

	   if ( (assoc_value) == 0)
		/* Nothing has hashed to this slot. 
		   Lookup has come to a sorry end. */
		{ 
		   return assoc_value;  /* <=========== */
		}
	
	   if (strcmp( string_from_cell(assoc_value,table), string) == 0)
		/*  An identical string was previously put in this slot.
		**  We found it!
		*/
	        { 
		   return assoc_value;  /* <=========== */
		}

	   /* collision... try next slot in the rehash orbit */
	   rehash = REHASH(rehash,table);
	   goto look_at_slot;		/* <=========== */
	}

  }


} /* end assoc_lookup */


mem_cell
assocn_lookup( string, length, table)
  register char* string;
  register assoc_mem table;
{
  register entry retval;
  int hashval;

  hashn(string, table->mask, length, &hashval);
  
  { register int  rehash = hashval;
    register int * assoc_value = 0;
    
  look_at_slot:
    {  entry * slot = &((*(table->array))[rehash]);
       
       assoc_value = *slot;
       
       if ( (assoc_value) == 0)
	 /* Nothing has hashed to this slot. 
	    Lookup has come to a sorry end. */
	 { 
	   return assoc_value;  /* <=========== */
	 }
       
       if (lstrncmp( string_from_cell(assoc_value,table), string, length) == 0)
	 /*  An identical string was previously put in this slot.
	 **  We found it!
	 */
	 { 
	   return assoc_value;  /* <=========== */
	 }
       
       /* collision... try next slot in the rehash orbit */
       rehash = REHASH(rehash,table);
       goto look_at_slot;		/* <=========== */

     }
    
  }


} /* end assocn_lookup */


mem_cell
assocnf_lookup( string, length, table)
  register char* string;
  register assoc_mem table;
{
  register entry retval;
  int hashval;

  hashnf(string, table->mask, length, &hashval);
  
  { register int  rehash = hashval;
    register int * assoc_value = 0;
    
  look_at_slot:
    {  entry * slot = &((*(table->array))[rehash]);
       
       assoc_value = *slot;
       
       if ( (assoc_value) == 0)
	 /* Nothing has hashed to this slot. 
	    Lookup has come to a sorry end. */
	 { 
	   return assoc_value;  /* <=========== */
	 }
       
       if (lstrncmpf( string_from_cell(assoc_value,table), string, length) == 0)
	 /*  An identical string was previously put in this slot.
	 **  We found it!
	 */
	 { 
	   return assoc_value;  /* <=========== */
	 }
       
       /* collision... try next slot in the rehash orbit */
       rehash = REHASH(rehash,table);
       goto look_at_slot;		/* <=========== */

     }
    
  }


} /* end assocnf_lookup */




/* This routine hashes a string and counts the number of chars in it.   */
/* The hash value is a function of the table size. 			*/

static
hash(string, mask, lenp, hashp)
  char* string;
  int mask;	 /* Is table size minus one. */
  int *lenp;
  int *hashp;

{
  register int len = 0;
  register int hash = 0;
  register char* cursor = string;

  len = 0;
  hash = 0;

  while (*cursor)
	{ len++;
	  hash += ((hash << 1) + *cursor++);
	}
  *hashp = hash & mask;
  *lenp = len;  


} /* hash */

/* Like hash, except for counted (not null-terminated) strings */
static
hashn(string, mask, len, hashp)
  char* string;
  int mask;	 /* Is table size minus one. */
  int len;
  int *hashp;

{
  register int hash = 0;
  register char* cursor = string;

  hash = 0;

  while (len--)
	{
	  hash += ((hash << 1) + *cursor++);
	}
  
  *hashp = hash & mask;

} /* hashn*/
/* Like hash, except for counted (not null-terminated) strings */
/* Folds cases. */
static
hashnf(string, mask, len, hashp)
  char* string;
  int mask;	 /* Is table size minus one. */
  int len;
  int *hashp;

{
  register int hash = 0;
  register char* cursor = string;

  hash = 0;

  while (len--)
	{
	  hash += ((hash << 1) + LOWER(*cursor));
	  cursor++;
	}
  
  *hashp = hash & mask;

} /* hashn*/




/* "Safe" memory allocation routine... zeros out memory obtained. */

static int*
H_getmem(size)
  int size;
{
  int * retval = (int*)calloc(size, sizeof(char));
  if (retval == (int*)0)
    {
	fprintf(PANIC_FILE, "RESOURCE FAILURE: Assoc out of memory. (%d)\n",
		size);
	exitpg(1);
    }
  else return retval;

}






/* When a table becomes half full, we double its size.  (The
** orbit of the rehash function touches exactly half the slots.)
**
*/

static
H_expand_table(table)
  register assoc_mem table;
{
  register hash_table * old_table = table->array;
  register int old_size = table->size;
 
  table->size_div_2 = table->size;
  table->size = table->size * 2;
  table->mask = table->size -1;

  table->array = (hash_table *)H_getmem(table->size * (sizeof (mem_cell)));

  /* Move the members from the old small table to be new big one. */
  { register int recno;

	for (recno = 0; recno < old_size; recno++)
	  if ( (*old_table)[recno] != (entry)0)
		H_reassoc( (*old_table)[recno], table );
  }

  cfree (old_table);
}





/* This routine is a little like assoc. It is used by expand_table() to
** put entries which were in table which overflowed into the new larger one.
** Used by assoc_free() to put entries back into the table which might
** have originally been bumped down the rehash orbit by the entry being
** removed.
*/

static
H_reassoc( rec, table)
  register entry rec;
  register assoc_mem table;
{
  register entry retval;
  register char* string = string_from_cell(rec, table);
  int length;
  int hashval;

  hash(string, table->mask, &length, &hashval);

  { register int  rehash = hashval;

    look_at_slot:
	{  register entry * slot = &((*(table->array))[rehash]);

	   if ( (*slot) == 0)
		{ 
		  *slot = rec;
		  *(mem_from_cell(*slot)) = rehash;

		  return; 	   /* <========= */
		}
	
	   rehash = REHASH(rehash,table);
	   goto look_at_slot;      /* <========= */
	}
    
  }


} /* H_reassoc */




/* This is a sequencer for a table.  You give it a pointer to an
** integer variable which you have initialized to zero, and it gives
** you a member of the table and modifies the variable.  Call it
** again without changing the variable and it gives you the next one, etc...
**
**	{ int handle = 0;
**	  mem_cell member;
**
**	  do { member = assoc_seq(table, &handle);
**	       if (member != NULL) process(member);
**	     }
**	  while (member != NULL);
**	}
**
**
** DO NOT ADD OR DELETE MEMBERS BETWEEN RELATED CALLS TO assoc_seq().
** To do so will wreak non-determinancy if the assoc() caused the
** table to expand, or if the assoc_free() caused a member to be
** moved back up the rehash chain.  You might very easily miss some
** members.
**
*/

mem_cell
assoc_seq(table, num)
  register assoc_mem table;
  register int *num;
{
  register hash_table * hash_tab = table->array;
  register int size = table->size;
 
  /* Standard linear search algorithm looks for next non-empty slot
  ** at index *num or further down.
  */
  for (; (*num) < size; (*num)++)
    if ( (*hash_tab)[*num] != (entry)0)
	{ mem_cell retval = (*hash_tab)[*num];
	  (*num)++;
	  return retval;
	}

  return 0;

}



/*
** This procedure removes a member from a table.
*/

assoc_free(cell, table)
  mem_cell cell;
  assoc_mem table;
{
  /* Invariant: next_slot_num and next_slot point to entries in the rehash
  ** orbit of the cell being removed.  They start out pointing to the
  ** slot of the condemned cell itself:
  */
  register next_slot_num = *(mem_from_cell(cell));
  register entry *next_slot = &((*(table->array))[next_slot_num]);

  /* Remove the condemned cell. */
  free((char *)mem_from_cell(*next_slot));
  *next_slot = 0; /* Splat! got it. */
  table->entries -= 1;

  /* The entry we just removed might have caused some other entries
  ** to be "bumped down the rehash orbit" when they were installed in
  ** the table.  If that was the case, they can not now be found unless
  ** they are moved to their (now) proper position in the table.
  */
   while(
	  next_slot_num = REHASH(next_slot_num,table),
	  next_slot = &((*(table->array))[next_slot_num]),
	  (*next_slot != 0)
	)
     { entry mover = *next_slot;
       *next_slot = 0;
       H_reassoc(mover, table);
     }
  
}/* assoc_free */



/* Deletes a table and returns 0 if the table is empty.
** Does not delete table, but returns number of entries remaining if
** table is not empty.
*/

int
assoc_mem_free(table)
  assoc_mem table;
{
  if (table->entries == 0)
	{  free((char *)table->array);
	   free((char *)table);
	   return 0;
	}
  else return table->entries;

}

/* Deletes all members in a table, then removes the table. */

assoc_mem_remove(table)
  assoc_mem table;
{ register int num = 0;
  register hash_table * hash_tab = table->array;
  register int size = table->size;
 
  for (; (num) < size; (num)++)
    if ( (*hash_tab)[num] != (entry)0)
	{ 
  	    free((char *)mem_from_cell((*hash_tab)[num]));
	}


  free((char *)table->array);
  free((char *)table);

}