diff options
Diffstat (limited to 'private/unimodem/common/rovmem.c')
| -rw-r--r-- | private/unimodem/common/rovmem.c | 2269 |
1 files changed, 2269 insertions, 0 deletions
diff --git a/private/unimodem/common/rovmem.c b/private/unimodem/common/rovmem.c new file mode 100644 index 000000000..653cb1859 --- /dev/null +++ b/private/unimodem/common/rovmem.c @@ -0,0 +1,2269 @@ +// +// Copyright (c) Microsoft Corporation 1993-1995 +// +// mem.c +// +// This file contains memory management and dynamic +// array functions. +// +// History: +// 09-27-94 ScottH Taken from commctrl +// 04-29-95 ScottH Taken from briefcase and cleaned up +// + + +#include "proj.h" +#include <rovcomm.h> + +#ifndef NOMEM + +////////////////////////////////////////////////////////////////// + +#ifdef WINNT + +/*---------------------------------------------------------- +Purpose: Wide-char version of SetStringA + +Returns: TRUE on success +Cond: -- +*/ +BOOL PUBLIC SetStringW( + LPWSTR FAR * ppszBuf, + LPCWSTR psz) // NULL to free *ppszBuf + { + BOOL bRet = FALSE; + + ASSERT(ppszBuf); + + // Free the buffer? + if (!psz) + { + // Yes + if (*ppszBuf) + { + LocalFree(LOCALOF(*ppszBuf)); + *ppszBuf = NULL; + } + bRet = TRUE; + } + else + { + // No; (re)allocate and set buffer + UINT cb = CbFromCchW(lstrlenW(psz)+1); + + if (*ppszBuf) + { + // Need to reallocate? + if (cb > LocalSize(LOCALOF(*ppszBuf))) + { + // Yes + LPWSTR pszT = (LPWSTR)LocalReAlloc(LOCALOF(*ppszBuf), cb, LMEM_MOVEABLE | LMEM_ZEROINIT); + if (pszT) + { + *ppszBuf = pszT; + bRet = TRUE; + } + } + else + { + // No + bRet = TRUE; + } + } + else + { + *ppszBuf = (LPWSTR)LocalAlloc(LPTR, cb); + if (*ppszBuf) + { + bRet = TRUE; + } + } + + if (bRet) + { + ASSERT(*ppszBuf); + lstrcpyW(*ppszBuf, psz); + } + } + return bRet; + } + + +/*---------------------------------------------------------- +Purpose: Wide-char version of CatStringA + +Returns: TRUE on success +Cond: -- +*/ +BOOL +PRIVATE +MyCatStringW( + IN OUT LPWSTR FAR * ppszBuf, + IN LPCWSTR psz, OPTIONAL + IN BOOL bMultiString) + { + BOOL bRet = FALSE; + + ASSERT(ppszBuf); + + // Free the buffer? + if ( !psz ) + { + // Yes + if (*ppszBuf) + { + LocalFree(LOCALOF(*ppszBuf)); + *ppszBuf = NULL; + } + bRet = TRUE; + } + else + { + // No; (re)allocate and set buffer + LPWSTR pszBuf = *ppszBuf; + UINT cch; + + cch = lstrlenW(psz) + 1; // account for null + + if (bMultiString) + { + cch++; // account for second null + } + + if (pszBuf) + { + UINT cchExisting; + LPWSTR pszT; + + // Figure out how much of the buffer has been used + + // Is this a multi-string (one with strings with a double-null + // terminator)? + if (bMultiString) + { + // Yes + UINT cchT; + + cchExisting = 0; + pszT = (LPWSTR)pszBuf; + while (0 != *pszT) + { + cchT = lstrlenW(pszT) + 1; + cchExisting += cchT; + pszT += cchT; + } + } + else + { + // No; (don't need to count null because it is already + // counted in cch) + cchExisting = lstrlenW(pszBuf); + } + + // Need to reallocate? + if (CbFromCchW(cch + cchExisting) > LocalSize(LOCALOF(pszBuf))) + { + // Yes; realloc at least MAX_BUF to cut down on the amount + // of calls in the future + cch = cchExisting + max(cch, MAX_BUF); + + pszT = (LPWSTR)LocalReAlloc(LOCALOF(pszBuf), + CbFromCchW(cch), + LMEM_MOVEABLE | LMEM_ZEROINIT); + if (pszT) + { + pszBuf = pszT; + *ppszBuf = pszBuf; + bRet = TRUE; + } + } + else + { + // No + bRet = TRUE; + } + + pszBuf += cchExisting; + } + else + { + cch = max(cch, MAX_BUF); + + pszBuf = (LPWSTR)LocalAlloc(LPTR, CbFromCchW(cch)); + if (pszBuf) + { + bRet = TRUE; + } + + *ppszBuf = pszBuf; + } + + if (bRet) + { + ASSERT(pszBuf); + + lstrcpyW(pszBuf, psz); + + if (bMultiString) + { + pszBuf[lstrlenW(psz) + 1] = 0; // Add second null terminator + } + } + } + + return bRet; + } + + +/*---------------------------------------------------------- +Purpose: Wide-char version of CatStringA + +Returns: TRUE on success +Cond: -- +*/ +BOOL +PUBLIC +CatStringW( + IN OUT LPWSTR FAR * ppszBuf, + IN LPCWSTR psz) + { + return MyCatStringW(ppszBuf, psz, FALSE); + } + +/*---------------------------------------------------------- +Purpose: Wide-char version of CatMultiStringA + +Returns: TRUE on success +Cond: -- +*/ +BOOL +PUBLIC +CatMultiStringW( + IN OUT LPWSTR FAR * ppszBuf, + IN LPCWSTR psz) + { + return MyCatStringW(ppszBuf, psz, TRUE); + } + +#endif // WINNT + + +/*---------------------------------------------------------- +Purpose: Copies psz into *ppszBuf. Will alloc or realloc *ppszBuf + accordingly. + + If psz is NULL, this function frees *ppszBuf. This is + the preferred method of freeing the allocated buffer. + +Returns: TRUE on success +Cond: -- +*/ +BOOL PUBLIC SetStringA( + LPSTR FAR * ppszBuf, + LPCSTR psz) // NULL to free *ppszBuf + { + BOOL bRet = FALSE; + + ASSERT(ppszBuf); + + // Free the buffer? + if (!psz) + { + // Yes + if (ppszBuf) + { + LocalFree(LOCALOF(*ppszBuf)); + *ppszBuf = NULL; + } + bRet = TRUE; + } + else + { + // No; (re)allocate and set buffer + UINT cb = CbFromCchA(lstrlenA(psz)+1); + + if (*ppszBuf) + { + // Need to reallocate? + if (cb > LocalSize(LOCALOF(*ppszBuf))) + { + // Yes + LPSTR pszT = (LPSTR)LocalReAlloc(LOCALOF(*ppszBuf), cb, LMEM_MOVEABLE | LMEM_ZEROINIT); + if (pszT) + { + *ppszBuf = pszT; + bRet = TRUE; + } + } + else + { + // No + bRet = TRUE; + } + } + else + { + *ppszBuf = (LPSTR)LocalAlloc(LPTR, cb); + if (*ppszBuf) + { + bRet = TRUE; + } + } + + if (bRet) + { + ASSERT(*ppszBuf); + lstrcpyA(*ppszBuf, psz); + } + } + return bRet; + } + + +/*---------------------------------------------------------- +Purpose: Concatenates psz onto *ppszBuf. Will alloc or + realloc *ppszBuf accordingly. + + If bMultiString is TRUE, psz will be appended with + a null terminator separating the existing string + and new string. A double-null terminator will + be tacked on the end, too. + + To free, call MyCatString(ppszBuf, NULL). + +Returns: TRUE on success +Cond: -- +*/ +BOOL +PRIVATE +MyCatStringA( + IN OUT LPSTR FAR * ppszBuf, + IN LPCSTR psz, OPTIONAL + IN BOOL bMultiString) + { + BOOL bRet = FALSE; + + ASSERT(ppszBuf); + + // Free the buffer? + if ( !psz ) + { + // Yes + if (*ppszBuf) + { + LocalFree(LOCALOF(*ppszBuf)); + *ppszBuf = NULL; + } + bRet = TRUE; + } + else + { + // No; (re)allocate and set buffer + LPSTR pszBuf = *ppszBuf; + UINT cch; + + cch = lstrlenA(psz) + 1; // account for null + + if (bMultiString) + { + cch++; // account for second null + } + + if (pszBuf) + { + UINT cchExisting; + LPSTR pszT; + + // Figure out how much of the buffer has been used + + // Is this a multi-string (one with strings with a double-null + // terminator)? + if (bMultiString) + { + // Yes + UINT cchT; + + cchExisting = 0; + pszT = (LPSTR)pszBuf; + while (0 != *pszT) + { + cchT = lstrlenA(pszT) + 1; + cchExisting += cchT; + pszT += cchT; + } + } + else + { + // No; (don't need to count null because it is already + // counted in cch) + cchExisting = lstrlenA(pszBuf); + } + + // Need to reallocate? + if (CbFromCchA(cch + cchExisting) > LocalSize(LOCALOF(pszBuf))) + { + // Yes; realloc at least MAX_BUF to cut down on the amount + // of calls in the future + cch = cchExisting + max(cch, MAX_BUF); + + pszT = (LPSTR)LocalReAlloc(LOCALOF(pszBuf), + CbFromCchA(cch), + LMEM_MOVEABLE | LMEM_ZEROINIT); + if (pszT) + { + pszBuf = pszT; + *ppszBuf = pszBuf; + bRet = TRUE; + } + } + else + { + // No + bRet = TRUE; + } + + pszBuf += cchExisting; + } + else + { + cch = max(cch, MAX_BUF); + + pszBuf = (LPSTR)LocalAlloc(LPTR, CbFromCchA(cch)); + if (pszBuf) + { + bRet = TRUE; + } + + *ppszBuf = pszBuf; + } + + if (bRet) + { + ASSERT(pszBuf); + + lstrcpyA(pszBuf, psz); + + if (bMultiString) + { + pszBuf[lstrlenA(psz) + 1] = 0; // Add second null terminator + } + } + } + return bRet; + } + + +/*---------------------------------------------------------- +Purpose: Concatenates psz onto *ppszBuf. Will alloc or + realloc *ppszBuf accordingly. + + To free, call CatString(ppszBuf, NULL). + +Returns: TRUE on success +Cond: -- +*/ +BOOL +PUBLIC +CatStringA( + IN OUT LPSTR FAR * ppszBuf, + IN LPCSTR psz) OPTIONAL + { + return MyCatStringA(ppszBuf, psz, FALSE); + } + + +/*---------------------------------------------------------- +Purpose: Concatenates psz onto *ppszBuf. Will alloc or + realloc *ppszBuf accordingly. + + psz will be appended with a null terminator separating + the existing string and new string. A double-null + terminator will be tacked on the end, too. + + To free, call CatMultiString(ppszBuf, NULL). + +Returns: TRUE on success +Cond: -- +*/ +BOOL +PUBLIC +CatMultiStringA( + IN OUT LPSTR FAR * ppszBuf, + IN LPCSTR psz) + { + return MyCatStringA(ppszBuf, psz, TRUE); + } + + + +////////////////////////////////////////////////////////////////// + + +#ifndef WIN32 +// +// Subsegment Allocation for 16-bit +// + +#define MAX_WORD 0xffff + +DECLARE_HANDLE(HHEAP); + +typedef struct + { // maps to the bottom of a 16bit DS + WORD reserved[8]; + WORD cAlloc; + WORD cbAllocFailed; + HHEAP hhpFirst; + HHEAP hhpNext; + } HEAP; + +#define PHEAP(hhp) ((HEAP FAR*)MAKELP(hhp, 0)) +#define MAKEHP(sel, off) ((void _huge*)MAKELP((sel), (off))) + +#define CBSUBALLOCMAX 0x0000f000L + +HHEAP g_hhpFirst = NULL; + +BOOL NEAR DestroyHeap(HHEAP hhp); + +void Mem_Terminate() +{ + while (g_hhpFirst) + DestroyHeap(g_hhpFirst); +} + +BOOL NEAR CreateHeap(WORD cbInitial) +{ + HHEAP hhp; + + if (cbInitial < 1024) + cbInitial = 1024; + + hhp = (HHEAP)GlobalAlloc(GMEM_MOVEABLE | GMEM_ZEROINIT | GMEM_SHARE, cbInitial); + + if (!hhp) + return FALSE; + + if (!LocalInit((WORD)hhp, sizeof(HEAP), cbInitial - 1)) + { + GlobalFree(hhp); + return FALSE; + } + + PHEAP(hhp)->cAlloc = 0; + PHEAP(hhp)->cbAllocFailed = MAX_WORD; + PHEAP(hhp)->hhpNext = g_hhpFirst; + g_hhpFirst = hhp; + + TRACE_MSG(TF_GENERAL, "CreateHeap: added new local heap %x", hhp); + + return TRUE; +} + +#pragma optimize("o", off) // linked list removals don't optimize correctly +BOOL NEAR DestroyHeap(HHEAP hhp) +{ + ASSERT(hhp); + ASSERT(g_hhpFirst); + + if (g_hhpFirst == hhp) + { + g_hhpFirst = PHEAP(hhp)->hhpNext; + } + else + { + HHEAP hhpT = g_hhpFirst; + + while (PHEAP(hhpT)->hhpNext != hhp) + { + hhpT = PHEAP(hhpT)->hhpNext; + if (!hhpT) + return FALSE; + } + + PHEAP(hhpT)->hhpNext = PHEAP(hhp)->hhpNext; + } + if (GlobalFree((HGLOBAL)hhp) != NULL) + return FALSE; + + return TRUE; +} +#pragma optimize("", on) // back to default optimizations + +#pragma optimize("lge", off) // Suppress warnings associated with use of _asm... +void NEAR* NEAR HeapAlloc(HHEAP hhp, WORD cb) +{ + void NEAR* pb; + + _asm { + push ds + mov ds,hhp + } + + pb = (void NEAR*)LocalAlloc(LMEM_FIXED | LMEM_ZEROINIT, cb); + + if (pb) + ((HEAP NEAR*)0)->cAlloc++; + + _asm { + pop ds + } + + return pb; +} +#pragma optimize("", on) // back to default optimizations + +#ifndef NOSHAREDHEAP + +#pragma optimize("o", off) // linked list removals don't optimize correctly + + +void _huge* WINAPI SharedAlloc(long cb) +{ + void NEAR* pb; + HHEAP hhp; + HHEAP hhpPrev; + + // If this is a big allocation, just do a global alloc. + // + if (cb > CBSUBALLOCMAX) + { + void FAR* lpb = MAKEHP(GlobalAlloc(GMEM_MOVEABLE | GMEM_ZEROINIT | GMEM_SHARE, cb), 0); + if (!lpb) + DebugMsg(DM_ERROR, "Alloc: out of memory"); + return lpb; + } + + hhp = g_hhpFirst; + + while (TRUE) + { + if (hhp == NULL) + { + if (!CreateHeap(0)) + { + DebugMsg(DM_ERROR, "Alloc: out of memory"); + return NULL; + } + + hhp = g_hhpFirst; + } + + pb = HeapAlloc(hhp, (WORD)cb); + if (pb) + return MAKEHP(hhp, pb); + + // Record the size of the allocation that failed. + // Later attempts to allocate more than this amount + // will not succeed. This gets reset anytime anything + // is freed in the heap. + // + PHEAP(hhp)->cbAllocFailed = (WORD)cb; + + // First heap is full... see if there's room in any other heap... + // + for (hhpPrev = hhp; hhp = PHEAP(hhp)->hhpNext; hhpPrev = hhp) + { + // If the last allocation to fail in this heap + // is not larger than cb, don't even try an allocation. + // + if ((WORD)cb >= PHEAP(hhp)->cbAllocFailed) + continue; + + pb = HeapAlloc(hhp, (WORD)cb); + if (pb) + { + // This heap had room: move it to the front... + // + PHEAP(hhpPrev)->hhpNext = PHEAP(hhp)->hhpNext; + PHEAP(hhp)->hhpNext = g_hhpFirst; + g_hhpFirst = hhp; + + return MAKEHP(hhp, pb); + } + else + { + // The alloc failed. Set cbAllocFailed... + // + PHEAP(hhp)->cbAllocFailed = (WORD)cb; + } + } + } +} +#pragma optimize("", on) // back to default optimizations + +#pragma optimize("lge", off) // Suppress warnings associated with use of _asm... + +void _huge* WINAPI SharedReAlloc(void _huge* pb, long cb) +{ + void NEAR* pbNew; + void _huge* lpbNew; + UINT cbOld; + + // BUGBUG, does not work with cb > 64k + if (!pb) + return SharedAlloc(cb); + + if (OFFSETOF(pb) == 0) + return MAKEHP(GlobalReAlloc((HGLOBAL)SELECTOROF(pb), cb, GMEM_MOVEABLE | GMEM_ZEROINIT), 0); + + _asm { + push ds + mov ds,word ptr [pb+2] + } + + pbNew = (void NEAR*)LocalReAlloc(LOCALOF(pb), (int)cb, LMEM_MOVEABLE | LMEM_ZEROINIT); + if (!pbNew) + cbOld = LocalSize(LOCALOF(pb)); + + _asm { + pop ds + } + + if (pbNew) + return MAKEHP(SELECTOROF(pb), pbNew); + + lpbNew = SharedAlloc(cb); + if (lpbNew) + { + hmemcpy((void FAR*)lpbNew, (void FAR*)pb, cbOld); + Free(pb); + } + else + { + DebugMsg(DM_ERROR, "ReAlloc: out of memory"); + } + return lpbNew; +} + +BOOL WINAPI SharedFree(void _huge* FAR * ppb) +{ + BOOL fSuccess; + UINT cAlloc; + void _huge * pb = *ppb; + + if (!pb) + return FALSE; + + *ppb = 0; + + if (OFFSETOF(pb) == 0) + return (GlobalFree((HGLOBAL)SELECTOROF(pb)) == NULL); + + _asm { + push ds + mov ds,word ptr [pb+2] + } + + fSuccess = (LocalFree(LOCALOF(pb)) ? FALSE : TRUE); + + cAlloc = 1; + if (fSuccess) + { + cAlloc = --((HEAP NEAR*)0)->cAlloc; + ((HEAP NEAR*)0)->cbAllocFailed = MAX_WORD; + } + + _asm { + pop ds + } + + if (cAlloc == 0) + DestroyHeap((HHEAP)SELECTOROF(pb)); + + return fSuccess; +} + + +DWORD WINAPI SharedGetSize(void _huge* pb) +{ + WORD wSize; + + if (OFFSETOF(pb) == 0) + return GlobalSize((HGLOBAL)SELECTOROF(pb)); + + _asm { + push ds + mov ds,word ptr [pb+2] + } + + wSize = LocalSize(LOCALOF(pb)); + + _asm { + pop ds + } + + return (DWORD)wSize; +} + +#pragma optimize("", on) + +#endif // NOSHAREDHEAP + +////////////////////////////////////////////////////////////////// + +#else // WIN32 +// +// Win32 memory management wrappers +// + +// +// Shared heap memory management +// +#if !defined(NOSHAREDHEAP) && defined(WIN95) + +// Define a Global Shared Heap that we use to allocate memory +// out of that we need to share between multiple instances. +// +static HANDLE g_hSharedHeap = NULL; + +#define MAXHEAPSIZE 2097152 +#define HEAP_SHARED 0x04000000 /* put heap in shared memory */ + + +/*---------------------------------------------------------- +Purpose: Clean up heap. This function should be called at + the program's termination. + +Returns: -- +Cond: -- +*/ +void PUBLIC SharedTerminate() + { + // Assuming that everything else has exited + // + if (g_hSharedHeap != NULL) + HeapDestroy(g_hSharedHeap); + g_hSharedHeap = NULL; + } + + +/*---------------------------------------------------------- +Purpose: Allocate out of shared heap + +Returns: Pointer to allocate memory +Cond: -- +*/ +void FAR * PUBLIC SharedAlloc( + DWORD cb) + { + // I will assume that this is the only one that needs the checks to + // see if the heap has been previously created or not + + if (g_hSharedHeap == NULL) + { + ENTER_EXCLUSIVE() + { + if (g_hSharedHeap == NULL) + { + g_hSharedHeap = HeapCreate(HEAP_SHARED, 1, MAXHEAPSIZE); + } + } + LEAVE_EXCLUSIVE() + + // If still NULL we have problems! + if (g_hSharedHeap == NULL) + return(NULL); + } + + return HeapAlloc(g_hSharedHeap, HEAP_ZERO_MEMORY, cb); + } + + +/*---------------------------------------------------------- +Purpose: Realloc out of shared heap. + +Returns: Possibly new pointer to resized block +Cond: -- +*/ +void FAR * PUBLIC SharedReAlloc( + LPVOID pv, + DWORD cb) + { + if (NULL == pv) + { + return SharedAlloc(cb); + } + return HeapReAlloc(g_hSharedHeap, HEAP_ZERO_MEMORY, pv, cb); + } + + +/*---------------------------------------------------------- +Purpose: Free shared memory + +Returns: -- +Cond: -- +*/ +void PUBLIC _SharedFree( + LPVOID pv) + { + ASSERT(pv); + + if (pv) + { + HeapFree(g_hSharedHeap, 0, pv); + } + } + + +/*---------------------------------------------------------- +Purpose: Returns the allocated size of a block + +Returns: see above +Cond: -- +*/ +DWORD PUBLIC SharedGetSize( + LPVOID pv) + { + return HeapSize(g_hSharedHeap, 0, pv); + } + + +/*---------------------------------------------------------- +Purpose: Copies psz into *ppszBuf. Will alloc or realloc *ppszBuf + accordingly. + + If psz is NULL, this function frees *ppszBuf. This is + the preferred method of freeing the allocated buffer. + +Returns: TRUE on success +Cond: -- +*/ +BOOL PUBLIC SharedSetString( + LPTSTR FAR * ppszBuf, + LPCTSTR psz) // NULL to free *ppszBuf + { + BOOL bRet; + + ASSERT(ppszBuf); + + // Free the buffer? + if (!psz) + { + // Yes + if (ppszBuf) + SharedFree(*ppszBuf); + bRet = TRUE; + } + else + { + // No; (re)allocate and set buffer + DWORD cb = CbFromCch(lstrlen(psz)+1); + + LPTSTR pszT = SharedReAlloc(*ppszBuf, cb); + if (pszT) + { + *ppszBuf = pszT; + lstrcpy(*ppszBuf, psz); + bRet = TRUE; + } + else + bRet = FALSE; + } + return bRet; + } +#endif // NOSHAREDHEAP + +#endif // WIN32 + +////////////////////////////////////////////////////////////////// + + +#ifndef NODA + +#ifdef WIN32 + +// +// Memory tracking functions +// + +#ifdef DEBUG + +typedef struct _HEAPTRACE +{ + DWORD cAlloc; + DWORD cFailure; + DWORD cReAlloc; + DWORD cbMaxTotal; + DWORD cCurAlloc; + DWORD cbCurTotal; +} HEAPTRACE; + +HEAPTRACE g_htSync = {0}; // Start of zero... + +#endif // DEBUG + + +/*---------------------------------------------------------- +Purpose: Allocate from a heap. + +Returns: pointer to block of memory + NULL (if out of memory) + +Cond: -- +*/ +LPVOID PUBLIC MemAlloc( + HANDLE hheap, + DWORD cb) + { + LPVOID lp; + + if (hheap) + { + lp = HeapAlloc(hheap, HEAP_ZERO_MEMORY, cb); + } + else + { + lp = GAlloc(cb); + } + + if (lp == NULL) + { + DEBUG_CODE( g_htSync.cFailure++; ) + return NULL; + } + +#ifdef DEBUG + + // Update counts. + g_htSync.cAlloc++; + g_htSync.cCurAlloc++; + g_htSync.cbCurTotal += cb; + if (g_htSync.cbCurTotal > g_htSync.cbMaxTotal) + g_htSync.cbMaxTotal = g_htSync.cbCurTotal; + +#endif + + return lp; + } + + +/*---------------------------------------------------------- +Purpose: Reallocate a block of memory in a given heap. + +Returns: Pointer to reallocated block + NULL (if out of memory) + +Cond: -- +*/ +LPVOID PUBLIC MemReAlloc( + HANDLE hheap, + LPVOID pb, + DWORD cb) + { + LPVOID lp; + DEBUG_CODE( DWORD cbOld; ) + + if (hheap) + { + DEBUG_CODE( cbOld = HeapSize(hheap, 0, pb); ) + + lp = HeapReAlloc(hheap, HEAP_ZERO_MEMORY, pb, cb); + } + else + { + if (pb) + { + DEBUG_CODE( cbOld = GGetSize(pb); ) + + lp = GReAlloc(pb, cb); + } + else + { + DEBUG_CODE( cbOld = 0; ) + + lp = GAlloc(cb); + } + } + + if (lp == NULL) + { + DEBUG_CODE( g_htSync.cFailure++; ) + return NULL; + } + +#ifdef DEBUG + + // Update counts. + g_htSync.cReAlloc++; + g_htSync.cbCurTotal += cb - cbOld; + if (g_htSync.cbCurTotal > g_htSync.cbMaxTotal) + g_htSync.cbMaxTotal = g_htSync.cbCurTotal; + +#endif + + return lp; + } + + +/*---------------------------------------------------------- +Purpose: Free block of memory in heap. + +Returns: TRUE + FALSE (if failure) + +Cond: -- +*/ +BOOL PUBLIC MemFree( + HANDLE hheap, + LPVOID pb) + { + BOOL fRet; + DEBUG_CODE( DWORD cbOld; ) + + if (hheap) + { + DEBUG_CODE( cbOld = HeapSize(hheap, 0, pb); ) + + fRet = HeapFree(hheap, 0, pb); + } + else + { + DEBUG_CODE( cbOld = GGetSize(pb); ) + + GFree(pb); + fRet = TRUE; + } + +#ifdef DEBUG + + if (fRet) + { + // Update counts. + g_htSync.cCurAlloc--; + g_htSync.cbCurTotal -= cbOld; + } + +#endif + + return fRet; + } + + +/*---------------------------------------------------------- +Purpose: Returns the size of the given block. + +Returns: size in bytes +Cond: -- +*/ +DWORD PUBLIC MemSize( + HANDLE hheap, + LPVOID pb) + { + if (hheap) + return HeapSize(hheap, 0, pb); + else + return GGetSize(pb); + } + +#endif // WIN32 + + +/*---------------------------------------------------------- +Purpose: Private alloc for pointer array functions. + +Returns: pointer to block of memory + NULL (if out of memory) + +Cond: -- +*/ +LPVOID PRIVATE PrvAlloc( + DWORD dwFlags, // PAF_* flags + HANDLE hheap, + DWORD cb) + { + LPVOID lp; + + ASSERT(PAF_SHARED == SAF_SHARED); + + if (IsFlagSet(dwFlags, PAF_SHARED)) + { + lp = SharedAlloc(cb); + } + else + { + lp = MemAlloc(hheap, cb); + } + + return lp; + } + + +// Heapsort is a bit slower, but it doesn't use any stack or memory... +// Mergesort takes a bit of memory (O(n)) and stack (O(log(n)), but very fast... +// +#ifdef WIN32 +#define MERGESORT +#else +#define USEHEAPSORT +#endif + +#ifdef DEBUG +#define SA_MAGIC ('S' | ('A' << 256)) +#define IsSA(psa) ((psa) && (psa)->magic == SA_MAGIC) +#define PA_MAGIC ('P' | ('A' << 256)) +#define IsPA(ppa) ((ppa) && (ppa)->magic == PA_MAGIC) +#else +#define IsSA(psa) +#define IsPA(ppa) +#endif + + +typedef struct + { + LPVOID FAR * pp; + PFNPACOMPARE pfnCmp; + LPARAM lParam; + int cp; +#ifdef MERGESORT + LPVOID FAR * ppT; +#endif + } SORTPARAMS; + +BOOL NEAR PAQuickSort(SORTPARAMS FAR* psp); +BOOL NEAR PAQuickSort2(int i, int j, SORTPARAMS FAR* psp); +BOOL NEAR PAHeapSort(SORTPARAMS FAR* psp); +void NEAR PAHeapSortPushDown(int first, int last, SORTPARAMS FAR* psp); +BOOL NEAR PAMergeSort(SORTPARAMS FAR* psp); +void NEAR PAMergeSort2(SORTPARAMS FAR* psp, int iFirst, int cItems); + + +// +// Structure Array +// + +typedef struct _SA + { + // NOTE: The following field MUST be defined at the beginning of the + // structure in order for SAGetCount() to work. + int cItem; // number of elements in sa + + LPVOID aItem; // memory for elements + int cItemAlloc; // number items which fit in aItem + int cbItem; // size of each item + int cItemGrow; // number items to grow cItemAlloc by + DWORD dwFlags; + HANDLE hheap; + +#ifdef DEBUG + UINT magic; +#endif + } SA; + +#define SA_PITEM(psa, index) ((LPVOID)(((BYTE FAR*)(psa)->aItem) + ((index) * (psa)->cbItem))) + + +/*---------------------------------------------------------- +Purpose: Create a structure array. + +Returns: handle to structure array +Cond: -- +*/ +HSA PUBLIC SACreate( + int cbItem, + int cItemGrow, + HANDLE hheap, // Must be non-NULL if SAF_HEAP set + DWORD dwFlags) + { + HSA psa; + + ASSERT(cbItem); + ASSERT(hheap && IsFlagSet(dwFlags, SAF_HEAP) || + IsFlagClear(dwFlags, SAF_HEAP)); + + psa = PrvAlloc(dwFlags, hheap, sizeof(SA)); + +#if !defined(NOSHAREDHEAP) && defined(WIN95) + if (IsFlagSet(dwFlags, PAF_SHARED)) + hheap = g_hSharedHeap; +#endif + + if (psa) + { + psa->cItem = 0; + psa->cItemAlloc = 0; + psa->cbItem = cbItem; + psa->cItemGrow = (cItemGrow == 0 ? 1 : cItemGrow); + psa->aItem = NULL; + psa->dwFlags = dwFlags; + psa->hheap = hheap; + +#ifdef DEBUG + psa->magic = SA_MAGIC; +#endif + } + return psa; + } + + +/*---------------------------------------------------------- +Purpose: Destroys a structure array. + +Returns: +Cond: -- +*/ +BOOL PUBLIC SADestroy( + HSA psa) + { + ASSERT(IsSA(psa)); + + if (psa == NULL) // allow NULL for low memory cases, still assert + return TRUE; + +#ifdef DEBUG + psa->cItem = 0; + psa->cItemAlloc = 0; + psa->cbItem = 0; + psa->magic = 0; +#endif + if (psa->aItem && !MemFree(psa->hheap, psa->aItem)) + return FALSE; + + MemFree(psa->hheap, psa); + return TRUE; + } + + +/*---------------------------------------------------------- +Purpose: Copy structure at index into buffer. + +Returns: TRUE + FALSE +Cond: -- +*/ +BOOL PUBLIC SAGetItem( + HSA psa, + int index, + LPVOID pitem) + { + ASSERT(IsSA(psa)); + ASSERT(pitem); + + if (index < 0 || index >= psa->cItem) + { + TRACE_MSG(TF_ERROR, "SA: Invalid index: %d", index); + return FALSE; + } + + hmemcpy(pitem, SA_PITEM(psa, index), psa->cbItem); + return TRUE; + } + + +/*---------------------------------------------------------- +Purpose: Get pointer to structure in array + +Returns: +Cond: -- +*/ +LPVOID PUBLIC SAGetItemPtr( + HSA psa, + int index) + { + ASSERT(IsSA(psa)); + + if (index < 0 || index >= psa->cItem) + { + TRACE_MSG(TF_ERROR, "SA: Invalid index: %d", index); + return NULL; + } + return SA_PITEM(psa, index); + } + + +/*---------------------------------------------------------- +Purpose: Set item + +Returns: +Cond: -- +*/ +BOOL PUBLIC SASetItem( + HSA psa, + int index, + LPVOID pitem) + { + ASSERT(pitem); + ASSERT(IsSA(psa)); + + if (index < 0) + { + TRACE_MSG(TF_ERROR, "SA: Invalid index: %d", index); + return FALSE; + } + + if (index >= psa->cItem) + { + if (index + 1 > psa->cItemAlloc) + { + int cItemAlloc = (((index + 1) + psa->cItemGrow - 1) / psa->cItemGrow) * psa->cItemGrow; + + LPVOID aItemNew = MemReAlloc(psa->hheap, psa->aItem, cItemAlloc * psa->cbItem); + if (!aItemNew) + return FALSE; + + psa->aItem = aItemNew; + psa->cItemAlloc = cItemAlloc; + } + psa->cItem = index + 1; + } + + hmemcpy(SA_PITEM(psa, index), pitem, psa->cbItem); + + return TRUE; + } + + +/*---------------------------------------------------------- +Purpose: +Returns: +Cond: -- +*/ +int PUBLIC SAInsertItem( + HSA psa, + int index, + LPVOID pitem) + { + ASSERT(pitem); + ASSERT(IsSA(psa)); + + if (index < 0) + { + TRACE_MSG(TF_ERROR, "SA: Invalid index: %d", index); + return -1; + } + + if (index > psa->cItem) + index = psa->cItem; + + if (psa->cItem + 1 > psa->cItemAlloc) + { + LPVOID aItemNew = MemReAlloc(psa->hheap, psa->aItem, + (psa->cItemAlloc + psa->cItemGrow) * psa->cbItem); + if (!aItemNew) + return -1; + + psa->aItem = aItemNew; + psa->cItemAlloc += psa->cItemGrow; + } + + if (index < psa->cItem) + { + hmemcpy(SA_PITEM(psa, index + 1), SA_PITEM(psa, index), + (psa->cItem - index) * psa->cbItem); + } + psa->cItem++; + hmemcpy(SA_PITEM(psa, index), pitem, psa->cbItem); + + return index; + } + + +/*---------------------------------------------------------- +Purpose: +Returns: +Cond: -- +*/ +BOOL PUBLIC SADeleteItem( + HSA psa, + int index) + { + ASSERT(IsSA(psa)); + + if (index < 0 || index >= psa->cItem) + { + TRACE_MSG(TF_ERROR, "SA: Invalid index: %d", index); + return FALSE; + } + + if (index < psa->cItem - 1) + { + hmemcpy(SA_PITEM(psa, index), SA_PITEM(psa, index + 1), + (psa->cItem - (index + 1)) * psa->cbItem); + } + psa->cItem--; + + if (psa->cItemAlloc - psa->cItem > psa->cItemGrow) + { + LPVOID aItemNew = MemReAlloc(psa->hheap, psa->aItem, + (psa->cItemAlloc - psa->cItemGrow) * psa->cbItem); + + ASSERT(aItemNew); + psa->aItem = aItemNew; + psa->cItemAlloc -= psa->cItemGrow; + } + return TRUE; + } + + +/*---------------------------------------------------------- +Purpose: +Returns: +Cond: -- +*/ +BOOL PUBLIC SADeleteAllItems( + HSA psa) + { + ASSERT(IsSA(psa)); + + if (psa->aItem) + { + MemFree(psa->hheap, psa->aItem); + } + + psa->aItem = NULL; + psa->cItem = psa->cItemAlloc = 0; + return TRUE; + } + + +//================== Dynamic pointer array implementation =========== + +typedef struct _PA { +// NOTE: The following two fields MUST be defined in this order, at +// the beginning of the structure in order for the macro APIs to work. +// + int cp; + LPVOID FAR * pp; + + HANDLE hheap; // Heap to allocate from if NULL use shared + + int cpAlloc; + int cpGrow; + DWORD dwFlags; + +#ifdef DEBUG + UINT magic; +#endif +} PA; + + + +/*---------------------------------------------------------- +Purpose: Creates a pointer array. + +Returns: handle to pointer array + NULL (if out of memory) + +Cond: -- +*/ +HPA PUBLIC PACreate( + int cpGrow, + HANDLE hheap, // Must be non-null if PAF_HEAP set + DWORD dwFlags) // PAF_* + { + HPA ppa; + + ASSERT(hheap && IsFlagSet(dwFlags, SAF_HEAP) || + IsFlagClear(dwFlags, SAF_HEAP)); + + ppa = PrvAlloc(dwFlags, hheap, sizeof(PA)); + +#if !defined(NOSHAREDHEAP) && defined(WIN95) + if (IsFlagSet(dwFlags, PAF_SHARED)) + hheap = g_hSharedHeap; +#endif + + if (ppa) + { + ppa->dwFlags = dwFlags; + ppa->cp = 0; + ppa->cpAlloc = 0; + ppa->cpGrow = (cpGrow < 8 ? 8 : cpGrow); + ppa->pp = NULL; + +#ifdef WIN32 + ppa->hheap = hheap; +#else + ppa->hheap = NULL; +#endif + +#ifdef DEBUG + ppa->magic = PA_MAGIC; +#endif + } + return ppa; + } + + +/*---------------------------------------------------------- +Purpose: Destroy a pointer array, and call the given pfnFree + function for each element in the array. + +Returns: TRUE + FALSE (on failure) + +Cond: -- +*/ +BOOL PUBLIC PADestroyEx( + HPA ppa, + PFNPAFREE pfnFree, + LPARAM lParam) + { + ASSERT(IsPA(ppa)); + + if (ppa == NULL) // allow NULL for low memory cases, still assert + return TRUE; + + if (ppa->pp) + { + if (pfnFree) + { + int i = PAGetCount(ppa) - 1; + + for (; 0 <= i; i--) + { + pfnFree(PAFastGetPtr(ppa, i), lParam); + } + } + + if (!MemFree(ppa->hheap, ppa->pp)) + return FALSE; + } + +#ifdef DEBUG + ppa->cp = 0; + ppa->cpAlloc = 0; + ppa->magic = 0; +#endif + + return MemFree(ppa->hheap, ppa); + } + + +/*---------------------------------------------------------- +Purpose: Clone a pointer array + +Returns: pointer to new array + NULL (if out of memory) + +Cond: -- +*/ +HPA PUBLIC PAClone( + HPA ppa, + HPA ppaNew) + { + BOOL fAlloc = FALSE; + + if (!ppaNew) + { + ppaNew = PACreate(ppa->cpGrow, ppa->hheap, ppa->dwFlags); + if (!ppaNew) + return NULL; + + fAlloc = TRUE; + } + + if (!PAGrow(ppaNew, ppa->cpAlloc)) + { + if (fAlloc) + PADestroy(ppaNew); + return NULL; + } + + ppaNew->cp = ppa->cp; + hmemcpy(ppaNew->pp, ppa->pp, ppa->cp * sizeof(LPVOID)); + + return ppaNew; + } + + +/*---------------------------------------------------------- +Purpose: Get a pointer stored in index + +Returns: stored pointer +Cond: -- +*/ +LPVOID PUBLIC PAGetPtr( + HPA ppa, + int index) + { + ASSERT(IsPA(ppa)); + + if (index < 0 || index >= ppa->cp) + return NULL; + + return ppa->pp[index]; + } + + +/*---------------------------------------------------------- +Purpose: Gets the index that pointer p is stored at + +Returns: index +Cond: -- +*/ +int PUBLIC PAGetPtrIndex( + HPA ppa, + LPVOID p) + { + LPVOID FAR * pp; + LPVOID FAR * ppMax; + + ASSERT(IsPA(ppa)); + if (ppa->pp) + { + pp = ppa->pp; + ppMax = pp + ppa->cp; + for ( ; pp < ppMax; pp++) + { + if (*pp == p) + return (pp - ppa->pp); + } + } + return -1; + } + + +/*---------------------------------------------------------- +Purpose: Grow the pointer array + +Returns: +Cond: -- +*/ +BOOL PUBLIC PAGrow( + HPA ppa, + int cpAlloc) + { + ASSERT(IsPA(ppa)); + + if (cpAlloc > ppa->cpAlloc) + { + LPVOID FAR * ppNew; + + cpAlloc = ((cpAlloc + ppa->cpGrow - 1) / ppa->cpGrow) * ppa->cpGrow; + + if (ppa->pp) + ppNew = (LPVOID FAR *)MemReAlloc(ppa->hheap, ppa->pp, cpAlloc * sizeof(LPVOID)); + else + ppNew = (LPVOID FAR *)PrvAlloc(ppa->dwFlags, ppa->hheap, cpAlloc * sizeof(LPVOID)); + if (!ppNew) + return FALSE; + + ppa->pp = ppNew; + ppa->cpAlloc = cpAlloc; + } + return TRUE; + } + + +/*---------------------------------------------------------- +Purpose: Store a pointer at index. Grows the array accordingly. + +Returns: TRUE + FALSE (if out of memory) +Cond: -- +*/ +BOOL PUBLIC PASetPtr( + HPA ppa, + int index, + LPVOID p) + { + ASSERT(IsPA(ppa)); + + if (index < 0) + { + TRACE_MSG(TF_ERROR, "PA: Invalid index: %d", index); + return FALSE; + } + + if (index >= ppa->cp) + { + if (!PAGrow(ppa, index + 1)) + return FALSE; + ppa->cp = index + 1; + } + + ppa->pp[index] = p; + + return TRUE; + } + + +/*---------------------------------------------------------- +Purpose: Inserts a pointer at index. If index is beyond the + current size of array, this function appends the + pointer to the end of the array. + +Returns: index pointer is stored in + PA_ERR + +Cond: -- +*/ +int PUBLIC PAInsertPtr( + HPA ppa, + int index, + LPVOID p) + { + ASSERT(IsPA(ppa)); + + if (index < 0) + { + TRACE_MSG(TF_ERROR, "PA: Invalid index: %d", index); + return -1; + } + if (index > ppa->cp) + index = ppa->cp; + + // Make sure we have room for one more item + // + if (ppa->cp + 1 > ppa->cpAlloc) + { + if (!PAGrow(ppa, ppa->cp + 1)) + return -1; + } + + // If we are inserting, we need to slide everybody up + // + if (index < ppa->cp) + { + hmemcpy(&ppa->pp[index + 1], &ppa->pp[index], + (ppa->cp - index) * sizeof(LPVOID)); + } + + ppa->pp[index] = p; + ppa->cp++; + + return index; + } + + +/*---------------------------------------------------------- +Purpose: Delete a pointer from index. + +Returns: the deleted pointer + NULL (if index is out of range) + +Cond: -- +*/ +LPVOID PUBLIC PADeletePtr( + HPA ppa, + int index) + { + LPVOID p; + + ASSERT(IsPA(ppa)); + + if (index < 0 || index >= ppa->cp) + { + TRACE_MSG(TF_ERROR, "PA: Invalid index: %d", index); + return NULL; + } + + p = ppa->pp[index]; + + if (index < ppa->cp - 1) + { + hmemcpy(&ppa->pp[index], &ppa->pp[index + 1], + (ppa->cp - (index + 1)) * sizeof(LPVOID)); + } + ppa->cp--; + + if (ppa->cpAlloc - ppa->cp > ppa->cpGrow) + { + LPVOID FAR * ppNew; + ppNew = MemReAlloc(ppa->hheap, ppa->pp, (ppa->cpAlloc - ppa->cpGrow) * sizeof(LPVOID)); + + ASSERT(ppNew); + ppa->pp = ppNew; + ppa->cpAlloc -= ppa->cpGrow; + } + return p; + } + + +/*---------------------------------------------------------- +Purpose: Delete all the pointers in the array. If pfnFree + is non-NULL, this function will free each of the + pointer elements in this array using pfnFree. + +Returns: TRUE + FALSE + +Cond: -- +*/ +BOOL PUBLIC PADeleteAllPtrsEx( + HPA ppa, + PFNPAFREE pfnFree, + LPARAM lParam) + { + ASSERT(IsPA(ppa)); + + if (ppa->pp) + { + if (pfnFree) + { + int i = PAGetCount(ppa) - 1; + + for (; 0 <= i; i--) + { + pfnFree(PAFastGetPtr(ppa, i), lParam); + } + } + + if (!MemFree(ppa->hheap, ppa->pp)) + return FALSE; + } + + ppa->pp = NULL; + ppa->cp = ppa->cpAlloc = 0; + return TRUE; + } + + +/*---------------------------------------------------------- +Purpose: Sort the array. + +Returns: +Cond: -- +*/ +BOOL PUBLIC PASort( + HPA ppa, + PFNPACOMPARE pfnCmp, + LPARAM lParam) + { + SORTPARAMS sp; + + sp.cp = ppa->cp; + sp.pp = ppa->pp; + sp.pfnCmp = pfnCmp; + sp.lParam = lParam; + +#ifdef USEQUICKSORT + return PAQuickSort(&sp); +#endif +#ifdef USEHEAPSORT + return PAHeapSort(&sp); +#endif +#ifdef MERGESORT + return PAMergeSort(&sp); +#endif + } + +#ifdef USEQUICKSORT + +BOOL NEAR PAQuickSort(SORTPARAMS FAR* psp) +{ + return PAQuickSort2(0, psp->cp - 1, psp); +} + +BOOL NEAR PAQuickSort2(int i, int j, SORTPARAMS FAR* psp) +{ + LPVOID FAR * pp = psp->pp; + LPARAM lParam = psp->lParam; + PFNPACOMPARE pfnCmp = psp->pfnCmp; + + int iPivot; + LPVOID pFirst; + int k; + int result; + + iPivot = -1; + pFirst = pp[i]; + for (k = i + 1; k <= j; k++) + { + result = (*pfnCmp)(pp[k], pFirst, lParam); + + if (result > 0) + { + iPivot = k; + break; + } + else if (result < 0) + { + iPivot = i; + break; + } + } + + if (iPivot != -1) + { + int l = i; + int r = j; + LPVOID pivot = pp[iPivot]; + + do + { + LPVOID p; + + p = pp[l]; + pp[l] = pp[r]; + pp[r] = p; + + while ((*pfnCmp)(pp[l], pivot, lParam) < 0) + l++; + while ((*pfnCmp)(pp[r], pivot, lParam) >= 0) + r--; + } while (l <= r); + + if (l - 1 > i) + PAQuickSort2(i, l - 1, psp); + if (j > l) + PAQuickSort2(l, j, psp); + } + return TRUE; +} +#endif // USEQUICKSORT + +#ifdef USEHEAPSORT + +void NEAR PAHeapSortPushDown(int first, int last, SORTPARAMS FAR* psp) +{ + LPVOID FAR * pp = psp->pp; + LPARAM lParam = psp->lParam; + PFNPACOMPARE pfnCmp = psp->pfnCmp; + int r; + int r2; + LPVOID p; + + r = first; + while (r <= last / 2) + { + int wRTo2R; + r2 = r * 2; + + wRTo2R = (*pfnCmp)(pp[r-1], pp[r2-1], lParam); + + if (r2 == last) + { + if (wRTo2R < 0) + { + p = pp[r-1]; pp[r-1] = pp[r2-1]; pp[r2-1] = p; + } + break; + } + else + { + int wR2toR21 = (*pfnCmp)(pp[r2-1], pp[r2+1-1], lParam); + + if (wRTo2R < 0 && wR2toR21 >= 0) + { + p = pp[r-1]; pp[r-1] = pp[r2-1]; pp[r2-1] = p; + r = r2; + } + else if ((*pfnCmp)(pp[r-1], pp[r2+1-1], lParam) < 0 && wR2toR21 < 0) + { + p = pp[r-1]; pp[r-1] = pp[r2+1-1]; pp[r2+1-1] = p; + r = r2 + 1; + } + else + { + break; + } + } + } +} + +BOOL NEAR PAHeapSort(SORTPARAMS FAR* psp) +{ + LPVOID FAR * pp = psp->pp; + int c = psp->cp; + int i; + + for (i = c / 2; i >= 1; i--) + PAHeapSortPushDown(i, c, psp); + + for (i = c; i >= 2; i--) + { + LPVOID p = pp[0]; pp[0] = pp[i-1]; pp[i-1] = p; + + PAHeapSortPushDown(1, i - 1, psp); + } + return TRUE; +} +#endif // USEHEAPSORT + +#if defined(MERGESORT) && defined(WIN32) + +#define SortCompare(psp, pp1, i1, pp2, i2) \ + (psp->pfnCmp(pp1[i1], pp2[i2], psp->lParam)) + +// +// This function merges two sorted lists and makes one sorted list. +// psp->pp[iFirst, iFirst+cItes/2-1], psp->pp[iFirst+cItems/2, iFirst+cItems-1] +// +void NEAR PAMergeThem(SORTPARAMS FAR* psp, int iFirst, int cItems) +{ + // + // Notes: + // This function is separated from PAMergeSort2() to avoid comsuming + // stack variables. Never inline this. + // + int cHalf = cItems/2; + int iIn1, iIn2, iOut; + LPVOID FAR * ppvSrc = &psp->pp[iFirst]; + + // Copy the first part to temp storage so we can write directly into + // the final buffer. Note that this takes at most psp->cp/2 DWORD's + hmemcpy(psp->ppT, ppvSrc, cHalf*sizeof(LPVOID)); + + for (iIn1=0, iIn2=cHalf, iOut=0;;) + { + if (SortCompare(psp, psp->ppT, iIn1, ppvSrc, iIn2) <= 0) { + ppvSrc[iOut++] = psp->ppT[iIn1++]; + + if (iIn1==cHalf) { + // We used up the first half; the rest of the second half + // should already be in place + break; + } + } else { + ppvSrc[iOut++] = ppvSrc[iIn2++]; + if (iIn2==cItems) { + // We used up the second half; copy the rest of the first half + // into place + hmemcpy(&ppvSrc[iOut], &psp->ppT[iIn1], (cItems-iOut)*sizeof(LPVOID)); + break; + } + } + } +} + +// +// This function sorts a give list (psp->pp[iFirst,iFirst-cItems-1]). +// +void NEAR PAMergeSort2(SORTPARAMS FAR* psp, int iFirst, int cItems) +{ + // + // Notes: + // This function is recursively called. Therefore, we should minimize + // the number of local variables and parameters. At this point, we + // use one local variable and three parameters. + // + int cHalf; + + switch(cItems) + { + case 1: + return; + + case 2: + // Swap them, if they are out of order. + if (SortCompare(psp, psp->pp, iFirst, psp->pp, iFirst+1) > 0) + { + psp->ppT[0] = psp->pp[iFirst]; + psp->pp[iFirst] = psp->pp[iFirst+1]; + psp->pp[iFirst+1] = psp->ppT[0]; + } + break; + + default: + cHalf = cItems/2; + // Sort each half + PAMergeSort2(psp, iFirst, cHalf); + PAMergeSort2(psp, iFirst+cHalf, cItems-cHalf); + // Then, merge them. + PAMergeThem(psp, iFirst, cItems); + break; + } +} + +BOOL NEAR PAMergeSort(SORTPARAMS FAR* psp) +{ + if (psp->cp==0) + return TRUE; + + // Note that we divide by 2 below; we want to round down + psp->ppT = LocalAlloc(LPTR, psp->cp/2 * sizeof(LPVOID)); + if (!psp->ppT) + return FALSE; + + PAMergeSort2(psp, 0, psp->cp); + LocalFree(psp->ppT); + return TRUE; +} +#endif // MERGESORT + +// Search function +// +int PUBLIC PASearch(HPA ppa, LPVOID pFind, int iStart, + PFNPACOMPARE pfnCompare, LPARAM lParam, UINT options) +{ + int cp = PAGetCount(ppa); + + ASSERT(pfnCompare); + ASSERT(0 <= iStart); + + // Only allow these wierd flags if the list is sorted + ASSERT((options & PAS_SORTED) || !(options & (PAS_INSERTBEFORE | PAS_INSERTAFTER))); + + if (!(options & PAS_SORTED)) + { + // Not sorted: do linear search. + int i; + + for (i = iStart; i < cp; i++) + { + if (0 == pfnCompare(pFind, PAFastGetPtr(ppa, i), lParam)) + return i; + } + return -1; + } + else + { + // Search the array using binary search. If several adjacent + // elements match the target element, the index of the first + // matching element is returned. + + int iRet = -1; // assume no match + BOOL bFound = FALSE; + int nCmp = 0; + int iLow = 0; // Don't bother using iStart for binary search + int iMid = 0; + int iHigh = cp - 1; + + // (OK for cp == 0) + while (iLow <= iHigh) + { + iMid = (iLow + iHigh) / 2; + + nCmp = pfnCompare(pFind, PAFastGetPtr(ppa, iMid), lParam); + + if (0 > nCmp) + iHigh = iMid - 1; // First is smaller + else if (0 < nCmp) + iLow = iMid + 1; // First is larger + else + { + // Match; search back for first match + bFound = TRUE; + while (0 < iMid) + { + if (0 != pfnCompare(pFind, PAFastGetPtr(ppa, iMid-1), lParam)) + break; + else + iMid--; + } + break; + } + } + + if (bFound) + { + ASSERT(0 <= iMid); + iRet = iMid; + } + + // Did the search fail AND + // is one of the strange search flags set? + if (!bFound && (options & (PAS_INSERTAFTER | PAS_INSERTBEFORE))) + { + // Yes; return the index where the target should be inserted + // if not found + if (0 < nCmp) // First is larger + iRet = iLow; + else + iRet = iMid; + // (We don't distinguish between the two flags anymore) + } + else if ( !(options & (PAS_INSERTAFTER | PAS_INSERTBEFORE)) ) + { + // Sanity check with linear search + ASSERT(PASearch(ppa, pFind, iStart, pfnCompare, lParam, options & ~PAS_SORTED) == iRet); + } + return iRet; + } +} + +#endif // NODA + +#endif // NOMEM |