hash.c

早期freebsd实现

 *
 * Grow a new (bigger) hash table from the old one.
 * We choose to double the hash table's size.
 * Return a human-scrutible error string: "" if OK.
 * Warning! This uses hash_jam(), which had better not recurse
 * back here! Hash_jam() conditionally calls us, but we ALWAYS
 * call hash_jam()!
 * Internal.
 */
static char *
hash_grow(handle)			/* make a hash table grow */
     struct hash_control * handle;
{
  register struct hash_entry *      newwall;
  register struct hash_entry *      newwhere;
  struct hash_entry *      newtrack;
  register struct hash_entry *      oldtrack;
  register struct hash_entry *      oldwhere;
  register struct hash_entry *      oldwall;
  register int                      temp;
  int                      newsize;
  char *                   string;
  char *                   retval;
#ifdef SUSPECT
  int                      oldused;
#endif

  /*
   * capture info about old hash table
   */
  oldwhere = handle -> hash_where;
  oldwall  = handle -> hash_wall;
#ifdef SUSPECT
  oldused  = handle -> hash_stat[STAT_USED];
#endif
  /*
   * attempt to get enough room for a hash table twice as big
   */
  temp = handle->hash_stat[STAT_SIZE];
  if ( newwhere = (struct hash_entry *) xmalloc((long)((temp+temp+1)*sizeof(struct hash_entry))))
				/* +1 for wall slot */
    {
      retval = "";		/* assume success until proven otherwise */
      /*
       * have enough room: now we do all the work.
       * double the size of everything in handle,
       * note: hash_mask frob works for 1's & for 2's complement machines
       */
      handle->hash_mask              = handle->hash_mask + handle->hash_mask + 1;
      handle->hash_stat[STAT_SIZE] <<= 1;
      newsize                        = handle->hash_stat[STAT_SIZE];
      handle->hash_where             = newwhere;
      handle->hash_full            <<= 1;
      handle->hash_sizelog	    += 1;
      handle->hash_stat[STAT_USED]   = 0;
      handle->hash_wall              =
      newwall                        = newwhere + newsize;
      /*
       * set all those pesky new slots to vacant.
       */
      for (newtrack=newwhere; newtrack <= newwall; newtrack++)
	{
	  newtrack -> hash_string = NULL;
	}
      /*
       * we will do a scan of the old table, the hard way, using the
       * new control block to re-insert the data into new hash table.
       */
      handle -> hash_stat[STAT_USED] = 0;	/* inserts will bump it up to correct */
      for (oldtrack=oldwhere; oldtrack < oldwall; oldtrack++)
	{
	  if ( (string=oldtrack->hash_string) && string!=DELETED )
	    {
	      if ( * (retval = hash_jam(handle,string,oldtrack->hash_value) ) )
		{
		  break;
		}
	    }
	}
#ifdef SUSPECT
      if ( !*retval && handle->hash_stat[STAT_USED] != oldused)
	{
	  retval = "hash_used";
	}
#endif
      if (!*retval)
	{
	  /*
	   * we have a completely faked up control block.
	   * return the old hash table.
	   */
	  free((char *)oldwhere);
	  /*
	   * Here with success. retval is already "".
	   */
	}
    }
  else
    {
      retval = "no room";
    }
  return(retval);
}

/*
 *          h a s h _ a p p l y ( )
 *
 * Use this to scan each entry in symbol table.
 * For each symbol, this calls (applys) a nominated function supplying the
 * symbol's value (and the symbol's name).
 * The idea is you use this to destroy whatever is associted with
 * any values in the table BEFORE you destroy the table with hash_die.
 * Of course, you can use it for other jobs; whenever you need to
 * visit all extant symbols in the table.
 *
 * We choose to have a call-you-back idea for two reasons:
 *  asthetic: it is a neater idea to use apply than an explicit loop
 *  sensible: if we ever had to grow the symbol table (due to insertions)
 *            then we would lose our place in the table when we re-hashed
 *            symbols into the new table in a different order.
 *
 * The order symbols are visited depends entirely on the hashing function.
 * Whenever you insert a (symbol, value) you risk expanding the table. If
 * you do expand the table, then the hashing function WILL change, so you
 * MIGHT get a different order of symbols visited. In other words, if you
 * want the same order of visiting symbols as the last time you used
 * hash_apply() then you better not have done any hash_insert()s or
 * hash_jam()s since the last time you used hash_apply().
 *
 * In future we may use the value returned by your nominated function.
 * One idea is to abort the scan if, after applying the function to a
 * certain node, the function returns a certain code.
 * To be safe, please make your functions of type char *. If you always
 * return NULL, then the scan will complete, visiting every symbol in
 * the table exactly once. ALL OTHER RETURNED VALUES have no meaning yet!
 * Caveat Actor!
 *
 * The function you supply should be of the form:
 *      char * myfunct(string,value)
 *              char * string;        |* the symbol's name *|
 *              char * value;         |* the symbol's value *|
 *      {
 *        |* ... *|
 *        return(NULL);
 *      }
 *
 * The returned value of hash_apply() is (char*)NULL. In future it may return
 * other values. NULL means "completed scan OK". Other values have no meaning
 * yet. (The function has no graceful failures.)
 */
