smstab.c

基于单片机的 snmp协议解析的一些原代码 给有用的 同行

/*
 * Copyright 1992 SynOptics Communications, Inc.  All Rights Reserved.
 * SynOptics grants a non-exclusive license to use, copy, modify, and
 * distribute this software for any purpose and without fee, provided
 * that this copyright notice and license appear on all copies and
 * supporting documentation.
 * SynOptics makes no representations about the suitability of this
 * software for any particular purpose.  The software is supplied
 * "AS IS", and SynOptics makes no warranty, either express or implied,
 * as to the use, operation, condition, or performance of the software.
 * SynOptics retains all title and ownership in the software.
 *
 * file: SMSTAB.C - String table functions
 *
 * $Revision:   1.2  $ $Date:   08 Jul 1992 17:38:22  $
 * $Log:   R:/MIBTOOLS/V1.0/SMIC/SRC/SMSTAB.C_V  $
 * 
 *    Rev 1.2   08 Jul 1992 17:38:22   gfoster
 * Removed unnecessary revision comment lines added by
 * PVCS to make revision history easier to read.
 * 
 *    Rev 1.1   19 Jun 1992 16:33:34   gfoster
 * Copyright text was reformated.
 *
 *    Rev 1.0   27 May 1992 16:07:28   gfoster
 * Initial revision.
 *
*/


#include <stdio.h>

#ifdef MS_DOS
#include <stdlib.h>
#endif /* MS_DOS */

#include <string.h>

#include "tds.h"
#include "smscdefs.h"
#include "smstdefs.h"
#include "smsydefs.h"
#include "smic.h"


STRTAB *pStrTabRoot;            /* ptr to root of string table */
USHORT usStrTabHeight;          /* heigth of string table */


#define STRACT 100               /* number of string headers to allocate */
STRTAB *pStrAvail;              /* available list ptr to string headers */
USHORT cStrUsed;                /* number of string headers used */
USHORT cStrAlloc;               /* number of string headers allocated */


/** StrTabInsert - search string table and insert name if
*                   not already present.
*
* References: See Knuth "Sorting and Searching" Algorithm A p 455.
*             See Horowitz and Sahni "Data Structures"
*                 program AVL-INSERT p 454.
*
* call with:
*   pszVal - value to insert
*
* returns:
*   pStrTab - addr of node in string table
*/
    STRTAB *
#ifdef __STDC__
StrTabInsert(PSZ pszVal)
#else
StrTabInsert(pszVal)
    PSZ pszVal;
