idheap/

lib.rs

//! A heap of integer identifiers.

pub mod err;

use std::alloc::{alloc, dealloc, Layout};

use err::Error;

struct IdBlock {
  next: *mut IdBlock,
  prev: *mut IdBlock,
  low: usize,
  high: usize
}

impl IdBlock {
  fn count(&self) -> usize {
    self.high - self.low + 1
  }
}

/// A heap of integer identifiers that can be allocated off the heap and then
/// returned.
pub struct IdHeap {
  /// Lower id bound (inclusive).
  low: usize,

  /// Upper id bound (inclusive).
  high: usize,

  /// Doubly linked list containing all free/unallocated id's.
  ///
  /// Each block contains a lower and upper bounds of available id's, and the
  /// blocks are ordered (lowest first).
  blocks: *mut IdBlock
}

unsafe impl Send for IdHeap {}

/// Create a block spanning ids from `low` to `high`.
fn mkblock(low: usize, high: usize) -> *mut IdBlock {
  let layout = Layout::new::<IdBlock>();
  let blk = unsafe { alloc(layout) };
  let blk = blk as *mut IdBlock;

  unsafe {
    (*blk).next = std::ptr::null_mut();
    (*blk).prev = std::ptr::null_mut();
    (*blk).low = low;
    (*blk).high = high;
  }

  blk
}

impl IdHeap {
  /// Create a new intger identifier heap with the id bound `low` .. `high`
  /// (inclusive-inclusive).
  ///
  /// The entire range will be unallocated on creation.
  pub fn new(low: usize, high: usize) -> Result<Self, Error> {
    if high < low {
      #[cfg(feature = "hardfail")]
      panic!("minimum id bound much be lower than the maximum id bound");

      #[cfg(not(feature = "hardfail"))]
      return Err(Error::invalid_param(
        "Lower id bound must be lower than the higher id bound"
      ));
    }

    let idblk = mkblock(low, high);
    Ok(Self {
      low,
      high,
      blocks: idblk
    })
  }

  /// Generate an IdHeap from a id blocks specification string.
  ///
  /// A spec string can be generated using [`IdHeap::make_strlist()`].
  ///
  /// - `0-99` means there's one block of ids from 0 to 99 available.
  /// - `0-9,11,20-29` means there are three blocks of ids available.
  pub fn from_strlist(
    spec: &str,
    low: usize,
    high: usize
  ) -> Result<Self, Error> {
    let mut head: *mut IdBlock = std::ptr::null_mut();
    let mut tail: *mut IdBlock = std::ptr::null_mut();

    if !spec.is_empty() {
      for blkspec in spec.split(',') {
        let range: Vec<&str> = blkspec.split('-').collect();

        let blk = if range.len() == 1 {
          let id = match range[0].parse::<usize>() {
            Ok(id) => id,
            Err(_e) => {
              release_chain(head);
              return Err(Error::bad_format("Not a number in block spec"));
            }
          };

          mkblock(id, id)
        } else if range.len() == 2 {
          let low = match range[0].parse::<usize>() {
            Ok(id) => id,
            Err(_e) => {
              release_chain(head);
              return Err(Error::bad_format("Not a number in block spec"));
            }
          };
          let high = match range[1].parse::<usize>() {
            Ok(id) => id,
            Err(_e) => {
              release_chain(head);
              return Err(Error::bad_format("Not a number in block spec"));
            }
          };

          mkblock(low, high)
        } else {
          release_chain(head);
          return Err(Error::bad_format("invalid block spec"));
        };

        //
        // Make sure bounds are valid
        //
        unsafe {
          if (*blk).low > (*blk).high {
            release_chain(head);
            release_node(blk);
            return Err(Error::bad_format("Low bound higher than high bound"));
          }

          if (*blk).low < low || (*blk).high > high {
            release_chain(head);
            release_node(blk);
            return Err(Error::bad_format("Out of bounds"));
          }
        }

        if head == std::ptr::null_mut() {
          head = blk;
          tail = blk;
        } else {
          unsafe {
            // Make sure this current block's lower bound is higher than the
            // previous tail's upper bound, and that there's a gap between the
            // two.
            if (*tail).high >= (*blk).low {
              return Err(Error::bad_format("Overlapping spans"));
            }
            let d = (*blk).low - (*tail).high;
            if d < 2 {
              return Err(Error::bad_format("Contiguous spans"));
            }

            (*tail).next = blk;
            (*blk).prev = tail;

            tail = blk;
          }
        }
      }
    }

    Ok(Self {
      low,
      high,
      blocks: head
    })
  }