char *
hash_apply(handle,function)
     struct hash_control * handle;
     char*                 (*function)();
{
  register struct hash_entry *      entry;
  register struct hash_entry *      wall;

  wall = handle->hash_wall;
  for (entry = handle->hash_where; entry < wall; entry++)
    {
      if (islive(entry))	/* silly code: tests entry->string twice! */
	{
	  (*function)(entry->hash_string,entry->hash_value);
	}
    }
  return (NULL);
}

/*
 *          h a s h _ f i n d ( )
 *
 * Given symbol string, find value (if any).
 * Return found value or NULL.
 */
char *
hash_find(handle,string)	/* return char* or NULL */
     struct hash_control * handle;
     char *                string;
{
  register struct hash_entry *      entry;
  register char *                   retval;

  entry = hash_ask(handle,string,STAT__READ);
  if (hash_found)
    {
      retval = entry->hash_value;
    }
  else
    {
      retval = NULL;
    }
  return(retval);
}

/*
 *          h a s h _ a s k ( )
 *
 * Searches for given symbol string.
 * Return the slot where it OUGHT to live. It may be there.
 * Return hash_found: TRUE only if symbol is in that slot.
 * Access argument is to help keep statistics in control block.
 * Internal.
 */
static struct hash_entry *	/* string slot, may be empty or deleted */
hash_ask(handle,string,access)
     struct hash_control * handle;
     char *                string;
     int                   access; /* access type */
{
  register char	*string1;	/* JF avoid strcmp calls */
  register char *                   s;
  register int                      c;
  register struct hash_entry *      slot;
  register int                      collision; /* count collisions */

  slot = handle->hash_where + hash_code(handle,string); /* start looking here */
  handle->hash_stat[STAT_ACCESS+access] += 1;
  collision = 0;
  hash_found = FALSE;
  while ( (s = slot->hash_string) && s!=DELETED )
    {
    	for(string1=string;;) {
		if(!(c= *s++)) {
			if(!*string1)
				hash_found = TRUE;
			break;
		}
		if(*string1++!=c)
			break;
	}
	if(hash_found)
		break;
      collision++;
      slot++;
    }
  /*
   * slot:                                                      return:
   *       in use:     we found string                           slot
   *       at empty:
   *                   at wall:        we fell off: wrap round   ????
   *                   in table:       dig here                  slot
   *       at DELETED: dig here                                  slot
   */
  if (slot==handle->hash_wall)
    {
      slot = handle->hash_where; /* now look again */
      while( (s = slot->hash_string) && s!=DELETED )
	{
	  for(string1=string;*s;string1++,s++) {
	    if(*string1!=*s)
		break;
	  }
	  if(*s==*string1) {
	      hash_found = TRUE;
	      break;
	    }
	  collision++;
	  slot++;
	}
      /*
       * slot:                                                   return:
       *       in use: we found it                                slot
       *       empty:  wall:         ERROR IMPOSSIBLE             !!!!
       *               in table:     dig here                     slot
       *       DELETED:dig here                                   slot
       */
    }
/*   fprintf(stderr,"hash_ask(%s)->%d(%d)\n",string,hash_code(handle,string),collision); */
  handle -> hash_stat[STAT_COLLIDE+access] += collision;
  return(slot);			/* also return hash_found */
}

/*
 *           h a s h _ c o d e
 *
 * Does hashing of symbol string to hash number.
 * Internal.
 */
static int
hash_code(handle,string)
     struct hash_control * handle;
     register char *                string;
{
  register long int                 h;      /* hash code built here */
  register long int                 c;      /* each character lands here */
  register int			   n;      /* Amount to shift h by */

  n = (handle->hash_sizelog - 3);
  h = 0;
  while (c = *string++)
    {
      h += c;
      h = (h<<3) + (h>>n) + c;
    }
  return (h & handle->hash_mask);
}

/*
 * Here is a test program to exercise above.
 */
#ifdef TEST

#define TABLES (6)		/* number of hash tables to maintain */
				/* (at once) in any testing */
#define STATBUFSIZE (12)	/* we can have 12 statistics */

