src/dpgSortedArray.c

/******************************************************************************
 **                                                                          **
 **     Module:     dpgSortedArray.c                                         **
 **                                                                          **
 **                                                                          **
 **     This is same as "Utility_SortedArray.c                               **
 **                                                                          **
 **     Copyright (C) 1995-1996 Apple Computer, Inc.  All rights reserved.   **
 **                                                                          **
 **                                                                          **
 *****************************************************************************/
 
#include "dpgMemory.h"
#include "dpgSortedArray.h"
 
/******************************************************************************
 **                                                                          **
 **                             Array Macros                                 **
 **                                                                          **
 *****************************************************************************/
 
#define EmArrayElement(a, elemSize, index)  \
            ((char *) (a) + ((elemSize) * (index)))
 
 
/******************************************************************************
 **                                                                          **
 **                             Array Maintenance                            **
 **                                                                          **
 *****************************************************************************/
 
/*===========================================================================*\
 *
 *  Routine:    dpgSortedArray_Search()
 *
 *  Comments:   
 *
\*===========================================================================*/
TQ3Boolean dpgSortedArray_Search(
    void                *key,
    void                *array,
    unsigned long       nElems,
    unsigned long       elemSize,
    dpgCompareFunction  compare,
    unsigned long       *position)
{
    long    highElem    = nElems - 1;
    long    midElem     = highElem / 2;
    long    lowElem     = 0;
    long    direction   = 1;
    
    while ( (highElem >= lowElem) &&
            (direction = (*compare)(key, EmArrayElement(array, elemSize, midElem))) != 0)
    {
        if (direction > 0)
        {
            lowElem = midElem + 1;
        }
        else
        {
            highElem = midElem - 1;
        }
        midElem = (highElem + lowElem) / 2;
    }
    
    if (direction == 0)
    {
        *position = midElem;
        return kQ3True;
    }
    else
    {   
        *position = lowElem;
        return kQ3False;
    }
}
 
/*===========================================================================*\
 *
 *  Routine:    dpgSortedArray_Resize()
 *
 *  Comments:   
 *
\*===========================================================================*/
TQ3Status dpgSortedArray_Resize(
    void                **array,
    unsigned long       nElems,
    unsigned long       elemSize)
{
    void    *newArray;
        
    if (nElems > 0)
    {
        newArray = dpgRealloc(*array, nElems * elemSize);
        
        if (newArray)
        {
            *array = newArray;
            return (kQ3Success);
        }
    }
    else
    {
        if (*array != NULL) {
            dpgFree(*array);
            *array = NULL;
        }
        return (kQ3Success);
    }
    
    return (kQ3Failure);
}
 
/*===========================================================================*\
 *
 *  Routine:    dpgSortedArray_Insert()
 *
 *  Comments:   
 *
\*===========================================================================*/
void dpgSortedArray_InsertElement(
    void                *array,
    unsigned long       nElems,
    unsigned long       elemSize,
    void                *newElem,
    unsigned long       position)
{
    
    if (position < nElems)
    {
        dpgCopy(
            EmArrayElement(array, elemSize, position),
            EmArrayElement(array, elemSize, position + 1),
            (nElems - position) * elemSize);
    }
    dpgCopy(
        newElem,
        EmArrayElement(array, elemSize, position),
        elemSize);
}
 
/*===========================================================================*\
 *
 *  Routine:    dpgSortedArray_DeleteElement()
 *
 *  Comments:   
 *
\*===========================================================================*/
void dpgSortedArray_DeleteElement(
    void                *array,
    unsigned long       nElems,
    unsigned long       elemSize,
    void                *oldElem,   /* Can be NULL */
    unsigned long       position)
{
    
    if (oldElem)
    {
        dpgCopy(
            EmArrayElement(array, elemSize, position),
            oldElem,
            elemSize);
    }
    if (position < nElems - 1)
    {
        dpgCopy(
            EmArrayElement(array, elemSize, position + 1),
            EmArrayElement(array, elemSize, position),
            (nElems - position - 1) * elemSize);
    }
}


Copyright © 2003 Apple Computer, Inc. All Rights Reserved. Terms of Use | Privacy Policy | Updated: 2003-01-14