Solved

VB6 Problem with array memory copy operation in simple stack (FIFO) implementation

Posted on 2007-12-04
5
1,459 Views
Last Modified: 2013-11-25
Hi,

I am trying to implement a simple constant size stack that holds constant size strings.
It has Pop method that returns empty string until stack is full and then it starts returning oldest items on the stack. It works fine the first time it has to return the item, but then it starts returning rubbish.
The problem is in CopyMemory API call.
However, copying array in a loop beats the purpose of the stack, since it has to be efficient.
Where lays the problem? Is there some other efficient way to copy array?

Thank you!

I have implemented it this way (see attached snippet and ignore colouring)




'start of class

Private stack() As String

 

Private size_ As Integer

 

Private count_ As Integer

 

Public Sub Initialize(size As Integer)

    size_ = size

    ReDim stack(size_ - 1)

End Sub

 

Public Function Pop(push As String) As String

    If count_ < size_ Then

        stack(count_) = push

        count_ = count_ + 1

        Pop = ""

    Else

        Dim popResult As String

        popResult = stack(0)

        Dim tempStack() As String

        ReDim tempStack(size_ - 1)

        'copy to temp array but leave out the oldest item (source is stack(1))

        CopyMemory VarPtr(tempStack(0)), VarPtr(stack(1)), Len(popResult) * (size_ - 1)

        'put new item at the end of stack

        tempStack(size_ - 1) = push

        'copy temp array back to stack

        CopyMemory VarPtr(stack(0)), VarPtr(tempStack(0)), Len(popResult) * size_

        Pop = popResult

    End If

    

End Function

 

Public Function ToArray() As String()

    ToArray = stack()

End Function



'end of class of class

 

 

' I have declared CopyMemory API function in module as this:

 

Declare Sub CopyMemory Lib "kernel32" Alias "RtlMoveMemory" _

    (ByVal pDestination As Long, ByVal pSource As Long, ByVal ByteLen As Long)

 

 

'Finally, here is some test code, paste it into a form:

 

Private Sub testStack_Click()

    Dim stack As New ConstSizeStringStack

    stack.Initialize (5)

    

    Dim i As Integer

    For i = 0 To 8

        Dim itm As String * 10

        itm = "STR" & CStr(i)

         'prints nothing after returning STR0 and the content of internal 

         'stack array in debbuger shows error

        Debug.Print stack.Pop(itm)

    Next i

    

    

    Dim strs() As String

    strs = stack.ToArray

    

    Dim j As Integer

    For j = LBound(strs) To UBound(strs)

        Debug.Print strs(j)

    Next j

    

End Sub

Open in new window

0
Comment
Question by:Damn
  • 3
  • 2
5 Comments
 
LVL 85

Expert Comment

by:Mike Tomlinson
ID: 20405560
You have incorrectly assumed that the strings are actually being stored in your string array.

THEY ARE NOT...

POINTERS to the strings are what really get stored in the string array...so each entry in the string array is really a LONG value (4 bytes long).  You would need to modify the CopyMemory() calls to change the length to copy.  This should be 4 * (the number of elements to copy).

I fiddled with it a bit but couldn't the arrays to copy the last element properly for some reason.