#endif /* __STDC__ */
{
    STRTAB *pBal;               /* balancing point node in tree */
    STRTAB *pBalPar;            /* parent of balancing point node */
    STRTAB *pCur;               /* current node */
    STRTAB *pCurPar;            /* parrent of current node */
    STRTAB *pRot;               /* rotation point */
    STRTAB *pNew;               /* new node */
    register SHORT sCmp;        /* comparison result */
    register SHORT sD;          /* balance flag */



    /* check if tree empty */
    if (pStrTabRoot == NULL) {
    /* get new node, pStrTabRoot is global local */
        pStrTabRoot = StrTabNew();
        pStrTabRoot->pszVal = pszVal;
        usStrTabHeight = 1;
        return(pStrTabRoot);
    }


    /* First Phase: locate inserting point */
    /* Keep track of balancing point node (ie one with sBal = -1 or +1)
       by pBal. pBalPar is parent of balancing point */
    /* pCur and pCurPar move through tree with pCurPar, the parent of pCur */
    pCurPar = (pBalPar = NULL);
    pCur = (pBal = pStrTabRoot);
    while(pCur != NULL) {
        /* check for new balancing point */
        if (pCur->sBal != 0) {
            pBalPar = pCurPar;
            pBal = pCur;
        }
        if ((sCmp = strcmp(pszVal, pCur->pszVal)) < 0) {
            /* take left branch */
            pCurPar = pCur;
            pCur = pCurPar->pLeft;
        } else if (sCmp > 0) {
            /* take right branch */
            pCurPar = pCur;
            pCur = pCurPar->pRight;
        } else {
            /* a match */
            return(pCur);
        }
    }

    /* Second Phase: Insert node as child of pCurPar and rebalance */
    /* get new node, pNew is local */
    pNew = StrTabNew();
    pNew->pszVal = pszVal;

    if (sCmp < 0) {
        /* insert as left child */
        pCurPar->pLeft = pNew;
    } else {
        /* insert as right child */
        pCurPar->pRight = pNew;
    }

    /* Adjust balance factors from pBal to pCurPar. All nodes on this
       path must have balance factors of 0 and so will change to +1 or -1.
       A value of +1 for sD means node inserted on left subtree of pBal.
       A value of -1 for sD means node inserted on right subtree of pBal. */
    if (strcmp(pszVal, pBal->pszVal) < 0) {
        /* left subtree */
        pCur = pBal->pLeft;
        sD = 1;
    } else {
        /* right subtree */
        pCur = pBal->pRight;
        sD = -1;
    }
    pRot = pCur;

    while(pCur != pNew) {
        if (strcmp(pszVal, pCur->pszVal) < 0) {
            /* to left */
            pCur->sBal = 1;
            pCur = pCur->pLeft;
        } else {
            /* to right */
            pCur->sBal = -1;
            pCur = pCur->pRight;
        }
    }

    /* check if still balanced */
    if (pBal->sBal != sD) {
        /* check if gotten more balanced */
        if (pBal->sBal == -sD) {
            /* tree has grown more balanced */
            pBal->sBal = 0;
        } else {
            /* tree still balanced, but has grown in height */
            /* (this only happens when pBal == pStrTabRoot) */
            pBal->sBal = sD;
            usStrTabHeight++;
        }
        return(pNew);
    }
       
    /* tree out of balance, so rotate it */
    /* determine rotation type */
    if (pRot->sBal == sD) {
        /* single rotation */
        if (sD > 0) {
            /* rotate right */
            pBal->pLeft = pRot->pRight;
            pRot->pRight = pBal;
        } else {
            /* rotate left */
            pBal->pRight = pRot->pLeft;
            pRot->pLeft = pBal;
        }
        pBal->sBal = (pRot->sBal) = 0;
    } else {
        /* double rotation */
        if (sD > 0) {
            pCur = pRot->pRight;
            pRot->pRight = pCur->pLeft;
            pCur->pLeft = pRot;
            pBal->pLeft = pCur->pRight;
            pCur->pRight = pBal;
        } else {
            pCur = pRot->pLeft;
            pRot->pLeft = pCur->pRight;
            pCur->pRight = pRot;
            pBal->pRight = pCur->pLeft;
            pCur->pLeft = pBal;
        }
        if (pCur->sBal == sD) {
            pBal->sBal = -sD;
            pRot->sBal = 0;
        } else if (pCur->sBal == -sD) {
            pBal->sBal = 0;
            pRot->sBal = sD;
        } else {
            pBal->sBal = 0;
            pRot->sBal = 0;
        }
        pCur->sBal = 0;
        pRot = pCur;            /* new subtree top */
    }

    /* change ptr to root of new rebalanced subtree */
    if (pBalPar == NULL) {
        /* subtree was the whole tree */
        pStrTabRoot = pRot;
    } else if (pBal == pBalPar->pLeft) {
        /* new left subtree */
        pBalPar->pLeft = pRot;
    } else {
        /* new right subtree */
        pBalPar->pRight = pRot;
    }
    return(pNew);


} /* StrTabInsert */


/** StrTabNew - allocate new string table entry
*
* returns:
*   ptr to new string table node
*
*/

STRTAB *StrTabNew(void)
	{
   STRTAB *pNew;
   int err;

	/* allocate the first item */
   pNew = (STRTAB *)malloc(sizeof(STRTAB));
   if (pNew == NULL)
   	{
      /* out of memory */
      return(NULL);
      }
   else
   	{
      /*
		 * keep the memory allocated on the StrTabAlloc linked list
       * so that later we can free it.
       */
		err = AllocMemAdd(pNew);
      if (err)
      	{
         free(pNew);
         return (NULL);
         }
      else
      	{
         /* initialize */
         pNew->pszVal = NULL;
         pNew->fAccess = 0;
         pNew->sBal = 0;
         pNew->pSym = NULL;
         pNew->pLeft = NULL;
         pNew->pRight = NULL;
      	}
      }
   return(pNew);
	} /* StrTabNew */


#if 0
    STRTAB *
