OpaqueIDs.c   [plain text]


/*
 * Copyright (c) 2000-2005 Apple Computer, Inc. All rights reserved.
 *
 * @APPLE_LICENSE_HEADER_START@
 * 
 * This file contains Original Code and/or Modifications of Original Code
 * as defined in and that are subject to the Apple Public Source License
 * Version 2.0 (the 'License'). You may not use this file except in
 * compliance with the License. Please obtain a copy of the License at
 * http://www.opensource.apple.com/apsl/ and read it before using this
 * file.
 * 
 * The Original Code and all software distributed under the License are
 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
 * Please see the License for the specific language governing rights and
 * limitations under the License.
 * 
 * @APPLE_LICENSE_HEADER_END@
 */

#include "webdavd.h"

#include <stdlib.h>
#include <pthread.h>

#include "OpaqueIDs.h"

enum
{
	/*
	 * An opaque id is composed of two parts.  The lower half is an index into
	 * a table which holds the actual data for the opaque id.  The upper half is a
	 * counter which insures that a particular opaque id value isn't reused for a long
	 * time after it has been disposed.  Currently, with 20 bits as the index, there
	 * can be (2^20)-2 opaque ids in existence at any particular point in time
	 * (index 0 is not used), and no opaque id value will be re-issued more frequently than every
	 * 2^12th (4096) times. (although, in practice many more opaque ids will be issued
	 * before one is re-used).
	 */
	kOpaqueIDIndexBits = 20,
	kOpaqueIDIndexMask = ((1 << kOpaqueIDIndexBits) - 1),
	kOpaqueIDMaximumCount = (1 << kOpaqueIDIndexBits) - 1, /* all 0 bits are never a valid index */

	/*
	 * This keeps a little 'extra room' in the table, so that if it gets
	 * nearly full that a dispose and re-allocate won't quickly run thru the couple
	 * couple free slots in the table.  So, if there are less than this number of
	 * available items, the table will get grown.
	 */
	kOpaqueIDMinimumFree = 1024,
	/* When the table is grown, grow by this many entries */
	kOpaqueIDGrowCount = 2048
};

/*
 * Create an MPOpaqeID by masking together a count and and index.
 */
#define CreateOpaqueID(counter, index) (opaque_id)(((counter) << kOpaqueIDIndexBits) | ((index) & kOpaqueIDIndexMask))

/*
 * Get the count part of an opaque_id
 */
#define GetOpaqueIDCounterPart(id) (((uint32_t)(id)) >> kOpaqueIDIndexBits)

/*
 * Get the index part of an opaque_id
 */
#define GetOpaqueIDIndexPart(id) (((uint32_t)(id)) & kOpaqueIDIndexMask)

/*****************************************************************************/

/*
 * Keep a 'list' of free records in the gOpaqueEntryArray table, using the .nextIndex field as
 * the link to the next one.  Nodes are put into this list at the end, and removed
 * from the front, to try harder to keep from re-allocating a particular opaque id
 * anytime soon after it has been disposed of.
 */
 
struct OpaqueEntry
{
	opaque_id id;	/* when in use, this is the opaque ID; when not in use, the index part is zero */
	uint32_t nextIndex;	/* linkage for the free list */
	void *data;		/* when in use, this is pointer to the data; it is NULL otherwise */
};
typedef struct OpaqueEntry *OpaqueEntryArrayPtr;

static pthread_mutex_t gOpaqueEntryMutex = PTHREAD_MUTEX_INITIALIZER;
static u_int32_t gOpaqueEntriesAllocated = 0;
static u_int32_t gOpaqueEntriesUsed = 0;
static OpaqueEntryArrayPtr gOpaqueEntryArray = NULL;

static u_int32_t gIndexOfFreeOpaqueEntryHead = 0;
static u_int32_t gIndexOfFreeOpaqueEntryTail = 0;

/*****************************************************************************/

/*
 * AddToFreeList adds the OpaqueEntry at the specified index in the gOpaqueEntryArray array
 * to the free list.
 */
static void AddToFreeList(u_int32_t indexToFree)
{
	OpaqueEntryArrayPtr freeEntry;

	/* don't add the OpaqueEntry at index 0 to free list -- it just won't be used */
	if ( indexToFree != 0 )
	{
		freeEntry = &gOpaqueEntryArray[indexToFree];
		freeEntry->data = 0;
		freeEntry->nextIndex = 0;
		
		/* Add this OpaqueEntry to the tail of the free list */
		if ( gIndexOfFreeOpaqueEntryTail != 0 )
		{
			gOpaqueEntryArray[gIndexOfFreeOpaqueEntryTail].nextIndex = indexToFree;
		}
		gIndexOfFreeOpaqueEntryTail = indexToFree;

		/* If the head of the free list is 0, then this OpaqueEntry is also the head */
		if ( gIndexOfFreeOpaqueEntryHead == 0 )
		{
			gIndexOfFreeOpaqueEntryHead = indexToFree;
		}
	}
}

/*****************************************************************************/

/*
 * RemoveFromFreeList removes a OpaqueEntry from the free list and returns
 * its index in the gOpaqueEntryArray array.
 */