In the meantime...how about this appproach as an alternative?
(really don't know what your end goal is so this might not be appropriate)
' ------------------------------

'  Form1

' ------------------------------

Private Sub Command1_Click()

    Dim stack As New ConstSizeStringStack

    stack.Initialize 5

    

    Dim i As Integer

    For i = 0 To 8

        Dim itm As String * 10

        itm = "STR" & CStr(i)

        Dim rtn As String

        rtn = stack.Pop(itm)

        Debug.Print "Returned: " & rtn

    Next i

    

    ' show what is currently in the stack

    Dim value As Variant

    For Each value In stack

        Debug.Print value

    Next

End Sub
 

' ------------------------------

'  Class ConstSizeStringStack

' ------------------------------

Option Explicit
 

Private size_ As Integer

Private stack As Collection

 

Private Sub Class_Initialize()

    size_ = 1

    Set stack = New Collection

End Sub

 

Public Sub Initialize(size As Integer)

    size_ = size

    Set stack = New Collection

End Sub

 

Public Function Pop(push As String) As String

    If stack.Count = size_ Then

        ' a Collection is ONE based

        Pop = stack.Item(1)

        stack.Remove 1

    End If

    stack.Add push

End Function
 

Public Property Get NewEnum() As IUnknown

    ' Click on Tools --> Procedure Attributes

    ' Select "NewEnum" in the DropDown

    ' Now Click on the "Advanced" Button

    ' Change the "Procedure ID" to "-4"

   Set NewEnum = stack.[_NewEnum]

End Property

Open in new window

0
 

Author Comment

by:Damn
ID: 20406720
Idle_Mind,

Thanks for your comment.
I tried what you suggested, but the result is the same. The first time I loop over second Part of Pop method with CopyMemory call it works fine, (as seen in debugger), but the next time I call the Pop method, I get all kind of garbage inside stack() array.
I need very efficient implementation, so your Collection-based does not work for me.

Thank you
0
 
LVL 85

Accepted Solution

by:
Mike Tomlinson earned 500 total points
ID: 20407054
"I need very efficient implementation, so your Collection-based does not work for me."

How is the Collection-based approach not efficient?  It internally uses a Linked-List implementation so there is NO need to shuffle and/or copy the elements as items are added/removed.

Could you be a little more specific as why the collection won't work?...i.e. perhaps the bigger picture of your app?

Have you tried benchmarking it to see what kind of performance it has?

...and I won't be offended at all if you decide not to use the Collection approach!
0
 

Author Comment

by:Damn
ID: 20411145
Hello Idle_Mind,

Since you seem idle enough, this is what I am trying to accomplish...

I am trying to implement a simple LRU cache, based on Scripting.Dictionary object. Therefore I need an efficient way to find oldest items in the Dictionary. I tried looping over items in Dictionary, but that is vastly inefficient. (I am holding my cached object inside custom CacheItem, that is time-stamped on creation&).
Other way to track order by which items were added to cache is to place string key into the FIFO, as I explained in the post.
Let me test your solution, and if I find that your Collection based solution is performant enough, no dogma on my part and I will give you the points.


' Class Cache
 

'Simple LRU cache based on Scripting.Dictionary
 

Option Explicit
 

Private size_ As Integer

Private dictionary As Scripting.dictionary

Private keyStack As New ConstSizeStringStack
 

Private hitCount As Long

Private missCount As Long
 

Public Function GetFromCache(key As String) As Object

    If dictionary.Exists(key) Then

        Set GetFromCache = dictionary.Item(key).ItemInCache

    Else

        Set GetFromCache = Nothing

    End If

End Function
 

'OLD , too slow

Public Sub PutToCache2(key As String, object As Object)

    Dim cItem As New CacheItem

    If dictionary.Exists(key) Then

        dictionary.Remove (key)

    End If

    cItem.ItemInCache = object

    If dictionary.Count >= size_ Then

        dictionary.Remove (FindOldestItemKey())

    End If

    dictionary.Add key, cItem

End Sub
 

Public Sub PutToCache(key As String, object As Object)

    If keyStack.Pop(key) = "" Then

        dictionary.Add key, object

    Else

        dictionary.Remove (keyStack.Pop(key))

        dictionary.Add key, object

    End If

End Sub
 
 

Public Function InCache(key As String) As Boolean

    InCache = dictionary.Exists(key)

End Function
 

Private Sub Class_Initialize()

    'set default size

    size_ = 1001

    keyStack.Initialize (1001)

    Set dictionary = CreateObject("Scripting.Dictionary")

    dictionary.CompareMode = vbTextCompare

End Sub
 

Public Property Get size() As Integer

    size = size_

End Property
 
 

'VERY slow

Public Function FindOldestItemKey() As String

    Dim oldestKey As String

    Dim oldest As CacheItem

    Dim key As String

    oldestKey = ""

    Dim i As Integer

    

    For i = 0 To UBound(dictionary.Keys)

        key = dictionary.Keys(i)

        If oldestKey = "" Then

            oldestKey = key

            Set oldest = dictionary.Item(key)

        Else

            If CDbl(dictionary.Item(key).InCacheDate) > CDbl(oldest.InCacheDate) Then

                oldestKey = key

                Set oldest = dictionary.Item(key)

            End If

        End If

    Next i

    FindOldestItemKey = oldestKey

End Function
 
 

Public Sub Clear()

    dictionary.RemoveAll

End Sub
 
 

Private Sub Miss()

    On Error Resume Next

    missCount = missCount + 1

End Sub
 

Private Sub Hit()

    On Error Resume Next

    hitCount = hitCount + 1

End Sub
 

Public Sub Initialize(size As Integer)

    On Error Resume Next

    size_ = size

    keyStack.Initialize (size)

End Sub

Open in new window

0
 

Author Closing Comment

by:Damn
ID: 31412594
Idle_Mind:
I found your solution satisfactory for my needs. Thank you.
0

Featured Post

Why You Should Analyze Threat Actor TTPs

After years of analyzing threat actor behavior, it’s become clear that at any given time there are specific tactics, techniques, and procedures (TTPs) that are particularly prevalent. By analyzing and understanding these TTPs, you can dramatically enhance your security program.

Join & Write a Comment

Introduction While answering a recent question about filtering a custom class collection, I realized that this could be accomplished with very little code by using the ScriptControl (SC) library.  This article will introduce you to the SC library a…
I was working on a PowerPoint add-in the other day and a client asked me "can you implement a feature which processes a chart when it's pasted into a slide from another deck?". It got me wondering how to hook into built-in ribbon events in Office.
Get people started with the utilization of class modules. Class modules can be a powerful tool in Microsoft Access. They allow you to create self-contained objects that encapsulate functionality. They can easily hide the complexity of a process from…
Show developers how to use a criteria form to limit the data that appears on an Access report. It is a common requirement that users can specify the criteria for a report at runtime. The easiest way to accomplish this is using a criteria form that a…

706 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

15 Experts available now in Live!

Get 1:1 Help Now