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>
#ifdef SUNOS
#include <varargs.h>
#else
#include <stdarg.h>
#endif
#endif
#include "script.h"
#include "debug.h"
#include <limits.h>

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

static ReturnCode INLINE InitHash(struct Data *);
static unsigned long INLINE Gethash(uchar *);
static void * INLINE Init(struct Data *, long ASM (*)(AREG(0) void *), unsigned long *);
static ReturnCode REGARGS SetTags(struct Data *, unsigned long *);
static ReturnCode INLINE Hijack(struct Data *, struct Identifier *);
static ReturnCode REGARGS AddIdentifier(struct Data *, struct Identifier *);


ReturnCode REGARGS
    RenameIdentifier(struct Data *scr,
		     struct Identifier *ident, /* existing identifier */
		     uchar *newname)           /* new name */
{
    ReturnCode ret;
    struct Identifier *nident;
    ret = GetIdentifier(scr, newname, &nident);
    if(ret != FPLERR_IDENTIFIER_NOT_FOUND) {
      return FPLERR_IDENTIFIER_USED; /* !!! */
    }

    if(ident->flags&FPL_KEYWORD ||
       !(ident->flags&(FPL_EXTERNAL_FUNCTION|FPL_EXPORT_SYMBOL))) {
      /*
       * Nonononono... we have to draw the limit somewhere!!!
       */
      return FPLERR_IDENTIFIER_USED;
    }
    /*
     * Let's take the old one out of its chains!
     */
    if(ident->prev) {
      /* If there is a previous member */
      ident->prev->next=ident->next;
    }
    else {
      /* if this was the first in the list */
      scr->hash[ident->hash%scr->hash_size]=ident->next;
    }
    if(ident->next) {
      ident->next->prev=ident->prev;
    }
    if(ident->flags&(FPL_INTERNAL_FUNCTION|FPL_EXTERNAL_FUNCTION)) {
      if(ident->flags&FPL_DEALLOC_NAME_ANYWAY) {
        /* Oh well, this has already been renamed once! */
        FREE_KIND(ident->name);
      }
      else
        ident->flags |= FPL_DEALLOC_NAME_ANYWAY;
        /* this have to be known since this kind of functions regularly uses
           names in the user-area which never get freed by us! */
    }
    else {
      FREE_KIND(ident->name);
    }
    STRDUPA(ident->name, newname);
    CALL( AddIdentifier(scr, ident));
    return ret;
}

#ifndef AMIGA /* if not using SAS/C on Amiga */

#ifdef VARARG_FUNCTIONS
long fplAddFunctionTags(void *anchor, uchar *name, long ID, uchar rtrn,
                        uchar *format, ...)
{
  va_list tags;
  long ret;
#ifdef SUNOS
  va_start(tags); /* get parameter list */
#else
  va_start(tags, format); /* get parameter list */
#endif
  ret = fplAddFunction(anchor, name, ID, rtrn, format, (unsigned long *)tags);
  va_end(tags);
  return ret;
}
#else
long PREFIX fplAddFunctionTags(void *anchor, uchar *name, long ID, uchar rtrn,
                               uchar *format, unsigned long tags, ...)
{
  return(fplAddFunction(anchor, name, ID, rtrn, format, &tags));
}
#endif

#endif

/**********************************************************************
 *
 * int fplAddFunction();
 *
 * User frontend to AddIdentifier().
 *
 *****/

ReturnCode PREFIX
  fplAddFunction(AREG(0) struct Data *scr,      /* pointer to struct Data */
		 AREG(1) uchar *name,     /* name of function */
		 DREG(0) long ID,	 /* function ID */
		 DREG(1) uchar rtrn,      /* return type */
		 AREG(2) uchar *format,   /* format string */
		 AREG(3) unsigned long *tags) /* taglist pointer */
{
  ReturnCode ret;
  struct Identifier *ident;
#ifdef DEBUGMAIL
  DebugMail(scr, MAIL_FUNCTION, 500, "fplAddFunction");
#endif
  if(!scr)
    return(FPLERR_ILLEGAL_ANCHOR);

  ident=MALLOCA(sizeof(struct Identifier));
  if(!ident)
    return(FPLERR_OUT_OF_MEMORY);

  memset(&ident->data.external, 0, sizeof(struct ExternalFunction));
  while(tags && *tags) {
    switch(*tags++) {
    case FPLTAG_USERDATA:
      ident->data.external.data=(void *)*tags;
      break;
    case FPLTAG_FUNCTION:
      ident->data.external.func=(long (*)(void *))*tags;
      break;
    }
    tags++; /* next! */
  }

  ident->name = name;
  ident->data.external.ID = ID;
  ident->data.external.ret = rtrn;
  ident->data.external.format = format;
  ident->flags = FPL_EXTERNAL_FUNCTION|FPL_GLOBAL_SYMBOL|FPL_EXPORT_SYMBOL;
  ident->file = "<user>"; /* User added! */
  ident->func = NULL; /* everywhere! */
  ident->level = 0;

  CALL(AddIdentifier(scr, ident));
  return(FPL_OK);
}

/**********************************************************************
 *
 * int fplDelFunction();
 *
 * User frontend to DelIdentifier().
 *
 ******/

ReturnCode PREFIX fplDelFunction(AREG(0) struct Data *scr,
				 AREG(1) uchar *name)
{
  ReturnCode ret;
#ifdef DEBUGMAIL
  DebugMail(scr, MAIL_FUNCTION, 500, "fplDelFunction");
#endif
  if(!scr)
    return(FPLERR_ILLEGAL_ANCHOR);
  CALL(DelIdentifier(scr, name, NULL));
  return(FPL_OK);
}


/**********************************************************************
 *
 * int AddToList();
 *
 * Add the ident pointer the Local list.
 *
 *********************************************************************/
ReturnCode REGARGS
AddToList(struct Data *scr, /* pointer to struct Data */
          struct Identifier *ident,/* identifier struct pointer */
          struct Local **local)
{
  struct Local *temp;
  GETMEM(temp, sizeof(struct Local));  
  temp->next=*local;
  temp->ident=ident;
  *local=temp;
  return FPL_OK;
}

/**********************************************************************
 *
 * 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)
{
  ReturnCode ret;
  if(ret=AddIdentifier(scr, ident))
    ;
  else {
    ret = AddToList(scr, ident, local);
  }
  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!
 *
 *****/

ReturnCode REGARGS
DelLocalVar(struct Data *scr,
            struct Local **local)
{
  /* This removes only all listed symbols! */
  struct Identifier *ident;
  while(*local) {
    struct Local *temp=(*local)->next;
    ident=(*local)->ident;
    FREE(*local);
    *local=temp;
    if(ident)
      DelIdentifier(scr, NULL, ident); /* delete it for real */
    else
      break;
  }
  return(FPL_OK);
}


/**********************************************************************
 *
 * 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...
 *
 *******/

ReturnCode REGARGS static
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 % scr->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)
{