  pub fn from_slice(
    slice: &[(usize, usize)],
    low: usize,
    high: usize
  ) -> Result<Self, Error> {
    let mut head: *mut IdBlock = std::ptr::null_mut();
    let mut tail: *mut IdBlock = std::ptr::null_mut();

    if !slice.is_empty() {
      for (l, h) in slice {
        let blk = if l == h {
          mkblock(*l, *l)
        } else if *l > *h {
          release_chain(head);
          return Err(Error::bad_format("Low bound higher than high bound"));
        } else {
          mkblock(*l, *h)
        };

        unsafe {
          if (*blk).low < low || (*blk).high > high {
            release_chain(head);
            release_node(blk);
            return Err(Error::bad_format("Out of bounds"));
          }
        }

        if head == std::ptr::null_mut() {
          head = blk;
          tail = blk;
        } else {
          unsafe {
            // Make sure this current block's lower bound is higher than the
            // previous tail's upper bound, and that there's a gap between the
            // two.
            if (*tail).high >= (*blk).low {
              return Err(Error::bad_format("Overlapping spans"));
            }
            let d = (*blk).low - (*tail).high;
            if d < 2 {
              return Err(Error::bad_format("Contiguous spans"));
            }

            (*tail).next = blk;
            (*blk).prev = tail;

            tail = blk;
          }
        }
      }
    }

    Ok(Self {
      low,
      high,
      blocks: head
    })
  }


  /// Return total number of id's in heap.
  pub fn capacity(&self) -> usize {
    self.high - self.low + 1
  }

  /// Number of ids currently in heap.
  pub fn count(&self) -> usize {
    let mut ret = 0;

    let mut idblk = self.blocks;
    unsafe {
      while idblk != std::ptr::null_mut() {
        ret += (*idblk).count();
        idblk = (*idblk).next;
      }
    }

    ret
  }

  /// Number of ids allocated.
  pub fn allocated(&self) -> usize {
    self.capacity() - self.count()
  }

  pub fn is_empty(&self) -> bool {
    self.blocks == std::ptr::null_mut()
  }


  /// Generate a string from current id heap state.  The ouput format is
  /// compatible with [`IdHeap::from_strlist()`].
  pub fn make_strlist(&self) -> String {
    let mut ret = Vec::new();

    let mut n = self.blocks;
    while n != std::ptr::null_mut() {
      unsafe {
        if (*n).low == (*n).high {
          ret.push(format!("{}", (*n).low));
        } else {
          ret.push(format!("{}-{}", (*n).low, (*n).high));
        }

        n = (*n).next;
      }
    }

    ret.join(",")
  }


  /// Allocate an identifier.
  ///
  /// The id will always be the lowest available.
  ///
  /// Once the application is done with the id, it must be returned to the heap
  /// by calling [`IdHeap::release()`].
  ///
  /// Returns `Some(id)` on success.  Returns `None` if the id heap is empty.
  pub fn alloc(&mut self) -> Option<usize> {
    if self.blocks == std::ptr::null_mut() {
      return None;
    }

    let idblk = self.blocks;

    let id = unsafe { (*idblk).low };

    unsafe {
      if (*idblk).low != (*idblk).high {
        // keep block, but remove the allocated id
        (*idblk).low += 1;
      } else {
        // block is empty -- remove it
        self.blocks = (*self.blocks).next;

        // deallocate the empty block
        let layout = Layout::new::<IdBlock>();
        dealloc(idblk as *mut u8, layout);
      }
    }

    Some(id)
  }


