1 /* Copyright (c) 2019 The Linux Foundation. All rights reserved.
2 *
3 * Redistribution and use in source and binary forms, with or without
4 * modification, are permitted provided that the following conditions are
5 * met:
6 * * Redistributions of source code must retain the above copyright
7 * notice, this list of conditions and the following disclaimer.
8 * * Redistributions in binary form must reproduce the above
9 * copyright notice, this list of conditions and the following
10 * disclaimer in the documentation and/or other materials provided
11 * with the distribution.
12 * * Neither the name of The Linux Foundation, nor the names of its
13 * contributors may be used to endorse or promote products derived
14 * from this software without specific prior written permission.
15 *
16 * THIS SOFTWARE IS PROVIDED "AS IS" AND ANY EXPRESS OR IMPLIED
17 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
18 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT
19 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS
20 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
21 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
22 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
23 * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
24 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
25 * OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN
26 * IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 *
28 */
29
30 #ifndef LOC_SKIP_LIST_H
31 #define LOC_SKIP_LIST_H
32
33 #include <stdlib.h>
34 #include <list>
35 #include <vector>
36 #include <iostream>
37 #include <algorithm>
38
39 using namespace std;
40
41 namespace loc_util {
42
43 template <typename T,
44 template<typename elem, typename Allocator = std::allocator<elem>> class container = list>
45 class SkipNode {
46 public:
47 typedef typename container<SkipNode<T, container>>::iterator NodeIterator;
48
49 int mLevel;
50 T mData;
51 NodeIterator mNextInLevel;
52
SkipNode(int level,T & data)53 SkipNode(int level, T& data): mLevel(level), mData(data) {}
54 };
55
56 template <typename T>
57 class SkipList {
58 using NodeIterator = typename SkipNode<T>::NodeIterator;
59 private:
60 list<SkipNode<T>> mMainList;
61 vector<NodeIterator> mHeadVec;
62 vector<NodeIterator> mTailVec;
63 public:
64 SkipList(int totalLevels);
65 void append(T& data, int level);
66 void pop(int level);
67 void pop();
68 T front(int level);
69 int size();
70 void flush();
71 list<pair<T, int>> dump();
72 list<pair<T, int>> dump(int level);
73 };
74
75 template <typename T>
SkipList(int totalLevels)76 SkipList<T>::SkipList(int totalLevels): mHeadVec(totalLevels, mMainList.end()),
77 mTailVec(totalLevels, mMainList.end()) {}
78
79 template <typename T>
append(T & data,int level)80 void SkipList<T>::append(T& data, int level) {
81 if ( level < 0 || level >= mHeadVec.size()) {
82 return;
83 }
84
85 SkipNode<T> node(level, data);
86 node.mNextInLevel = mMainList.end();
87 mMainList.push_back(node);
88 auto iter = --mMainList.end();
89 if (mHeadVec[level] == mMainList.end()) {
90 mHeadVec[level] = iter;
91 } else {
92 (*mTailVec[level]).mNextInLevel = iter;
93 }
94 mTailVec[level] = iter;
95 }
96
97 template <typename T>
pop(int level)98 void SkipList<T>::pop(int level) {
99 if (mHeadVec[level] == mMainList.end()) {
100 return;
101 }
102
103 if ((*mHeadVec[level]).mNextInLevel == mMainList.end()) {
104 mTailVec[level] = mMainList.end();
105 }
106
107 auto tmp_iter = (*mHeadVec[level]).mNextInLevel;
108 mMainList.erase(mHeadVec[level]);
109 mHeadVec[level] = tmp_iter;
110 }
111
112 template <typename T>
pop()113 void SkipList<T>::pop() {
114 pop(mMainList.front().mLevel);
115 }
116
117 template <typename T>
front(int level)118 T SkipList<T>::front(int level) {
119 return (*mHeadVec[level]).mData;
120 }
121
122 template <typename T>
size()123 int SkipList<T>::size() {
124 return mMainList.size();
125 }
126
127 template <typename T>
flush()128 void SkipList<T>::flush() {
129 mMainList.clear();
130 for (int i = 0; i < mHeadVec.size(); i++) {
131 mHeadVec[i] = mMainList.end();
132 mTailVec[i] = mMainList.end();
133 }
134 }
135
136 template <typename T>
dump()137 list<pair<T, int>> SkipList<T>::dump() {
138 list<pair<T, int>> li;
139 for_each(mMainList.begin(), mMainList.end(), [&](SkipNode<T> &item) {
140 li.push_back(make_pair(item.mData, item.mLevel));
141 });
142 return li;
143 }
144
145 template <typename T>
dump(int level)146 list<pair<T, int>> SkipList<T>::dump(int level) {
147 list<pair<T, int>> li;
148 auto head = mHeadVec[level];
149 while (head != mMainList.end()) {
150 li.push_back(make_pair((*head).mData, (*head).mLevel));
151 head = (*head).mNextInLevel;
152 }
153 return li;
154 }
155
156 }
157
158 #endif
159