hash.c

类PASCAL语言的编译器,LINUX环境的,我没试过是否正确.

/******************************************************************************
 *		           FREXX PROGRAMMING LANGUAGE    		      *
 ******************************************************************************

 hash.c

 Functions for FPL hash tables and sorting!

 *****************************************************************************/

/************************************************************************
 *                                                                      *
 * fpl.library - A shared library interpreting script langauge.         *
 * Copyright (C) 1992-1994 FrexxWare                                    *
 * Author: Daniel Stenberg                                              *
 *                                                                      *
 * This program is free software; you may redistribute for non          *
 * commercial purposes only. Commercial programs must have a written    *
 * permission from the author to use FPL. FPL is *NOT* public domain!   *
 * Any provided source code is only for reference and for assurance     *
 * that users should be able to compile FPL on any operating system     *
 * he/she wants to use it in!                                           *
 *                                                                      *
 * You may not change, resource, patch files or in any way reverse      *
 * engineer anything in the FPL package.                                *
 *                                                                      *
 * This program is distributed in the hope that it will be useful,      *
 * but WITHOUT ANY WARRANTY; without even the implied warranty of       *
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.                 *
 *                                                                      *
 * Daniel Stenberg                                                      *
 * Ankdammsgatan 36, 4tr                                                *
 * S-171 43 Solna                                                       *
 * Sweden                                                               *
 *                                                                      *
 * FidoNet 2:201/328    email:[e-mail]                       *
 *                                                                      *
 ************************************************************************/

#ifdef AMIGA
#include <exec/types.h>
#include <proto/exec.h>
#include <dos.h>
#else
#include <stdio.h>
#endif
#include "script.h"
#include <limits.h>

#ifdef DEBUG
#include <stdio.h>
#endif

static long IdentNumber=0; /* identifier number to increase at every declaration */

static ReturnCode REGARGS AddIdentifier(struct Data *, struct Identifier *);
static ReturnCode INLINE InitHash(struct Data *);
static void * INLINE Init(struct Data *scr, long*);

/**********************************************************************
 *
 * int AddVar();
 *
 * Frontend to the AddIdentifier function.
 *
 * This routine adds a member to the linked list of local variable names.
 * That list exists to enable easy and fast removal of local variables
 * when leaving a block within which local variables has been declared!
 *
 * Make sure that the name member data is static as long we need this list
 * cause this routine doesn't copy that name, simply points to it!
 *
 *****/


ReturnCode REGARGS
AddVar(struct Data *scr, /* pointer to struct Data */
       struct Identifier *ident,/* identifier struct pointer */
       struct Local **local,
       uchar output)
{
  ReturnCode ret;
  struct Local *temp;
  if(ret=AddIdentifier(scr, ident))
    INFO(scr, CERROR_IDENTIFIER_USED, ident->name);
  else {
    GETMEM(temp, sizeof(struct Local));  
    temp->next=*local;
    temp->ident=ident;
    *local=temp;

    scr->currvariables++; /* increase number of current symbols */
    scr->totalvariables++; /* increase total number of symbols */
    ident->number= ++IdentNumber;
    if(output) {
      CALL(PutArg(scr, COMP_DECLARE, ident->flags));
      if(!(ident->flags&FPL_EXPORT_SYMBOL)) {
        CALL(PutArg(scr, COMP_NOTHING, ident->number));
      }
      else {
        CALL(PutArg(scr, COMP_NOTHING, ident->hash));
      }
      CALL(PutString(scr, COMP_NOTHING, ident->name, -1));
    }
  }
  return(ret);
}

/**********************************************************************
 *
 * AddLevel();
 *
 * This function adds a NULL-name in the local symbol list to visualize
 * the beginning of a new variable level!
 *
 *******/

ReturnCode REGARGS
AddLevel(struct Data *scr)
{
  struct Local *temp;
  GETMEM(temp, sizeof(struct Local));  
  temp->next=scr->locals;
  temp->ident=NULL;
  scr->locals=temp;
  return(FPL_OK);
}