  /// Attempt to allocate a specific id.
  ///
  /// Generally speaking use of this function is discouraged (applications
  /// should use [`IdHeap::alloc()`] unless the heap's state is being restored
  /// to a known state.
  ///
  /// Returns:
  /// - `Ok(id)` on success.
  /// - `Err(Error::Empty)` if heap is empty.
  /// - `Err(Error::Unavailable)` if the id has already been allocated.
  pub fn alloc_id(&mut self, id: usize) -> Result<usize, Error> {
    //
    // Make sure the id is without the id heap's bounds.
    //
    if id < self.low || id > self.high {
      #[cfg(feature = "hardfail")]
      panic!("id out of bounds");

      #[cfg(not(feature = "hardfail"))]
      return Err(Error::OutOfBounds);
    }

    //
    // Search for block containing id
    //
    let mut idblk = self.blocks;
    unsafe {
      //
      // Try to find the position where the id belongs.
      //
      while idblk != std::ptr::null_mut() {
        // If the requested id is higher than the upper bound, then the id can
        // not exist in this block, but may be in later blocks in the chain.
        // Go to next block.  (May end up being null, terminating the loop).
        if id > (*idblk).high {
          idblk = (*idblk).next;
          continue;
        }

        // If the requested id lower than the block's lowest value, then the id
        // does not exist within this id heap.
        if id < (*idblk).low {
          return Err(Error::Unavailable);
        }

        //
        // If this point is reached the id exists within this block.  There are
        // few different situations:
        // - The id is the only id in the block
        // - The id is at one of the block's boundaries
        // - The id is inside the bounds of the block.  The block needs to be
        //   split.
        //

        if (*idblk).low == (*idblk).high {
          // Id exists within the block
          self.free_node(idblk);
          return Ok(id);
        }

        if (*idblk).low == id {
          (*idblk).low += 1;
          return Ok(id);
        }

        if (*idblk).high == id {
          (*idblk).high -= 1;
          return Ok(id);
        }

        //
        // If this point is reached the current block needs to be split
        //
        let newblock = mkblock((*idblk).low, id - 1);

        (*idblk).low = id + 1;

        self.insert_node(idblk, newblock);

        return Ok(id);
      }
    }

    Err(Error::Unavailable)
  }