#ifdef __STDC__
StrTabNew(VOID)
#else
StrTabNew()
#endif /* __STDC__ */
{
#ifdef DEBUG
	static int calls = 0;
#endif
    STRTAB *pNew;
    USHORT i;

    /* check if any available */
#ifdef DEBUG
	fprintf(fhMsg, "StrTabNew Call %d\n", ++calls);
#endif
    if (pStrAvail == NULL) {
        /* none available - so allocate some */
        pStrAvail = (STRTAB *)malloc(sizeof(STRTAB)*STRACT);
        if (pStrAvail == NULL) {
            yyerror("StrTabNew: out of heap memory");
            yystats();
            yyterm();
            return(NULL);
        }
        cStrAlloc += STRACT;
#ifdef DEBUG
	fprintf(fhMsg, "cStrAlloc %d\n", cStrAlloc);
#endif
        /* put items in list */
        for (pNew = pStrAvail, i = 1; i < STRACT; i++, pNew++) {
            pNew->pLeft = pNew + 1;
        }
        pNew->pLeft = NULL;
    }

    /* get entry from list */
    pNew = pStrAvail;
    pStrAvail = pStrAvail->pLeft;
    cStrUsed++;

#ifdef DEBUG
	fprintf(fhMsg, "cStrUsed = %d\n", cStrUsed);
#endif

    /* init fields */
    pNew->pszVal = NULL;
    pNew->fAccess = 0;
    pNew->sBal = 0;
    pNew->pSym = NULL;
    pNew->pLeft = NULL;
    pNew->pRight = NULL;

    return(pNew);

} /* StrTabNew */
#endif
/** StrTabInOrder - print out string table in sorted order
*
* call with:
*   pStrTab - subtree of string table
*/
    VOID
#ifdef __STDC__
StrTabInOrder(STRTAB *pCur)
#else
StrTabInOrder(pCur)
    STRTAB *pCur;
#endif /* __STDC__ */
{
    /* check if anything to do */
    if (pCur == NULL)
        return;

    /* do left subtree */
    StrTabInOrder(pCur->pLeft);

    fprintf(fhOut, "\"%s\"\n", pCur->pszVal);

    /* do right subtree */
    StrTabInOrder(pCur->pRight);

} /* StrTabInOrder */


/** StrTabPreOrder - print out string table
*
* call with:
*   pStrTab - subtree of String table
*   usLev - indentation level
*/
    VOID
#ifdef __STDC__
StrTabPreOrder(PSZ pszPos, STRTAB *pCur, USHORT usLev)
#else
StrTabPreOrder(pszPos, pCur, usLev)
    PSZ pszPos;
    STRTAB *pCur;
    USHORT usLev;
#endif /* __STDC__ */
{
    USHORT i;

    if (pCur == NULL)
        return;

    for (i = 0; i < usLev; i++)
        fprintf(fhOut, "  ");

    fprintf(fhOut, "%s: (%d)\"%s\" b=%d\n", pszPos, i+1, pCur->pszVal, pCur->sBal);

    usLev++;
    StrTabPreOrder("Left ", pCur->pLeft, usLev);
    StrTabPreOrder("Right", pCur->pRight, usLev);

} /* StrTabPreOrder */


/** StrTabDump - print out string table in order
*
*/
    VOID
#ifdef __STDC__
StrTabDump(VOID)
#else
StrTabDump()
#endif /* __STDC__ */
{
    fprintf(fhOut, "Tree height is %d\n", usStrTabHeight);

    /* do pre-order traversal */
    StrTabPreOrder(" Root", pStrTabRoot, 0);

    /* do an in-order traversal to print out nodes in order */
    StrTabInOrder(pStrTabRoot);

} /* StrTabDump */


/** StrTabSearch - search string table for specified entry
*
* call with:
*   pszVal - value of string
*
* returns:
*   ptr to entry or NULL if not found
*
*/
    STRTAB *
#ifdef __STDC__
StrTabSearch(PSZ pszVal)
#else
StrTabSearch(pszVal)
    PSZ pszVal;
#endif /* __STDC__ */
{
    STRTAB *pCur;
    register SHORT sCmp;


    /* start at root */
    pCur = pStrTabRoot;

    /* search for match */
    while (pCur != NULL) {
        if ((sCmp = strcmp(pszVal, pCur->pszVal)) == 0) {
            /* a match */
            break;
        }
        if (sCmp < 0) {
            /* item smaller than one in tree, take left branch */
            pCur = pCur->pLeft;
        } else {
            /* item larger than one in tree, take right branach */
            pCur = pCur->pRight;
        }
    }

    return(pCur);

} /* StrTabSearch */

/* free pStrAvail */

/* end of file: SMSTAB.C */