RICHEDIT: optimize the CharList structure (take 2)

[Mike McCormack]

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);