  /// Return an id back to the heap.
  pub fn release(&mut self, id: usize) -> Result<(), Error> {
    //
    // Make sure the id is without the id heap's bounds.
    //
    if id < self.low || id > self.high {
      #[cfg(feature = "hardfail")]
      panic!("id out of bounds");

      #[cfg(not(feature = "hardfail"))]
      return Err(Error::OutOfBounds);
    }

    let mut idblk = self.blocks;
    let mut last = std::ptr::null_mut();
    unsafe {
      //
      // Try to find the position where the id belongs.
      //
      while idblk != std::ptr::null_mut() {
        if id + 1 == (*idblk).low {
          // Id belongs to the beginning of this block
          (*idblk).low -= 1;

          // Check if this block should be merged with the previous one
          if (*idblk).prev != std::ptr::null_mut() {
            // Have a previous node
            if (*(*idblk).prev).high + 1 == (*idblk).low {
              // Yes, nodes should be merged.
              // Delete the current node, so merge backwards.
              (*(*idblk).prev).high = (*idblk).high;

              // Unlink and release node
              self.free_node(idblk);
            }
          }

          return Ok(());
        }

        if id == (*idblk).high + 1 {
          // Id belongs to the end of this block
          (*idblk).high += 1;

          // Check if this block should be merged with the next one

          if (*idblk).next != std::ptr::null_mut() {
            // Have a next node
            if (*(*idblk).next).low == (*idblk).high + 1 {
              // Yes, nodes should be merged.
              // Delete the current node, so merge forwards.
              (*(*idblk).next).low = (*idblk).low;

              // Unlink and release node
              self.free_node(idblk);
            }
          }

          return Ok(());
        }

        if id < (*idblk).low {
          // Found an insertion point for a new block.
          break;
        }

        //
        // If id is this block then application attempted to return an
        // unallocated id to the heap.
        //
        if id >= (*idblk).low && id <= (*idblk).high {
          #[cfg(feature = "hardfail")]
          panic!("Attempted to release an unallocated id");

          #[cfg(not(feature = "hardfail"))]
          return Err(Error::invalid_param(""));
        }

        // remember the last node
        last = idblk;

        // Follow the forward link.  May end up at null.
        idblk = (*idblk).next;
      }

      //
      // If this point is reached it means id was not returned to a block.
      // This can happen for three different reasons:
      // - Reached an insertion point (idblk will be non-null)
      // - Reached the end (idblk will be null and last will be non-null)
      // - There are no blocks in the id heap (last till be null)
      //

      //
      // Regardless of which situation this is, create a new block for the id.
      //
      let mut newblock = mkblock(id, id);
      if self.blocks == std::ptr::null_mut() {
        // id heap was empty -- make new block the entire chain
        self.blocks = newblock;
      } else if idblk != std::ptr::null_mut() {
        self.insert_node(idblk, newblock);
      } else if last != std::ptr::null_mut() {
        // Append new node to the end of the block list.
        //  'last' will be set to the last node.  Link 'newnode' after 'last'.
        (*last).next = newblock;
        (*newblock).prev = last;
      }
    }

    Ok(())
  }
}


/// Internals
impl IdHeap {
  /// Insert an id block specified by `newblock`, at the point of `idblk`.
  unsafe fn insert_node(
    &mut self,
    idblk: *mut IdBlock,
    newblock: *mut IdBlock
  ) {
    // idblk is the insertion point
    // It may be the first block, which would mean that the new block would
    // become the new head.

    (*newblock).next = idblk;
    (*newblock).prev = (*idblk).prev;

    // Relink next node's previous link to the new node.
    // There's always a next block since this is an insertion
    (*(*newblock).next).prev = newblock;

    // If there's a previous node, then make it link forward to the new
    // node
    if (*newblock).prev != std::ptr::null_mut() {
      (*(*newblock).prev).next = newblock;
    } else {
      // The node being inserted will be the new head
      self.blocks = newblock;
    }
  }


  /// Release a id block node, updating chain pointer as needed.
  /// It is the responsibility of the caller to ensure that `idblk` points to a
  /// valid block.
  unsafe fn free_node(&mut self, idblk: *mut IdBlock) {
    if idblk == self.blocks {
      // Make next node the new head.  (This can be null)
      self.blocks = (*idblk).next;
    }

    //
    // unlink node
    //
    if (*idblk).prev != std::ptr::null_mut() {
      // Have a previous node -- make its next link point to our next (may be
      // null).
      //
      //                                    +-------+
      // +---+   +---+   +---+      +---+   | +---+ |   +---+
      // |   |-->|###|-->|   |  =>  |   |---+ |###|-+-->|   |
      // |   |<--|###|<--|   |      |   |<----|###|<----|   |
      // +---+   +---+   +---+      +---+     +---+     +---+
      (*(*idblk).prev).next = (*idblk).next;
    } else if (*idblk).next != std::ptr::null_mut() {
      // No previous node, but have a next one -- so make it not have a
      // previous link.
      //
      //
      // +---+   +---+      +---+    +---+
      // |###|-->|   |  =>  |###|--->|   |
      // |###|<--|   |      |###|    |   |
      // +---+   +---+      +---+    +---+
      (*(*idblk).next).prev = std::ptr::null_mut();
    }

    if (*idblk).next != std::ptr::null_mut() {
      // Have a next node -- make its previous link point to our previous
      // (may be null)
      //
      //           +-------+                      +-------+
      //   +---+   | +---+ |   +---+      +---+   | +---+ |   +---+
      //   |   |---+ |###|-+-->|   |  =>  |   |---+ |###|-+-->|   |
      //   |   |<----|###|<----|   |      |   |<--+-|###| +---|   |
      //   +---+     +---+     +---+      +---+   | +---+ |   +---+
      //                                          +-------+
      (*(*idblk).next).prev = (*idblk).prev;
    } else if (*idblk).prev != std::ptr::null_mut() {
      // No next node, but have a previous one -- so make it not have a
      // next link.
      (*(*idblk).prev).next = std::ptr::null_mut();
    }

    let layout = Layout::new::<IdBlock>();
    dealloc(idblk as *mut u8, layout);
  }


