Requirements

• operations
  • enqueue element: offer(Message)
  • dequeue element: poll()
  • get first element: peek()
  • remove specified elements: deleteSpecific(int)
• message format

  class Message {
    int what;
    int arg1;
    int arg2;
    Object obj;
  }

Motivation

• Since Java 7: java.util.concurrent.BlockingQueue
• with some implementations
• but nothing like deleteSpecific()
• → implement from scratch

Non functioncal requirements

• fast queue and dequeue operations
• independent queue and dequeue operations

How to store the data?

• Linked List?
  • enqueue operates on tail
  • dequeue operates on head
  • remove iterates over elements

Linked List — empty

Linked List — offer(1)

Linked List — offer(2)

Linked List — poll()

Concurrency

• seperate locks
  • enqueue locks tail
  • dequeue locks head
• remove requires locking both
• peek should require no locks

Blocking mechanics

• poll() on empty queue should block:

  while (count.get() == 0) {
      locks.awaitNotEmpty();
  }
  message = queueOperations.dequeue();

• a Condition should help here
  • "wait until notified by another thread"

Design of MessageQueue

• lock and queue operation can be separated and reused:
  • MessageQueue
    • MessageQueueLocks
    • MessageQueueOperations
• Immutables is used to avoid boilerplate data classes
  • Message immutable
  • Node mutable

some Benchmarks