/**********************************************************************
 *
 * int DelLocalVar()
 *
 * This routine deletes all members to the linked list of local variable
 * names. Call this routine every time you leave a local level. Deletes
 * all variables and the following NULL name!
 *
 *****/

long REGARGS
DelLocalVar(struct Data *scr,
            struct Local **local)
{
  /* This removes only all listed symbols! */
  long deleted=0;
  struct Identifier *ident;
  while(*local) {
    struct Local *temp=(*local)->next;
    ident=(*local)->ident;
    FREE(*local);
    *local=temp;
    if(ident) {
      deleted++;
      scr->currvariables--; /* count down the current amount */
      DelIdentifier(scr, NULL, ident); /* delete it for real */
    }
    else
      break;
  }
  return deleted;
}


/**********************************************************************
 *
 * int AddIdentifier()
 *
 * This function adds the function to the hash table according to all
 * parameters.
 *
 * If the hash member of the Data structure is NULL, the hash table
 * will be inited. No not init the hash list if you don't have to cause
 * that sure is a peep hole in the performance...
 *
 *******/

static ReturnCode REGARGS
AddIdentifier(struct Data *scr,
              struct Identifier *ident)
{
  unsigned long hash;       /* hash number of the identifier */
  struct Identifier **add;  /* where to store the pointer to this identifier */
  struct Identifier *prev=NULL; /* pointer to previous hash structure */
  struct Identifier *next;  /* pointer to next hash structure */
  hash=Gethash(ident->name);
  
  add=(struct Identifier **)&scr->hash[hash % FPL_HASH_SIZE];
  while(*add) {
    if((*add)->hash==hash) {
      /* they were identical */
      if(ident->flags&FPL_FUNCTION &&
	 !strcmp((*add)->name, ident->name) &&
/*
  PREV STOOPID WAY:
	 (!ident->file || !strcmp(ident->file, (*add)->file))) { */

	 (ident->flags&FPL_EXPORT_SYMBOL || !strcmp(ident->file, (*add)->file))) {
	/* if it's already there, fail!!! */
	return FPLERR_IDENTIFIER_USED;
      } else
	/* add it here! */
	break; 
    } else if((*add)->hash>hash) {
      /* continue search for a place to insert */
      /* 'add' now points to the pointer */
      prev=(*add);
      add=(struct Identifier **)&((*add)->next);
    } else {
      /* insert it here! */
      prev=(*add)->prev;
      break;
    }
  }

  next=(*add);
  *add=ident;
  (*add)->hash=hash;
  (*add)->prev=prev;
  (*add)->next=next;
  if(next)
    next->prev=ident;
  return(FPL_OK);
}

/**********************************************************************
 *
 * int GetIdentifier();
 *
 * Sets the pointer to the Identifier structure to which the name
 * fits, in the third argument.
 *
 *****/

#ifdef DEBUG
int hashed=0;
int max_hashed=0;
#endif

ReturnCode REGARGS
GetIdentifier(struct Data *scr,
              uchar *name,
	      struct Identifier **ident)
{
  struct Identifier *get;
  unsigned long hash=Gethash(name);
  get=scr->hash[hash%FPL_HASH_SIZE];
#ifdef DEBUG
  hashed=0;
#endif

  while(get) {
    if(

       (get->hash==hash) && 
       /* identical hash value! */

       !strcmp(get->name, name) &&
       /* identical name! */

       (get->flags&(FPL_GLOBAL_SYMBOL|FPL_EXPORT_SYMBOL) ||
        (get->func==scr->func && get->level<=scr->varlevel))
       /* If not global, declared under the *same* function, in this or
	  a lower level! */

       ) {

      /* this is it! */
      *ident=get;
#ifdef DEBUG
      if(hashed>max_hashed)
	max_hashed=hashed;
#endif
      return(FPL_OK);
    } else if(get->hash<hash)
      /* we've been searching through all possible alternatives! */
      break;
#ifdef DEBUG
    hashed++;
#endif
    get=get->next;
  }    
  *ident=NULL;
  return(FPLERR_IDENTIFIER_NOT_FOUND);
}


/**********************************************************************