  /// Get a list of all the available id blocks.
  #[allow(dead_code)]
  fn get_blocks_list(&self) -> Vec<(usize, usize)> {
    let mut ret = Vec::new();
    let mut idblk = self.blocks;
    unsafe {
      while idblk != std::ptr::null_mut() {
        ret.push(((*idblk).low, (*idblk).high));
        idblk = (*idblk).next;
      }
    }
    ret
  }
}

impl Drop for IdHeap {
  fn drop(&mut self) {
    let layout = Layout::new::<IdBlock>();
    let mut idblk = self.blocks;
    while idblk != std::ptr::null_mut() {
      unsafe {
        let next = (*idblk).next;
        dealloc(idblk as *mut u8, layout);
        idblk = next;
      }
    }
  }
}


fn release_chain(head: *mut IdBlock) {
  let mut n = head;

  while n != std::ptr::null_mut() {
    let next = unsafe { (*n).next };

    release_node(n);

    n = next;
  }
}

fn release_node(n: *mut IdBlock) {
  let layout = Layout::new::<IdBlock>();
  unsafe {
    dealloc(n as *mut u8, layout);
  }
}


#[cfg(test)]
mod tests {
  use super::*;

  #[test]
  fn single_id() {
    let mut idh = IdHeap::new(1, 1).unwrap();
    assert_eq!(idh.capacity(), 1);
    assert_eq!(idh.count(), 1);
    assert_eq!(idh.allocated(), 0);
    let fb = idh.get_blocks_list();
    assert_eq!(fb.as_slice(), [(1, 1)]);
    assert_eq!(fb.is_empty(), false);

    assert_eq!(idh.alloc(), Some(1));

    assert_eq!(idh.capacity(), 1);
    assert_eq!(idh.count(), 0);
    assert_eq!(idh.allocated(), 1);
    let fb = idh.get_blocks_list();
    assert_eq!(fb.as_slice(), []);
    assert_eq!(fb.is_empty(), true);

    idh.release(1).unwrap();

    assert_eq!(idh.capacity(), 1);
    assert_eq!(idh.count(), 1);
    assert_eq!(idh.allocated(), 0);
    let fb = idh.get_blocks_list();
    assert_eq!(fb.as_slice(), [(1, 1)]);
    assert_eq!(fb.is_empty(), false);
  }


  #[test]
  fn just_init() {
    let mut idh = IdHeap::new(0, 9).unwrap();
    assert_eq!(idh.capacity(), 10);
    assert_eq!(idh.count(), 10);
    assert_eq!(idh.allocated(), 0);
    let fb = idh.get_blocks_list();
    assert_eq!(fb.as_slice(), [(0, 9)]);

    assert_eq!(idh.alloc(), Some(0));
  }


  #[test]
  fn alloc_one() {
    let mut idh = IdHeap::new(0, 9).unwrap();

    assert_eq!(idh.alloc(), Some(0));

    assert_eq!(idh.capacity(), 10);
    assert_eq!(idh.count(), 9);
    assert_eq!(idh.allocated(), 1);
    let fb = idh.get_blocks_list();
    assert_eq!(fb.as_slice(), [(1, 9)]);
  }


