UT/UT_ArrayHelp.h

Go to the documentation of this file.

/*
 * PROPRIETARY INFORMATION.  This software is proprietary to
 * Side Effects Software Inc., and is not to be reproduced,
 * transmitted, or disclosed in any way without written permission.
 *
 * Produced by:
 *      Jeff Lait
 *      Side Effects Software Inc
 *      477 Richmond Street West
 *      Toronto, Ontario
 *      Canada   M5V 3E7
 *      416-504-9876
 *
 * NAME:        UT_ArrayHelp.h ( UT Library, C++)
 *
 * COMMENTS:
 *      Provides simple helper functions for the UT_*Array and UT_Symbol/
 *      HashTable classes.
 *
 *      Should be private to the UT library, but needs to be exported
 *      so NT style template instantiation will work.
 */

#ifndef __UT_ArrayHelp__
#define __UT_ArrayHelp__

#include "UT_API.h"
typedef int (*ut_ptr_compare_func_t)(const void *, const void *);

#define SMALL_ALLOC     4
#define BIG_ALLOC       128

// This routine describes how to change the size of an array.
// It must increase the current_size by at least one!
static inline unsigned int
bumpAlloc(unsigned int current_size)
{
    unsigned    bump;

    // For small values, we increment in by fixed amounts.  For
    // large values, we increment by one eighth of the current size.
    // This prevents n^2 behaviour with allocation one element at a time.
    // A factor of 1/8 will waste 1/16 the memory on average, and will
    // double the size of the array in approximately 6 reallocations.
    if (current_size < BIG_ALLOC)
        bump = SMALL_ALLOC;
    else if (current_size < BIG_ALLOC * 8)
        bump = BIG_ALLOC;
    else
        bump = current_size >> 3;               // Divided by 8.
        
    current_size += bump;
    return current_size;
}

// This function is used by the symbol tables to bump to the next/previous
// prime size.
UT_API int UTbumpAllocToPrime(int current_size);
UT_API int UTdecreaseAllocToPrime(int current_size);

#endif

---