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