  #[test]
  fn return_new_first_block() {
    let mut idh = IdHeap::new(0, 9).unwrap();

    // Remove first and second ids
    assert_eq!(idh.alloc(), Some(0));
    assert_eq!(idh.alloc(), Some(1));

    // Return the first id, which should force the creation of a new first
    // block.
    idh.release(0).unwrap();

    assert_eq!(idh.capacity(), 10);
    assert_eq!(idh.count(), 9);
    assert_eq!(idh.allocated(), 1);
    let fb = idh.get_blocks_list();
    assert_eq!(fb.as_slice(), [(0, 0), (2, 9)]);
  }


  #[test]
  fn merge_front_and_back_add_tail() {
    let mut idh = IdHeap::new(0, 2).unwrap();

    assert_eq!(idh.alloc(), Some(0));
    assert_eq!(idh.alloc(), Some(1));
    assert_eq!(idh.alloc(), Some(2));

    let fb = idh.get_blocks_list();
    assert_eq!(fb.as_slice(), []);

    idh.release(0).unwrap();

    let fb = idh.get_blocks_list();
    assert_eq!(fb.as_slice(), [(0, 0)]);

    // Add new tail
    idh.release(2).unwrap();

    let fb = idh.get_blocks_list();
    assert_eq!(fb.as_slice(), [(0, 0), (2, 2)]);

    idh.release(1).unwrap();

    let fb = idh.get_blocks_list();
    assert_eq!(fb.as_slice(), [(0, 2)]);
  }


  #[test]
  fn merge_front_and_back_add_head() {
    let mut idh = IdHeap::new(0, 2).unwrap();

    assert_eq!(idh.alloc(), Some(0));
    assert_eq!(idh.alloc(), Some(1));
    assert_eq!(idh.alloc(), Some(2));

    let fb = idh.get_blocks_list();
    assert_eq!(fb.as_slice(), []);

    idh.release(2).unwrap();

    let fb = idh.get_blocks_list();
    assert_eq!(fb.as_slice(), [(2, 2)]);

    // Add new head
    idh.release(0).unwrap();

    let fb = idh.get_blocks_list();
    assert_eq!(fb.as_slice(), [(0, 0), (2, 2)]);

    idh.release(1).unwrap();

    let fb = idh.get_blocks_list();
    assert_eq!(fb.as_slice(), [(0, 2)]);
  }


  #[test]
  fn alloc_id_head() {
    let mut idh = IdHeap::new(1, 3).unwrap();

    assert_eq!(idh.alloc_id(1).unwrap(), 1);

    let fb = idh.get_blocks_list();
    assert_eq!(fb.as_slice(), [(2, 3)]);

    // Return the id
    idh.release(1).unwrap();

    // Make sure the blocks merged correctly
    let fb = idh.get_blocks_list();
    assert_eq!(fb.as_slice(), [(1, 3)]);
  }


  #[test]
  fn alloc_id_split() {
    // Allocate an id heap with three elements in it
    let mut idh = IdHeap::new(1, 3).unwrap();

    // Request the meddle id, to force the id block to split in two
    assert_eq!(idh.alloc_id(2).unwrap(), 2);

    // Make sure the split ocurred
    let fb = idh.get_blocks_list();
    assert_eq!(fb.as_slice(), [(1, 1), (3, 3)]);

    // Return the id
    idh.release(2).unwrap();

    // Make sure the blocks merged correctly
    let fb = idh.get_blocks_list();
    assert_eq!(fb.as_slice(), [(1, 3)]);
  }


