[erlang-questions] queues (previously: documentation of data structures)

[Lev Walkin]

Andras Georgy Bekes wrote:
>> The first step would be implementing a new data type: `cell' with operations such as
>> - - cell:empty/0 (create an empty cell)
>> - - cell:make/1 (create a cell with a given contents)
>> - - cell:get/1 (non-destructively get the contents of a cell. Block (or throw an error or some
>> predefined value if it is empty)
>> - - cell:put/2 (destructively overwrite a cell with a given value)
>> Basically, cell can be represented as a process that responds to proper messages. There can be
>> wrapper procedures
>> - - cell:/isEmpty/1 returns true if a given cell is empty
>>
>> If you have cells, you can implement `queue item' as a triple composed from:
>> - - a cell containing a reference to the previous `queue item'
>> - - a cell containing a reference to the value of the current `queue item'
>> - - a cell containing a reference to the next `queue item'.
>>
>> If you have that, you can represent the whole queue as a couple composed from:
>> - - a cell containing a reference to the head
>> - - a cell containing a reference to the tail
> 
> Why having a process for each queue entry???
> Ok, you can change a specific element once you've put on the
> queue, but you probably don't want that.
> 
> Why not just use the message queue of Erlang?
> (see attached module --- very simple)
> 
> Pros:
> - one process for each queue
> - same efficiency as the message queues of the VM
>   (hope you're satisfied with that)
> - works when several processes use a common queue
> 
> Cons:
> - copies each queued element twice (just like your solution)
> - ???

The killing Con is that one process may keep a megabyte
in the queue making this queue performance excruciatingly
slow for all other processes due to repeating message
queue scans.

-- 
Lev Walkin
vlm@REDACTED