int statbuf[STATBUFSIZE];	/* display statistics here */
char answer[100];		/* human farts here */
char * hashtable[TABLES];	/* we test many hash tables at once */
char * h;			/* points to curent hash_control */
char ** pp;
char *  p;
char *  name;
char *  value;
int     size;
int     used;
char    command;
int     number;			/* number 0:TABLES-1 of current hashed */
				/* symbol table */

main()
{
  char (*applicatee());
  char * hash_find();
  char * destroy();
  char * what();
  struct hash_control * hash_new();
  char * hash_replace();
  int *  ip;

  number = 0;
  h = 0;
  printf("type h <RETURN> for help\n");
  for(;;)
    {
      printf("hash_test command: ");
      gets(answer);
      command = answer[0];
      if (isupper(command)) command = tolower(command);	/* ecch! */
      switch (command)
	{
	case '#':
	  printf("old hash table #=%d.\n",number);
	  whattable();
	  break;
	case '?':
	  for (pp=hashtable; pp<hashtable+TABLES; pp++)
	    {
	      printf("address of hash table #%d control block is %xx\n"
		     ,pp-hashtable,*pp);
	    }
	  break;
	case 'a':
	  hash_apply(h,applicatee);
	  break;
	case 'd':
	  hash_apply(h,destroy);
	  hash_die(h);
	  break;
	case 'f':
	  p = hash_find(h,name=what("symbol"));
	  printf("value of \"%s\" is \"%s\"\n",name,p?p:"NOT-PRESENT");
	  break;
	case 'h':
	  printf("# show old, select new default hash table number\n");
	  printf("? display all hashtable control block addresses\n");
	  printf("a apply a simple display-er to each symbol in table\n");
	  printf("d die: destroy hashtable\n");
	  printf("f find value of nominated symbol\n");
	  printf("h this help\n");
	  printf("i insert value into symbol\n");
	  printf("j jam value into symbol\n");
	  printf("n new hashtable\n");
	  printf("r replace a value with another\n");
	  printf("s say what %% of table is used\n");
	  printf("q exit this program\n");
	  printf("x delete a symbol from table, report its value\n");
	  break;
	case 'i':
	  p = hash_insert(h,name=what("symbol"),value=what("value"));
	  if (*p)
	    {
	      printf("symbol=\"%s\"  value=\"%s\"  error=%s\n",name,value,p);
	    }
	  break;
	case 'j':
	  p = hash_jam(h,name=what("symbol"),value=what("value"));
	  if (*p)
	    {
	      printf("symbol=\"%s\"  value=\"%s\"  error=%s\n",name,value,p);
	    }
	  break;
	case 'n':
	  h = hashtable[number] = (char *) hash_new();
	  break;
	case 'q':
	  exit();
	case 'r':
	  p = hash_replace(h,name=what("symbol"),value=what("value"));
	  printf("old value was \"%s\"\n",p?p:"{}");
	  break;
	case 's':
	  hash_say(h,statbuf,STATBUFSIZE);
	  for (ip=statbuf; ip<statbuf+STATBUFSIZE; ip++)
	    {
	      printf("%d ",*ip);
	    }
	  printf("\n");
	  break;
	case 'x':
	  p = hash_delete(h,name=what("symbol"));
	  printf("old value was \"%s\"\n",p?p:"{}");
	  break;
	default:
	  printf("I can't understand command \"%c\"\n",command);
	  break;
	}
    }
}

char *
what(description)
     char * description;
{
  char * retval;
  char * malloc();

  printf("   %s : ",description);
  gets(answer);
  /* will one day clean up answer here */
  retval = malloc(strlen(answer)+1);
  if (!retval)
    {
      error("room");
    }
  (void)strcpy(retval,answer);
  return(retval);
}

char *
destroy(string,value)
     char * string;
     char * value;
{
  free(string);
  free(value);
  return(NULL);
}


char *
applicatee(string,value)
     char * string;
     char * value;
{
  printf("%.20s-%.20s\n",string,value);
  return(NULL);
}

whattable()			/* determine number: what hash table to use */
				/* also determine h: points to hash_control */
{

  for (;;)
    {
      printf("   what hash table (%d:%d) ?  ",0,TABLES-1);
      gets(answer);
      sscanf(answer,"%d",&number);
      if (number>=0 && number<TABLES)
	{
	  h = hashtable[number];
	  if (!h)
	    {
	      printf("warning: current hash-table-#%d. has no hash-control\n",number);
	    }
	  return;
	}
      else
	{
	  printf("invalid hash table number: %d\n",number);
	}
    }
}



#endif /* #ifdef TEST */

/* end: hash.c */