  #[test]
  fn alloc_id_tail() {
    let mut idh = IdHeap::new(1, 3).unwrap();

    assert_eq!(idh.alloc_id(3).unwrap(), 3);

    let fb = idh.get_blocks_list();
    assert_eq!(fb.as_slice(), [(1, 2)]);

    // Return the id
    idh.release(3).unwrap();

    // Make sure the blocks merged correctly
    let fb = idh.get_blocks_list();
    assert_eq!(fb.as_slice(), [(1, 3)]);
  }


  #[test]
  fn from_strlist() {
    let idh = IdHeap::from_strlist("", 0, 7).unwrap();
    let fb = idh.get_blocks_list();
    assert_eq!(fb.as_slice(), []);

    let idh = IdHeap::from_strlist("0", 0, 7).unwrap();
    let fb = idh.get_blocks_list();
    assert_eq!(fb.as_slice(), [(0, 0)]);

    let idh = IdHeap::from_strlist("0-2", 0, 7).unwrap();
    let fb = idh.get_blocks_list();
    assert_eq!(fb.as_slice(), [(0, 2)]);

    let idh = IdHeap::from_strlist("0-2,6", 0, 7).unwrap();
    let fb = idh.get_blocks_list();
    assert_eq!(fb.as_slice(), [(0, 2), (6, 6)]);

    let idh = IdHeap::from_strlist("0-1,3,5-7", 0, 7).unwrap();
    let fb = idh.get_blocks_list();
    assert_eq!(fb.as_slice(), [(0, 1), (3, 3), (5, 7)]);
  }


  #[test]
  fn from_slice() {
    let idh = IdHeap::from_slice(&[], 0, 7).unwrap();
    let fb = idh.get_blocks_list();
    assert_eq!(fb.as_slice(), []);

    let idh = IdHeap::from_slice(&[(0, 0)], 0, 7).unwrap();
    let fb = idh.get_blocks_list();
    assert_eq!(fb.as_slice(), [(0, 0)]);

    let idh = IdHeap::from_slice(&[(0, 2)], 0, 7).unwrap();
    let fb = idh.get_blocks_list();
    assert_eq!(fb.as_slice(), [(0, 2)]);

    let idh = IdHeap::from_slice(&[(0, 2), (6, 6)], 0, 7).unwrap();
    let fb = idh.get_blocks_list();
    assert_eq!(fb.as_slice(), [(0, 2), (6, 6)]);

    let idh = IdHeap::from_slice(&[(0, 1), (3, 3), (5, 7)], 0, 7).unwrap();
    let fb = idh.get_blocks_list();
    assert_eq!(fb.as_slice(), [(0, 1), (3, 3), (5, 7)]);
  }


  #[test]
  fn from_strlist_fail() {
    match IdHeap::from_strlist("1-0", 0, 7) {
      Err(Error::BadFormat(s)) => {
        assert_eq!(&s, "Low bound higher than high bound");
      }
      _ => panic!("test failed")
    }

    match IdHeap::from_strlist("a", 0, 7) {
      Err(Error::BadFormat(s)) => {
        assert_eq!(&s, "Not a number in block spec");
      }
      _ => panic!("test failed")
    }

    match IdHeap::from_strlist("a-4", 0, 7) {
      Err(Error::BadFormat(s)) => {
        assert_eq!(&s, "Not a number in block spec");
      }
      _ => panic!("test failed")
    }

    match IdHeap::from_strlist("0-a", 0, 7) {
      Err(Error::BadFormat(s)) => {
        assert_eq!(&s, "Not a number in block spec");
      }
      _ => panic!("test failed")
    }

    match IdHeap::from_strlist("0-2", 1, 7) {
      Err(Error::BadFormat(s)) => {
        assert_eq!(&s, "Out of bounds");
      }
      _ => panic!("test failed")
    }

    match IdHeap::from_strlist("4-8", 1, 7) {
      Err(Error::BadFormat(s)) => {
        assert_eq!(&s, "Out of bounds");
      }
      _ => panic!("test failed")
    }

    //  |--------|
    //        |-------|
    match IdHeap::from_strlist("0-5,4-7", 0, 7) {
      Err(Error::BadFormat(s)) => {
        assert_eq!(&s, "Overlapping spans");
      }
      _ => panic!("test failed")
    }

    //  |--------|
    //           |-------|
    match IdHeap::from_strlist("0-4,4-7", 0, 7) {
      Err(Error::BadFormat(s)) => {
        assert_eq!(&s, "Overlapping spans");
      }
      _ => panic!("test failed")
    }

    // A gap is needed, so this is not allowed:
    //  |--------||-------|
    match IdHeap::from_strlist("0-4,5-7", 0, 7) {
      Err(Error::BadFormat(s)) => {
        assert_eq!(&s, "Contiguous spans");
      }
      _ => panic!("test failed")
    }
  }


