osptransids.c

radius协议源码÷The Radius Stack will connect to a Radius Server. This stack implementation is built upo

/* osptransids.c: 
*/
/*
###########################################################################
###########################################################################
###########################################################################
###                                                                     ###
###   COPYRIGHT (c) 1999 by TransNexus, LLC                             ###
###                                                                     ###
###   This software contains proprietary and confidential information   ###
###   of TransNexus, LLC. Except as may be set forth in the license     ###
###   agreement under which this software is supplied, use, disclosure, ###
###   or reproduction is prohibited without the prior, express, written ###
###   consent of TransNexus, LLC.                                       ###
###                                                                     ###
###########################################################################
###########################################################################
###########################################################################
*/

/*
 *
 *
 *           OVERALL DESIGN STRATEGY
 *
 *           Transaction ID's are stored in two parallel
 *           structures -- a binary tree and a doubly-linked
 *           list. The binary tree organizes the IDs by
 *           their value. Its purpose is to quickly search
 *           for a particular ID value. A binary tree is
 *           efficient for two reasons:
 *
 *             1) Nearly all attempts to search for an
 *                ID should fail. If a search does succeed,
 *                it means that a duplicate ID had been
 *                detected, and that *should* never happen.
 *                Since most searches are expected to end
 *                in "failure", simpler data structures
 *                that force an exhaustive search would
 *                be particularly costly.
 *
 *             2) By nature of their Hamming coding, ID
 *                values are essentially random. Trees
 *                built from these values should therefore
 *                be relatively balanced. There is no
 *                need, consequently, to explicitly balance
 *                the data a la AVL trees.
 *
 *           The second parallel data structure -- a doubly-
 *           linked list -- sorts the transaction IDs by
 *           their expiration time. A doubly-linked list
 *           is efficient for this operation because:
 *
 *             1) Transaction IDs should be added to the
 *                list in order (more or less). In other
 *                words, each additional ID is likely to
 *                be newer than all previously added IDs.
 *                Keeping the list sorted, therefore, should
 *                be relatively inexpensive. (Note, though,
 *                that the order in which IDs are added is
 *                only approximately sorted, so some manual
 *                sorting in these routines is still essential.)
 *
 *             2) Only the oldest Transaction is removed
 *                from the list. This is true in the strictest
 *                sense, making a linked list (provided it
 *                maintains pointers to its head and tail)
 *                perfect for the removal operation.
 *
 *             3) Because IDs are added in nearly sorted order,
 *                binary tree-based structures are likely to be
 *                very unbalanced, and explicitly balanced
 *                trees (e.g. AVL trees) are likely to require
 *                relatively significant CPU cycles to balance.
 *
 *             4) Double links are needed (instead of a single
 *                link) because of the complications of
 *                removing a node from a binary tree. (Since
 *                the tree and list data structures are
 *                parallel, every node simultaneously exists
 *                on both structures.) See the binary tree
 *                deletion routine for details.
 *
 *           IMPLEMENTATION ISSUES
 *
 *           The binary tree stuff is pretty straightforward
 *           (check out any decent Algorithms text), but the
 *           linked list might seem a bit unusual to some.
 *           (It's still pretty standard, though.) The
 *           list uses a dummy node for a sentinel instead
 *           of explicit head (and/or tail) pointers. Using
 *           a sentinel makes insertions and deletions a
 *           lot cleaner, since we don't have to check for
 *           those messy boundary conditions where pointers
 *           are equal to null. It does mean, though, that
 *           the list must be explicitly initialized before
 *           it can be used.
 *
 *           The last (e.g. newest) node in the list is set
 *           so that its newer pointer points to the sentinel,
 *           and the sentinel's own newer pointer points to
 *           the first (oldest) node in the list. Similarly,
 *           the first node's older pointer points to the
 *           sentinel, and the sentinel's older pointer points
 *           to the last node in the list. This makes it easy
 *           to find both the head or the tail of the list
 *           through the sentinel. The following picture shows
 *           the organization:
 *
 *
 *                             SENTINEL <-------------+
 *                            [=======]               |
 *                            [ xx:xx ]               |
 *            +-------------> [ older ] -------+      |
 *            |      +------- [ newer ]        |      |
 *            |      |        [=======]        |      |
 *            |      |                         |      |
 *            |      v                         V      |
 *            |  [=======]    [=======]    [=======]  |
 *            |  [ 01:00 ]    [ 02:00 ]    [ 03:00 ]  |
 *            +- [ older ] <- [ older ] <- [ older ]  |
 *               [ newer ] -> [ newer ] -> [ newer ] -+
 *               [=======]    [=======]    [=======]
 *
 *
 *           DEBUGGING ISSUES
 *
 *           Moderately liberal use of assertions throughout
 *           these routines. In the author's experience,
 *           asserts are extremely valuable in debugging
 *           complex data structures like trees and lists
 *           because they allow you to detect a corrupt
 *           structure just about as soon as possible. If
 *           you suspect problems with the routines, be
 *           sure to compile with appropriate DEBUG flags
 *           to enable the assert statements. (Check your
 *           compiler for details, ANSI standard is to
 *           undefine NDEBUG.)
 *
 *           MULTI-THREADING IMPLICATIONS
 *
 *           The functions, as currently written, are not
 *           thread-safe at all. Making them thread-safe,
 *           however, is a relatively simple task, and the
 *           code includes comments that indicate where
 *           multi-threading support (mainly semaphore
 *           locking and unlocking) should go. The current
 *           code omits the actual semaphore function calls
 *           so as to maintain maximum clarity and portability.
 *           Actual implementations must replace the comments
 *           below with actual calls to the environment's
 *           appropriate semaphore mechanisms.
 */

