RICHEDIT: convert the charlist structure from a linked list to a
buffer to improve speed
Mike McCormack
mike at codeweavers.com
Mon Feb 2 18:12:42 CST 2004
ChangeLog:
* Convert richedit's charlist structure from a linked list to a buffer
to improve speed
-------------- next part --------------
? dlls/richedit/x
Index: dlls/richedit/charlist.c
===================================================================
RCS file: /cvstrees/crossover/office/wine/dlls/richedit/charlist.c,v
retrieving revision 1.1.1.5
diff -u -r1.1.1.5 charlist.c
--- dlls/richedit/charlist.c 12 Sep 2003 18:37:28 -0000 1.1.1.5
+++ dlls/richedit/charlist.c 2 Feb 2004 23:09:03 -0000
@@ -35,75 +35,47 @@
extern HANDLE RICHED32_hHeap;
-void CHARLIST_Enqueue( CHARLIST* pCharList, char myChar )
-{
- CHARLISTENTRY* pNewEntry = HeapAlloc(RICHED32_hHeap, 0,sizeof(CHARLISTENTRY));
- pNewEntry->pNext = NULL;
- pNewEntry->myChar = myChar;
-
- TRACE("\n");
-
- if(pCharList->pTail == NULL)
- {
- pCharList->pHead = pCharList->pTail = pNewEntry;
- }
- else
- {
- CHARLISTENTRY* pCurrent = pCharList->pTail;
- pCharList->pTail = pCurrent->pNext = pNewEntry;
- }
+#define CHUNKSIZE 0x1000
- pCharList->nCount++;
-}
-
-void CHARLIST_Push( CHARLIST* pCharList, char myChar)
+void CHARLIST_Enqueue( CHARLIST* pCharList, char ch )
{
- CHARLISTENTRY* pNewEntry = malloc(sizeof(CHARLISTENTRY));
+ int ofs, sz;
- TRACE("\n");
-
- pNewEntry->myChar = myChar;
-
- if(pCharList->pHead == NULL)
+ if( !pCharList->buffer )
{
- pCharList->pHead = pCharList->pTail = pNewEntry;
- pNewEntry->pNext = NULL;
-
+ pCharList->nMaxCount = CHUNKSIZE;
+ pCharList->buffer = HeapAlloc( RICHED32_hHeap, 0, pCharList->nMaxCount );
}
- else
+ /* check if we need to add more memory */
+ if( pCharList->nCount == pCharList->nMaxCount )
{
- pNewEntry->pNext = pCharList->pHead;
- pCharList->pHead = pNewEntry;
+ pCharList->nMaxCount += CHUNKSIZE;
+ pCharList->buffer = HeapReAlloc( RICHED32_hHeap, 0,
+ pCharList->buffer, pCharList->nMaxCount );
+ sz = pCharList->nHead - pCharList->nCount;
+ if( sz > 0 )
+ {
+ memmove( &pCharList->buffer[pCharList->nMaxCount - sz],
+ &pCharList->buffer[pCharList->nMaxCount - CHUNKSIZE - sz], sz);
+ }
}
-
+ ofs = pCharList->nHead + (pCharList->nCount%pCharList->nMaxCount);
+ pCharList->buffer[ofs] = ch;
pCharList->nCount++;
}
char CHARLIST_Dequeue(CHARLIST* pCharList)
{
- CHARLISTENTRY* pCurrent;
- char myChar;
-
- TRACE("\n");
+ char ch;
if(pCharList->nCount == 0)
- return 0;
+ return 0;
+ ch = pCharList->buffer[pCharList->nHead++];
pCharList->nCount--;
- myChar = pCharList->pHead->myChar;
- pCurrent = pCharList->pHead->pNext;
- HeapFree(RICHED32_hHeap, 0,pCharList->pHead);
-
- if(pCharList->nCount == 0)
- {
- pCharList->pHead = pCharList->pTail = NULL;
- }
- else
- {
- pCharList->pHead = pCurrent;
- }
-
- return myChar;
+ if( pCharList->nHead > pCharList->nMaxCount )
+ pCharList->nHead = 0;
+ return ch;
}
int CHARLIST_GetNbItems(CHARLIST* pCharList)
@@ -116,20 +88,19 @@
void CHARLIST_FreeList(CHARLIST* pCharList){
TRACE("\n");
- while(pCharList->nCount)
- CHARLIST_Dequeue(pCharList);
+ HeapFree( RICHED32_hHeap, 0, pCharList->buffer );
+ pCharList->nCount = 0;
+ pCharList->nMaxCount = 0;
+ pCharList->nHead = 0;
}
/* this function counts the number of occurrences of a caracter */
int CHARLIST_CountChar(CHARLIST* pCharList, char myChar)
{
- CHARLISTENTRY *pCurrent;
- int nCount = 0;
-
- TRACE("\n");
+ int i, nCount = 0;
- for(pCurrent =pCharList->pHead ;pCurrent;pCurrent=pCurrent->pNext)
- if(pCurrent->myChar == myChar)
+ for(i=0; i<pCharList->nCount; i++)
+ if(pCharList->buffer[i]== myChar)
nCount++;
return nCount;
@@ -137,17 +108,14 @@
int CHARLIST_toBuffer(CHARLIST* pCharList, char* pBuffer, int nBufferSize)
{
-
- TRACE("\n");
-
/* we add one to store a NULL caracter */
if(nBufferSize < pCharList->nCount + 1)
return pCharList->nCount;
- for(;pCharList->nCount;pBuffer++)
- *pBuffer = CHARLIST_Dequeue(pCharList);
-
- *pBuffer = '\0';
+ //for(;pCharList->nCount;pBuffer++)
+ // *pBuffer = pCharList->buffer[pCharList->nCount--];
+ memcpy(pBuffer, pCharList->buffer, pCharList->nCount );
+ pBuffer[pCharList->nCount] = '\0';
return 0;
}
Index: dlls/richedit/charlist.h
===================================================================
RCS file: /cvstrees/crossover/office/wine/dlls/richedit/charlist.h,v
retrieving revision 1.1.1.4
diff -u -r1.1.1.4 charlist.h
--- dlls/richedit/charlist.h 11 Jul 2002 22:16:57 -0000 1.1.1.4
+++ dlls/richedit/charlist.h 2 Feb 2004 23:09:03 -0000
@@ -21,22 +21,16 @@
#ifndef _CHARLIST
#define _CHARLIST
-typedef struct _tagCHARLISTENTRY
-{
- struct _tagCHARLISTENTRY *pNext;
- char myChar;
-} CHARLISTENTRY;
-
typedef struct _tagCHARLIST
{
+ unsigned int nHead;
unsigned int nCount; /* Entries Count; */
- CHARLISTENTRY *pHead;
- CHARLISTENTRY *pTail;
+ unsigned int nMaxCount;
+ char *buffer;
} CHARLIST;
void CHARLIST_Enqueue( CHARLIST* pCharList, char myChar);
-void CHARLIST_Push( CHARLIST* pCharList, char myChar);
char CHARLIST_Dequeue(CHARLIST* pCharList);
int CHARLIST_GetNbItems(CHARLIST* pCharList);
void CHARLIST_FreeList(CHARLIST* pCharList);
More information about the wine-patches
mailing list