Index: generic/tclPreserve.c ================================================================== --- generic/tclPreserve.c +++ generic/tclPreserve.c @@ -8,10 +8,22 @@ * Copyright (c) 1991-1994 The Regents of the University of California. * Copyright (c) 1994-1998 Sun Microsystems, Inc. * * See the file "license.terms" for information on usage and redistribution of * this file, and for a DISCLAIMER OF ALL WARRANTIES. + * + * + * === NOVEM EXPERIMENT === + * Replace the dynamic var-sized array of References with a + * hashtable. Faster lookup, no linear search. + * + * Current disadvantage - Possible higher memory churn as individual + * Reference structures get allocated and freed. + * + * Could be fixable by using a list-based stack of free/reusable Reference + * structures. + * === NOVEM EXPERIMENT === */ #include "tclInt.h" /* @@ -34,18 +46,13 @@ /* * Global data structures used to hold the list of preserved data references. * These variables are protected by "preserveMutex". */ -static Reference *refArray = NULL; /* First in array of references. */ -static int spaceAvl = 0; /* Total number of structures available at - * *firstRefPtr. */ -static int inUse = 0; /* Count of structures currently in use in - * refArray. */ -TCL_DECLARE_MUTEX(preserveMutex)/* To protect the above statics */ - -#define INITIAL_SIZE 2 /* Initial number of reference slots to make */ +static Tcl_HashTable* refTable; + +TCL_DECLARE_MUTEX(preserveMutex)/* To protect the above statics */ /* * The following data structure is used to keep track of whether an arbitrary * block of memory has been deleted. This is used by the TclHandle code to * avoid the more time-expensive algorithm of Tcl_Preserve(). This mechanism @@ -86,15 +93,23 @@ /* ARGSUSED */ void TclFinalizePreserve(void) { Tcl_MutexLock(&preserveMutex); - if (spaceAvl != 0) { - ckfree(refArray); - refArray = NULL; - inUse = 0; - spaceAvl = 0; + if (refTable) { + for (;;) { + Reference* refPtr; + Tcl_HashSearch s; + Tcl_HashEntry* hEntry; + hEntry = Tcl_FirstHashEntry (refTable, &s); + if (!hEntry) break; + refPtr = Tcl_GetHashValue (hEntry); + Tcl_DeleteHashEntry (hEntry); + ckfree (refPtr); + } + Tcl_DeleteHashTable (refTable); + refTable = 0; } Tcl_MutexUnlock(&preserveMutex); } /* @@ -119,46 +134,47 @@ void Tcl_Preserve( ClientData clientData) /* Pointer to malloc'ed block of memory. */ { Reference *refPtr; - int i; + int isnew; + Tcl_HashEntry* hEntry; /* * See if there is already a reference for this pointer. If so, just * increment its reference count. */ Tcl_MutexLock(&preserveMutex); - for (i=0, refPtr=refArray ; iclientData == clientData) { - refPtr->refCount++; - Tcl_MutexUnlock(&preserveMutex); - return; - } - } - - /* - * Make a reference array if it doesn't already exist, or make it bigger - * if it is full. - */ - - if (inUse == spaceAvl) { - spaceAvl = spaceAvl ? 2*spaceAvl : INITIAL_SIZE; - refArray = ckrealloc(refArray, spaceAvl * sizeof(Reference)); + + if (!refTable) { + refTable = ckalloc (sizeof (Tcl_HashTable)); + Tcl_InitHashTable (refTable, TCL_ONE_WORD_KEYS); + } + + hEntry = Tcl_FindHashEntry (refTable, clientData); + if (hEntry) { + refPtr = Tcl_GetHashValue (hEntry); + refPtr->refCount++; + + Tcl_MutexUnlock(&preserveMutex); + return; } /* * Make a new entry for the new reference. */ - refPtr = &refArray[inUse]; + refPtr = ckalloc (sizeof (Reference)); refPtr->clientData = clientData; refPtr->refCount = 1; refPtr->mustFree = 0; refPtr->freeProc = TCL_STATIC; - inUse += 1; + + hEntry = Tcl_CreateHashEntry (refTable, clientData, &isnew); + Tcl_SetHashValue (hEntry, refPtr); + Tcl_MutexUnlock(&preserveMutex); } /* *---------------------------------------------------------------------- @@ -182,64 +198,68 @@ void Tcl_Release( ClientData clientData) /* Pointer to malloc'ed block of memory. */ { Reference *refPtr; - int i; - - Tcl_MutexLock(&preserveMutex); - for (i=0, refPtr=refArray ; iclientData != clientData) { - continue; - } - - if (--refPtr->refCount != 0) { - Tcl_MutexUnlock(&preserveMutex); - return; - } - - /* - * Must remove information from the slot before calling freeProc to - * avoid reentrancy problems if the freeProc calls Tcl_Preserve on the - * same clientData. Copy down the last reference in the array to - * overwrite the current slot. - */ - - freeProc = refPtr->freeProc; - mustFree = refPtr->mustFree; - inUse--; - if (i < inUse) { - refArray[i] = refArray[inUse]; - } - - /* - * Now committed to disposing the data. But first, we've patched up - * all the global data structures so we should release the mutex now. - * Only then should we dabble around with potentially-slow memory - * managers... - */ - - Tcl_MutexUnlock(&preserveMutex); - if (mustFree) { - if (freeProc == TCL_DYNAMIC) { - ckfree(clientData); - } else { - freeProc(clientData); - } - } - return; - } - Tcl_MutexUnlock(&preserveMutex); - - /* - * Reference not found. This is a bug in the caller. - */ - - Tcl_Panic("Tcl_Release couldn't find reference for %p", clientData); + Tcl_HashEntry* hEntry; + int mustFree; + Tcl_FreeProc *freeProc; + + Tcl_MutexLock(&preserveMutex); + + if (!refTable) { + refTable = ckalloc (sizeof (Tcl_HashTable)); + Tcl_InitHashTable (refTable, TCL_ONE_WORD_KEYS); + } + + hEntry = Tcl_FindHashEntry (refTable, clientData); + if (!hEntry) { + Tcl_MutexUnlock(&preserveMutex); + + /* + * Reference not found. This is a bug in the caller. + */ + + Tcl_Panic("Tcl_Release couldn't find reference for %p", clientData); + } + + refPtr = Tcl_GetHashValue (hEntry); + + if (--refPtr->refCount != 0) { + Tcl_MutexUnlock(&preserveMutex); + return; + } + + /* + * Must remove information from the slot before calling freeProc to + * avoid reentrancy problems if the freeProc calls Tcl_Preserve on the + * same clientData. + */ + + freeProc = refPtr->freeProc; + mustFree = refPtr->mustFree; + + Tcl_DeleteHashEntry (hEntry); + ckfree (refPtr); + + /* + * Now committed to disposing the data. But first, we've patched up + * all the global data structures so we should release the mutex now. + * Only then should we dabble around with potentially-slow memory + * managers... + */ + + Tcl_MutexUnlock(&preserveMutex); + + if (mustFree) { + if (freeProc == TCL_DYNAMIC) { + ckfree(clientData); + } else { + freeProc(clientData); + } + } + return; } /* *---------------------------------------------------------------------- * @@ -262,30 +282,36 @@ Tcl_EventuallyFree( ClientData clientData, /* Pointer to malloc'ed block of memory. */ Tcl_FreeProc *freeProc) /* Function to actually do free. */ { Reference *refPtr; - int i; /* * See if there is a reference for this pointer. If so, set its "mustFree" * flag (the flag had better not be set already!). */ Tcl_MutexLock(&preserveMutex); - for (i = 0, refPtr = refArray; i < inUse; i++, refPtr++) { - if (refPtr->clientData != clientData) { - continue; - } - if (refPtr->mustFree) { - Tcl_Panic("Tcl_EventuallyFree called twice for %p", clientData); - } - refPtr->mustFree = 1; - refPtr->freeProc = freeProc; - Tcl_MutexUnlock(&preserveMutex); - return; - } + + if (refTable) { + Tcl_HashEntry* hEntry; + + hEntry = Tcl_FindHashEntry (refTable, clientData); + if (hEntry) { + refPtr = Tcl_GetHashValue (hEntry); + + if (refPtr->mustFree) { + Tcl_Panic("Tcl_EventuallyFree called twice for %p", clientData); + } + refPtr->mustFree = 1; + refPtr->freeProc = freeProc; + + Tcl_MutexUnlock(&preserveMutex); + return; + } + } + Tcl_MutexUnlock(&preserveMutex); /* * No reference for this block. Free it now. */