#include "osptransids.h"
#include "ospprovider.h"

/*-----------------------------------------------------------------------*/
/* OSPPTransIdAdd - add a transaction ID to the ordered tree */

OSPTBOOL                                /* returns false if duplicate */
OSPPTransIdAdd
(
    OSPTTRANSID     *ospvTransId,   /* transaction ID to add */
    OSPTPROVIDER    *ospvProvider
)
{
    OSPTTRANSID **root      = OSPC_OSNULL;


    /* check to make sure the transaction ID structure is clean */
    if(!(ospvTransId->ospmTransactionIdLessPtr == 0) ||
       !(ospvTransId->ospmTransactionIdMorePtr == 0))
    {
        return OSPC_FALSE;        
    }

    /*
     * Pretty much a standard, non-recursive binary tree algorithm.
     * We start looking at the root of the tree and keep following
     * down until we reach the place to add the new node. The
     * variable ppRoot keeps track of where we are in the tree. When
     * it's value is zero, we're there.
     */

    root = OSPPProviderGetTransIdRoot(ospvProvider);

    while (*root != 0)
    {

        if (ospvTransId->ospmTransactionId < (*root)->ospmTransactionId)
        {
            /*
             * We're not at the end of the tree yet, so we have to
             * keep searching. In this case, the node to be added
             * is numerically less than the current root, so we
             * need to continue looking down the "Less" side of
             * of the tree.
             */
        
            root= &((*root)->ospmTransactionIdLessPtr);
        }
        else if (ospvTransId->ospmTransactionId > (*root)->ospmTransactionId)
        {
            /*
             * This is the same as the previous case, except that
             * the node being added is numerically greater than the
             * current root. In this case, we keep looking on the
             * "More" side of the tree.
             */
 
            root = &((*root)->ospmTransactionIdMorePtr);
        }
        else
        {
            /*
             * This isn't *supposed* to happen, but we've found a duplicate
             * node already in the tree. Our response is to return false.
             */
       
            return(OSPC_FALSE);
        }
    }

    /*
     * We've reached the end of the tree in our current search,
     * so this is where we want to add the new node. A simple
     * assignment will do.
     *
     * If this is the first item to be added, then ppRoot will
     * point to the absolute root of the tree and we'll be
     * updating that root. Otherwise, root will point to
     * a child pointer (either Less or More) in an existing
     * node, and we'll update that node's pointer.
     */
         
    *root = ospvTransId;
    ospvTransId->ospmTransactionIdParent = root;

    /* since everything's okay, return true */
    return(OSPC_TRUE);

}

/*-----------------------------------------------------------------------*/
/* OSPPTransIdCheckAndAdd - add a transaction ID, as long as it's unique */

