Sexain-MemController/index_queue.h at master · basicthinker/Sexain-MemController · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
// index_queue.h
// Copyright (c) 2014 Jinglei Ren <jinglei@ren.systems>

#ifndef SEXAIN_INDEX_QUEUE_H_
#define SEXAIN_INDEX_QUEUE_H_

#include <cerrno>
#include <cassert>
#include <set>
#include <algorithm>

struct IndexNode {
  int prev;
  int next;
  IndexNode() {
    prev = next = -EINVAL;
  }
};

class IndexArray {
 public:
  virtual IndexNode& operator[](int i) = 0;
};

class QueueVisitor {
 public:
  virtual void Visit(int i) = 0;
};

class IndexQueue {
 public:
  IndexQueue(IndexArray& arr);
  int Front() const { return head_.prev; }
  int Back() const { return head_.next; }
  bool Empty() const;
  void Remove(int i);
  int PopFront();
  void PushBack(int i);

  int Accept(QueueVisitor* visitor);
  int length() const { return length_; }
 private:
  IndexNode& FrontNode();
  IndexNode& BackNode();
  void SetFront(int i) { head_.prev = i; }
  void SetBack(int i) { head_.next = i; }

  IndexNode head_;
  IndexArray& array_;
  int length_;
};

inline IndexQueue::IndexQueue(IndexArray& arr) : array_(arr) {
  SetFront(-EINVAL);
  SetBack(-EINVAL);
  length_ = 0;
}

inline IndexNode& IndexQueue::FrontNode() {
  assert(Front() >= 0);
  return array_[Front()];
}

inline IndexNode& IndexQueue::BackNode() {
  assert(Back() >= 0);
  return array_[Back()];
}

inline bool IndexQueue::Empty() const {
  assert((Front() == -EINVAL) == (Back() == -EINVAL));
  assert((length_ == 0) == (Front() == -EINVAL));
  return Front() == -EINVAL;
}

inline int IndexQueue::PopFront() {
  if (Empty()) return -EINVAL;
  const int front = Front();
  Remove(front);
  return front;
}

#endif // SEXAIN_INDEX_QUEUE_H_