RICHEDIT: optimize the CharList structure (take 2)
Mike McCormack
mike at codeweavers.com
Tue Feb 3 14:58:09 CST 2004
ChangeLog:
* Convert richedit's charlist structure from a linked list to a buffer
to improve speed
-------------- next part --------------
Index: dlls/richedit/charlist.c
===================================================================
RCS file: /home/wine/wine/dlls/richedit/charlist.c,v
retrieving revision 1.7
diff -u -r1.7 charlist.c
--- dlls/richedit/charlist.c 5 Sep 2003 23:08:32 -0000 1.7
+++ dlls/richedit/charlist.c 3 Feb 2004 19:54:51 -0000
@@ -35,118 +35,93 @@
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;
- }
-
- pCharList->nCount++;
-}
+#define CHUNKSIZE 0x1000
-void CHARLIST_Push( CHARLIST* pCharList, char myChar)
+void CHARLIST_Enqueue( CHARLIST* pcl, char ch )
{
- CHARLISTENTRY* pNewEntry = malloc(sizeof(CHARLISTENTRY));
+ int ofs, sz;
- TRACE("\n");
-
- pNewEntry->myChar = myChar;
-
- if(pCharList->pHead == NULL)
+ if( !pcl->buffer )
{
- pCharList->pHead = pCharList->pTail = pNewEntry;
- pNewEntry->pNext = NULL;
-
+ pcl->nMaxCount = CHUNKSIZE;
+ pcl->buffer = HeapAlloc( RICHED32_hHeap, 0, pcl->nMaxCount );
}
- else
+ /* check if we need to add more memory */
+ if( pcl->nCount == pcl->nMaxCount )
{
- pNewEntry->pNext = pCharList->pHead;
- pCharList->pHead = pNewEntry;
+ pcl->nMaxCount += CHUNKSIZE;
+ pcl->buffer = HeapReAlloc( RICHED32_hHeap, 0,
+ pcl->buffer, pcl->nMaxCount );
+ sz = pcl->nHead - pcl->nCount;
+ if( sz > 0 )
+ {
+ memmove( &pcl->buffer[pcl->nMaxCount - sz],
+ &pcl->buffer[pcl->nMaxCount - CHUNKSIZE - sz], sz);
+ }
}
-
- pCharList->nCount++;
+ ofs = (pcl->nHead + pcl->nCount)%pcl->nMaxCount;
+ pcl->buffer[ofs] = ch;
+ pcl->nCount++;
}
-char CHARLIST_Dequeue(CHARLIST* pCharList)
+char CHARLIST_Dequeue(CHARLIST* pcl)
{
- CHARLISTENTRY* pCurrent;
- char myChar;
-
- TRACE("\n");
-
- if(pCharList->nCount == 0)
- return 0;
+ char ch;
- pCharList->nCount--;
- myChar = pCharList->pHead->myChar;
- pCurrent = pCharList->pHead->pNext;
- HeapFree(RICHED32_hHeap, 0,pCharList->pHead);
+ if(pcl->nCount == 0)
+ return 0;
- if(pCharList->nCount == 0)
- {
- pCharList->pHead = pCharList->pTail = NULL;
- }
- else
- {
- pCharList->pHead = pCurrent;
- }
-
- return myChar;
+ ch = pcl->buffer[pcl->nHead++];
+ pcl->nCount--;
+ if( pcl->nHead > pcl->nMaxCount )
+ pcl->nHead = 0;
+ return ch;
}
-int CHARLIST_GetNbItems(CHARLIST* pCharList)
+int CHARLIST_GetNbItems(CHARLIST* pcl)
{
TRACE("\n");
- return pCharList->nCount;
+ return pcl->nCount;
}
-void CHARLIST_FreeList(CHARLIST* pCharList){
+void CHARLIST_FreeList(CHARLIST* pcl){
TRACE("\n");
- while(pCharList->nCount)
- CHARLIST_Dequeue(pCharList);
+ HeapFree( RICHED32_hHeap, 0, pcl->buffer );
+ pcl->buffer = 0;
+ pcl->nCount = 0;
+ pcl->nMaxCount = 0;
+ pcl->nHead = 0;
}
/* this function counts the number of occurrences of a caracter */
-int CHARLIST_CountChar(CHARLIST* pCharList, char myChar)
+int CHARLIST_CountChar(CHARLIST* pcl, 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<pcl->nCount; i++)
+ if(pcl->buffer[i]== myChar)
nCount++;
return nCount;
}
-int CHARLIST_toBuffer(CHARLIST* pCharList, char* pBuffer, int nBufferSize)
+int CHARLIST_toBuffer(CHARLIST* pcl, char* pBuffer, int nBufferSize)
{
-
- TRACE("\n");
+ int 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);
+ if(nBufferSize < pcl->nCount + 1)
+ return pcl->nCount;
+ while( pcl->nCount )
+ {
+ *pBuffer++ = pcl->buffer[pcl->nHead++];
+ if( pcl->nHead >= pcl->nMaxCount )
+ pcl->nHead = 0;
+ pcl->nCount--;
+ }
*pBuffer = '\0';
return 0;
Index: dlls/richedit/charlist.h
===================================================================
RCS file: /home/wine/wine/dlls/richedit/charlist.h,v
retrieving revision 1.5
diff -u -r1.5 charlist.h
--- dlls/richedit/charlist.h 28 Jun 2002 17:37:34 -0000 1.5
+++ dlls/richedit/charlist.h 3 Feb 2004 19:54:51 -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