sharded-cache/linkedlist.cpp at main · log-y/sharded-cache · 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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
// linkedlist.cpp

#include "linkedlist.h"
#include <iostream>

using namespace std;

LinkedList::LinkedList()
{
  try
  {
    head = new Node(-1, 0);
    tail = new Node(-1, 0);
    head->next = tail;
    tail->prev = head;
    tail->next = nullptr;
    head->prev = nullptr;
  }
  catch (const std::bad_alloc &e)
  {
    std::cerr << "error allocating" << std::endl;
  }

  size = 0;
}

Node *LinkedList::get_front()
{
  if (size == 0)
  {
    return nullptr;
  }
  return head->next;
}

void LinkedList::add_between_nodes(Node *new_node, Node *left, Node *right)
{
  if (new_node == nullptr || left == nullptr || right == nullptr)
  {
    return;
  }

  left->next = new_node;
  new_node->prev = left;
  right->prev = new_node;
  new_node->next = right;
  size++;
}

// connects the 2 nodes around new_node to each other
void LinkedList::cut_node(Node *curr_node)
{
  if (curr_node == nullptr || curr_node->prev == nullptr || curr_node->next == nullptr)
  {
    return;
  }

  Node *prev_node = curr_node->prev;
  Node *next_node = curr_node->next;

  prev_node->next = next_node;
  next_node->prev = prev_node;

  curr_node->next = nullptr;
  curr_node->prev = nullptr;
}

void LinkedList::pop_front()
{
  if (size == 0)
  {
    return;
  }
  Node *first = head->next;
  cut_node(first);
  delete first;
  size--;
}

void LinkedList::push_back(Node *new_node)
{
  if (size == 0)
  {
    add_between_nodes(new_node, head, tail);
    return;
  }

  Node *last = tail->prev;

  add_between_nodes(new_node, last, tail);
}

void LinkedList::move_to_back(Node *new_node)
{
  if (size == 0 || size == 1){
    return;
  }
  cut_node(new_node);
  push_back(new_node);
}

void LinkedList::delete_node(Node *curr_node)
{
  cut_node(curr_node);
  delete curr_node;
}

LinkedList::~LinkedList()
{
  Node *curr_node = head;
  while (curr_node != nullptr)
  {
    Node *next = curr_node->next;
    delete curr_node;
    curr_node = next;
  }
}

void LinkedList::print()
{
  Node *curr_node = head;
  while (curr_node != nullptr)
  {
    Node *next = curr_node->next;
    std::cout << curr_node->key << " " << curr_node->val << std::endl;
    curr_node = next;
  }
}