  #[test]
  fn from_slice_fail() {
    match IdHeap::from_slice(&[(1, 0)], 0, 7) {
      Err(Error::BadFormat(s)) => {
        assert_eq!(&s, "Low bound higher than high bound");
      }
      _ => panic!("test failed")
    }

    match IdHeap::from_slice(&[(0, 2)], 1, 7) {
      Err(Error::BadFormat(s)) => {
        assert_eq!(&s, "Out of bounds");
      }
      _ => panic!("test failed")
    }

    match IdHeap::from_slice(&[(4, 8)], 1, 7) {
      Err(Error::BadFormat(s)) => {
        assert_eq!(&s, "Out of bounds");
      }
      _ => panic!("test failed")
    }

    //  |--------|
    //        |-------|
    match IdHeap::from_slice(&[(0, 5), (4, 7)], 0, 7) {
      Err(Error::BadFormat(s)) => {
        assert_eq!(&s, "Overlapping spans");
      }
      _ => panic!("test failed")
    }

    //  |--------|
    //           |-------|
    match IdHeap::from_slice(&[(0, 4), (4, 7)], 0, 7) {
      Err(Error::BadFormat(s)) => {
        assert_eq!(&s, "Overlapping spans");
      }
      _ => panic!("test failed")
    }

    // A gap is needed, so this is not allowed:
    //  |--------||-------|
    match IdHeap::from_slice(&[(0, 4), (5, 7)], 0, 7) {
      Err(Error::BadFormat(s)) => {
        assert_eq!(&s, "Contiguous spans");
      }
      _ => panic!("test failed")
    }
  }


  #[test]
  fn deserialize_serialize() {
    let input = "";
    let idh = IdHeap::from_strlist(input, 0, 7).unwrap();
    assert_eq!(input, idh.make_strlist());

    let input = "0";
    let idh = IdHeap::from_strlist(input, 0, 7).unwrap();
    assert_eq!(input, idh.make_strlist());

    let input = "0-2";
    let idh = IdHeap::from_strlist(input, 0, 7).unwrap();
    assert_eq!(input, idh.make_strlist());

    let input = "0-2,4";
    let idh = IdHeap::from_strlist(input, 0, 7).unwrap();
    assert_eq!(input, idh.make_strlist());

    let input = "0-2,4-6";
    let idh = IdHeap::from_strlist(input, 0, 7).unwrap();
    assert_eq!(input, idh.make_strlist());

    let input = "0-1,3,5-7";
    let idh = IdHeap::from_strlist(input, 0, 7).unwrap();
    assert_eq!(input, idh.make_strlist());

    let input = "0,2,4,6";
    let idh = IdHeap::from_strlist(input, 0, 7).unwrap();
    assert_eq!(input, idh.make_strlist());
  }


  #[test]
  fn send_to_thread() {
    let mut idh = IdHeap::new(0, 7).unwrap();

    let handle = std::thread::spawn(|| {
      let id = idh.alloc().unwrap();
      (idh, id)
    });

    let (mut idh, id) = handle.join().unwrap();
    idh.release(id).unwrap();
  }
}

// vim: set ft=rust et sw=2 ts=2 sts=2 cinoptions=2 tw=79 :