OSPTBOOL                            /* returns false if addition fails */
OSPPTransIdCheckAndAdd
(
    OSPTUINT64     ospvTransId,     /* transaction ID value */
    unsigned long  ospvExpires,     /* expiration time in seconds */
    OSPTPROVIDER   *ospvProvider
)
{
    OSPTTRANSID *ptransid = OSPC_OSNULL;    /* pointer to Transaction ID */
    int         errorcode = OSPC_ERR_NO_ERROR;

    /* LOCK GLOBAL DATA NOW */
    errorcode = OSPPProviderLockTransIdMutex(ospvProvider);

    /*
     * As a first step, we purge any transaction IDs that have
     * expired. That may free up memory which will make it easier
     * to add the new ID.
     *
     * Note that we never actually check to make sure the current
     * transaction hasn't itself expired. We don't think that's
     * critical (nothing wrong with an old ID hanging around for
     * a little extra time), and it should never happen (presumably,
     * the caller checks the expiration time before accepting the
     * transaction in the first place), but it does make it possible
     * to purge some old transactions and then add an even older
     * one. A bit funny looking if you test for it, but no harm
     * done.
     */

    if(errorcode == OSPC_ERR_NO_ERROR)
    {
        OSPPTransIdPurge(OSPPProviderGetTransIdSentinel(ospvProvider),
			ospvProvider);
    }

    /*
     * Now get memory to store the current transaction ID. This
     * is a little optimistic, since we might not be able to
     * add the new ID (in which case we'd have to free the
     * memory later). That's a pretty rare occurrence, though,
     * so we can afford the slight inefficiency.
     */

    if(errorcode == OSPC_ERR_NO_ERROR)
    {
        ptransid = OSPPTransIdNew(ospvTransId, ospvExpires);

        if (ptransid != OSPC_OSNULL)
        {
        
            /* add it to the binary tree of ordered IDs */
            if (OSPPTransIdAdd(ptransid, ospvProvider))
            {

                /*
                 * If we were able to add the ID okay, also add it to
                 * the sorted list by expiration time.
                 */

                OSPPTransIdTimeAdd(ptransid, ospvProvider);
            }
            else
            {
                /*
                 * Couldn't add the ID (there must be a duplicate), so
                 * we need to free the memory we allocated.
                 */
                OSPPTransIdDelete(ptransid);
                
                /* RELEASE LOCK ON GLOBAL DATA NOW */
                errorcode = OSPPProviderUnLockTransIdMutex(ospvProvider);
                return OSPC_FALSE;
            }
        }
    }

    /* RELEASE LOCK ON GLOBAL DATA NOW */
	errorcode = OSPPProviderUnLockTransIdMutex(ospvProvider);

#ifdef TN_TRANSDBD
	/* wbr debug: */
	tnTransById( ospvProvider );
#endif

    return((OSPTBOOL)((errorcode == OSPC_ERR_NO_ERROR) ? OSPC_TRUE : OSPC_FALSE));
}

/*-----------------------------------------------------------------------*/
/* OSPPTransIdDelete - free a transaction ID structure */

void                                /* no return value */
OSPPTransIdDelete
(
    OSPTTRANSID *ospvTransId              /* structure to free */
)
{
    OSPM_FREE(ospvTransId);
}

/*-----------------------------------------------------------------------*/
/*OSPPTransIDInit - initialize tree and linked list*/
void
OSPPTransIdInit(
    OSPTPROVIDER * ospvProvider)
{
    int errorcode = OSPC_ERR_NO_ERROR;

    /*initialize transaction tracking
     * initialize the doubly-linked list sentinel */
    OSPTTRANSID *sentinel = OSPPProviderGetTransIdSentinel(ospvProvider);
    OSPTTRANSID **treeroot = OSPPProviderGetTransIdRoot(ospvProvider);

    OSPM_MEMSET(sentinel, 0, sizeof(OSPTTRANSID));
    sentinel->ospmTransactionIdOlderPtr = sentinel;
    sentinel->ospmTransactionIdNewerPtr = sentinel;

    OSPM_MUTEX_INIT(ospvProvider->TransIdMutex, 0, errorcode);

#ifdef TN_TRANSDBG
    if(errorcode != OSPC_ERR_NO_ERROR)
    {
        fprintf(stderr, "\nMutex Init failed Err=  %d.", errorcode);  
    }
#endif
    /* initialize binary tree */
    *treeroot = 0;
}

/*-----------------------------------------------------------------------*/
/* OSPPTransIdNew - allocate and initialize a new transaction ID structure */

OSPTTRANSID *                        /* returns null on failure */
OSPPTransIdNew
(
    OSPTUINT64     ospvTransIdVal,  /* transaction ID value */
    unsigned long  ospvExpires      /* expiration time in seconds */
)
{
    OSPTTRANSID *transid = OSPC_OSNULL;             /* pointer to Transaction ID */

    OSPM_MALLOC(transid, OSPTTRANSID, sizeof(OSPTTRANSID));
    if (transid)
    {
        OSPM_MEMSET(transid, 0, sizeof(OSPTTRANSID));
        transid->ospmTransactionId = ospvTransIdVal;
        transid->ospmTransactionIdExpires = ospvExpires;
    }

    return(transid);
}

/*-----------------------------------------------------------------------*/
/* OSPPTransIdPurge - remove expired transaction IDs */

void                                /* returns nothing */