Expiring Today—Celebrate National IT Professionals Day with 3 months of free Premium Membership. Use Code ITDAY17

x
?
Solved

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

Posted on 2007-12-04
5
Medium Priority
?
1,529 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
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 3
  • 2
5 Comments
 
LVL 86

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 86

Accepted Solution

by:
Mike Tomlinson earned 2000 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

Concerto's Cloud Advisory Services

Want to avoid the missteps to gaining all the benefits of the cloud? Learn more about the different assessment options from our Cloud Advisory team.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Introduction In a recent article (http://www.experts-exchange.com/A_7811-A-Better-Concatenate-Function.html) for the Excel community, I showed an improved version of the Excel Concatenate() function.  While writing that article I realized that no o…
You can of course define an array to hold data that is of a particular type like an array of Strings to hold customer names or an array of Doubles to hold customer sales, but what do you do if you want to coordinate that data? This article describes…
Get people started with the process of using Access VBA to control Excel using automation, Microsoft Access can control other applications. An example is the ability to programmatically talk to Excel. Using automation, an Access application can laun…
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…
Suggested Courses

719 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