queue.verona

// Copyright (c) Microsoft Corporation. All rights reserved.
// Licensed under the MIT License.

/**
 *  This file implements a simple queue.  The queue always 
 *  contains at least one node.  The last node in the queue
 *  does not contain a Value. This removes a branch from the
 *  fast path of Addition.
 * 
 *  The queue is stored in a single region, but the Values it
 *  contains are in sub-regions.
 **/

/**
 * Generic class for nodes in a queue.
 * Value is the type is holds.
 **/
class Node[Value]
{
    // A pointer to the value pointed to by the node, or None.
    // If it is not None, then the Value is in its own region.
    value: (iso & Value) | (None & imm);
    // A pointer to the next element of the queue, or None.
    // The next value is in the same region.
    next: (Node[Value] & mut) | (None & imm);

    // Called when node is deallocated by the runtime.
    // Used to demonstrate when collections occur.
    final(self: mut)
    {
      Builtin.print("Finalise node\n");
    }
}

class Queue[Value]
{
  // Used for tracing to illustrate which queue is doing something.
  id: U64 & imm;

  // Start of the queue
  hd: Node[Value] & mut;
  // End of the queue, if hd == tl, then the queue is empty.
  tl: Node[Value] & mut;

  // Used to fake global immutable singletons.
  none: None & imm;  // Fix when we have singletons

  // Statistics for the queue.
  // The implementation given here performs periodic tracing of
  // the region for this queue.  These statistic allow the programmer
  // to decide when it is worth tracing to reclaim.
  // Future implementations will use other memory management strategies,
  // and there statistics might not be needed.
  length: U64 & imm;
  freed: U64 & imm;

  // Creates an empty queue in a new region with id = i
  create(i: U64 & imm): Queue[Value] & iso
  {
    // Allocate the queue in a new region
    var q = new Queue;
    
    // Fake up singleton for None.
    q.none = None.create();
    
    // Set id and initialise statistics
    q.id = i;
    q.length = 0;
    q.freed = 0;

    // Allocate the stub not in the same region as q
    var n = new Node in q;
    // Initialise node.
    n.next = q.none;
    n.value = q.none;

    // Link stub node into queue.
    q.hd = n;
    q.tl = n;
    
    // Return queue
    q
  }

  add(self: mut, v: iso & Value)
  {
    // Create new stub node
    var n_tail = new Node in self;
    n_tail.next = self.none;
    n_tail.value = self.none;

    // Fill in previous stub, and update tail.
    var old_tl = self.tl;
    old_tl.value = v;
    old_tl.next = n_tail;
    self.tl = n_tail;

    // Update statistics
    self.length = self.length + 1;
  }

  remove(self: mut): (iso & Value) | (None & imm)
  {
    var h = self.hd;

    // Data structure level GC heuristic:
    var boundary = self.length + self.length + 4;
    var value = self.freed > boundary;
    
    // Decide if we should collect some old nodes.
    if (value)
    {
      Builtin.print1("Should reclaim some memory! Queue {}\n", self.id);
      
      // This needs to ensure other references are removed in the type system.
      Builtin.trace(self);
      
      self.freed = 0;
    };

    // In Verona, like in Pony, assignment returns the previous value in the l-value:
    //     x = (y = 5)
    // Can be seend as move the value from y into x, and store 5 into y.
    // Thus,
    //     match(h.value = self.none)
    // sets value, to none, and extracts the old value, and performs a match on it.
    match (h.value = self.none)
    {
      var a: None => a, // Empty case
      var v: Value =>
      {
        // Non-empty case
        match (h.next)
        {
          var a: None => self.none, // Should be unreachable, but not enforced by type system.
          var n: Node[Value] =>
          {
            // Update head, and the statistics.
            self.hd = n;
            self.length = self.length - 1;
            self.freed = self.freed + 1;
            // Return extracted Node.
            v
          }
        }
      }
    }
  }
}