static u_int32_t RemoveFromFreeList()
{
	u_int32_t result;
	
	/* are there any OpaqueEntries free? */
	if ( gIndexOfFreeOpaqueEntryHead != 0 )
	{
		/* remove the OpaqueEntry from the head */
		result = gIndexOfFreeOpaqueEntryHead;

		if ( gIndexOfFreeOpaqueEntryHead == gIndexOfFreeOpaqueEntryTail )
		{
			gIndexOfFreeOpaqueEntryTail = 0;
		}

		gIndexOfFreeOpaqueEntryHead = gOpaqueEntryArray[gIndexOfFreeOpaqueEntryHead].nextIndex;
	}
	else
	{
		result = 0;
	}

	return ( result );
}

/*****************************************************************************/

int AssignOpaqueID(void *inData, opaque_id *outID)
{
	int error;
	u_int32_t entryToUse;
	
	require_action(outID != NULL, bad_parameter, error = EINVAL);
	
	*outID = kInvalidOpaqueID;
	
	error = pthread_mutex_lock(&gOpaqueEntryMutex);
	require_noerr(error, pthread_mutex_lock);
	
	/*
	 * If there aren't any items in the table, or if the number of free items is
	 * lower than we want, then grow the table.
	 */
	if ( (gIndexOfFreeOpaqueEntryHead == 0) || ((gOpaqueEntriesAllocated - gOpaqueEntriesUsed) < kOpaqueIDMinimumFree) )
	{
		u_int32_t newCount;
		
		newCount = MIN(gOpaqueEntriesAllocated + 2048, kOpaqueIDMaximumCount);

		if ( gOpaqueEntriesAllocated < newCount )
		{
			OpaqueEntryArrayPtr nuids;
			
			nuids = (OpaqueEntryArrayPtr)realloc(gOpaqueEntryArray, sizeof(struct OpaqueEntry) * newCount);

			if ( nuids != NULL )
			{
				u_int32_t i;

				gOpaqueEntryArray = nuids;

				/* Add all the 'new' OpaqueEntry to the free list. */
				for ( i = 0; i < newCount - gOpaqueEntriesAllocated; ++i )
				{
					/* set both count and index to 0 */
					gOpaqueEntryArray[gOpaqueEntriesAllocated + i].id = 0;

					AddToFreeList(gOpaqueEntriesAllocated + i);
				}

				gOpaqueEntriesAllocated = newCount;
			}
		}
	}

	/* get index of an OpaqueEntry to use */
	entryToUse = RemoveFromFreeList();

	/* release the lock */
	pthread_mutex_unlock(&gOpaqueEntryMutex);

	/* did we get an OpaqueEntry? */
	require_action((entryToUse != 0) && (entryToUse < gOpaqueEntriesAllocated), no_opaqueID, error = EINVAL);
		
	/* the new id is created with the previous counter + 1, and the index */
	gOpaqueEntryArray[entryToUse].id = CreateOpaqueID(GetOpaqueIDCounterPart(gOpaqueEntryArray[entryToUse].id) + 1, entryToUse);
	gOpaqueEntryArray[entryToUse].data = inData;
	
	*outID = gOpaqueEntryArray[entryToUse].id;

	++gOpaqueEntriesUsed;

no_opaqueID:
pthread_mutex_lock:
bad_parameter:

	return ( error );
}

/*****************************************************************************/

int DeleteOpaqueID(opaque_id inID)
{
	int error;
	uint32_t index;

	error = pthread_mutex_lock(&gOpaqueEntryMutex);
	require_noerr(error, pthread_mutex_lock);
	
	index = GetOpaqueIDIndexPart(inID);
	if ( (index != 0) && (index < gOpaqueEntriesAllocated) && (gOpaqueEntryArray[index].id == inID) )
	{
		/*
		 * Keep the old counter so that next time we can increment the
		 * generation count and return a 'new' opaque ID which maps to this
		 * same index. The index is set to zero to indicate this entry is not
		 * in use.
		 */
		gOpaqueEntryArray[index].id = CreateOpaqueID(GetOpaqueIDCounterPart(inID), 0);

		AddToFreeList(index);
		--gOpaqueEntriesUsed;
	}
	else
	{
		error = EINVAL;
	}

	pthread_mutex_unlock(&gOpaqueEntryMutex);

pthread_mutex_lock:

	return ( error );
}

/*****************************************************************************/

int RetrieveDataFromOpaqueID(opaque_id inID, void **outData)
{
	int error;
	uint32_t index;

	error = pthread_mutex_lock(&gOpaqueEntryMutex);
	require_noerr(error, pthread_mutex_lock);
	
	index = GetOpaqueIDIndexPart(inID);
	if ( (index != 0) && (index < gOpaqueEntriesAllocated) && (gOpaqueEntryArray[index].id == inID) )
	{
		if (outData)
		{
			*outData = gOpaqueEntryArray[index].data;
		}
	}
	else
	{
		error = EINVAL;
	}
	
	pthread_mutex_unlock(&gOpaqueEntryMutex);

pthread_mutex_lock:

	return ( error );
}

/*****************************************************************************/