Implementing a CircularQueue


#1

Hello everyone.

I implemented a CircularQueue in ChaiScript. Because ot the inner workings of ChaiScript I face a problem.

The problem is the following: I want to preallocate memory for 10 messages. These messages that arrive are from different types.

class CircularDeque {
    var elements
    var currPutIdx
    var currGetIdx

    def CircularDeque(size) {
        this.elements = Vector()
        for (var i = 0; i < size; ++i) {
            this.elements.push_back([Dynamic_Object(), 0])
        }
        this.currPutIdx = 0
        this.currGetIdx = 0
    }

    def push(elem) {
      this.elements[this.currPutIdx] := elem
      this.currPutIdx = (this.currPutIdx + 1) % this.elements.size()
   }

  def empty() {
      return this.currPutIdx == this.currGetIdx
  }

  def pop() {
      var elem := this.elements[this.currGetIdx]
      this.currGetIdx = (this.currGetIdx + 1) % this.elements.size()
      return elem
  }
}

var queue = CircularQueue(10)

queue.push(elem)
...
queue.pop()
...
//When this element is assigned internally to already used storage if the left hand side is
//not compatible with the right hand side, it will trigger an error because I cannot
//assign right hand side object to object from left hand side. What I want is to just assign
//directly to the storage, no matter what there was before
queue.push(someElem)

At that time I create a Vector internally and push 10 Dynamic_Objects. Until here everything is ok. The problem comes when the buffer is complete and a new message arrives. If the message from the right hand of the assignment does not match the one on the left side, then a crash will happen when trying to assign.

How can I have a CircularQueue that is made of heterogeneous elements?

I thought of reassigning Dynamic_Objects when the element is popped, but that would allocate memory I think, so it is not a good solution.


#2

The problem that you are hitting is that once the type of an object is set in ChaiScript the type is fixed. In this way it’s strongly typed.

There’s currently no way to reassign the type of an object. A std::vector will not reallocate memory if you pop a single element and push back an element. This is probably your best option.


#3

The problem is actually that I do not know which kind of object will occupy which position. This queue receives network messages, in any order, and I want to reuse the slots. So for example, 3 messages arrive, I pop 3 of them, later 2 more arrive. I cannot know the kind of message that arrives in advance, because it could very well be an error also or anything else.


#4

Hm, i sounds strange that messages are of different base types. I would expect a class Message with a member var “type” or something like that. However, just for the sake of it - if you had MessageA and MessageB types you could wrap them in some super class that holds pointers to both types as well a the info which type it currently contains. That would work with ChaiScript i guess. But i always feel solutions like that have the smell of weird design.


#5

Actually my original code does not use inheritance :slight_smile: