1 #include <iostream>
  2 #include <stdlib.h>
  3 #include <time.h>
  4 
  5 using namespace std;
  6 
  7 #define MAX_LEVEL 30
  8 
  9 typedef struct node {
 10     node * right;
 11     node * down;
 12     int key;
 13 } data_node;
 14 
 15 struct skip_list {
 16     data_node ** header;
 17     int max_level;
 18     int size;
 19 };
 20 
 21 node * height[MAX_LEVEL];
 22 
 23 int get_current_level()
 24 {
 25     int k = 0;
 26     while (rand() % 2) ++k;
 27     return k;
 28 }
 29 
 30 skip_list * skip_list_init()
 31 {
 32     srand((unsigned)time(NULL));
 33     skip_list * sl;
 34     sl = new skip_list();
 35     sl->max_level = 0;
 36     sl->header = new data_node*[MAX_LEVEL];
 37     for (int i = 0; i < MAX_LEVEL; ++i) {
 38         data_node * t = new data_node();
 39         t->key = -10;
 40         t->right = NULL;
 41         sl->header[i] = t;
 42     }
 43     for (int i = MAX_LEVEL - 1; i; --i) {
 44         sl->header[i]->down = sl->header[i - 1];
 45     }
 46     return sl;
 47 }
 48 
 49 data_node * find_x_from_skip_list(skip_list * sl, int x)
 50 {
 51     data_node *h = sl->header[sl->max_level];
 52     while (h) {
 53         if (h->key == x && h->down == NULL) {
 54             return h;
 55         }
 56         else {
 57             if (x >= h->key && (h->right == NULL || h->right->key > x)) {
 58                 h = h->down;
 59 #ifdef DEBUG
 60                 cout << "d-";
 61 #endif
 62             }
 63             else {
 64                 if (x < h->key) {
 65 #ifdef DEBUG
 66                     cout << "return imediately" << endl;
 67 #endif
 68                     return NULL;
 69                 }
 70                 else {
 71                     h = h->right;
 72 #ifdef DEBUG
 73                     cout << "r-";
 74 #endif
 75                 }
 76             }
 77         }
 78     }
 79 #ifdef DEBUG
 80     cout << endl;
 81 #endif
 82     return h;
 83 }
 84 
 85 data_node * insert_x_into_list(node * head, int x)
 86 {
 87 
 88     node * prev = NULL;
 89     while (head && x > head->key) {
 90         prev = head;
 91         head = head->right;
 92     }
 93     node * n = new node;
 94     n->key = x;
 95     n->right = NULL;
 96     n->down = NULL;
 97     if (prev == NULL) {
 98         if (head) {
 99             n->right = head->right;
100         }
101         else {
102             head = n;
103         }
104     }
105     else {
106         prev->right = n;
107         n->right = head;
108     }
109     return n;
110 }
111 
112 int insert_x_into_skip_list(skip_list * sl, int x)
113 {
114     int current_level = get_current_level();
115     if (current_level > sl->max_level) {
116         sl->max_level = current_level;
117     }
118 #ifdef DEBUG
119     cout << "current_level " << current_level << " insert " << x << endl;
120 #endif
121     for (int i = current_level; i >= 0; --i) {
122         // insert x into single link list
123         height[i] = insert_x_into_list(sl->header[i], x);
124     }
125     for (int i = current_level; i; --i) {
126         height[i]->down = height[i - 1];
127 #ifdef DEBUG
128         cout << "connect down " << height[i]->key << " " << endl;
129 #endif
130     }
131     ++sl->size;
132     return 0;
133 }
134 
135 
136 int remove_data_from_list(node *head, int x)
137 {
138     node * prev = NULL;
139     node * cur = head;
140     while (cur) {
141         if (cur->key == x) {
142             if (prev) {
143                 prev->right = cur->right;
144                 delete cur;
145                 cur = prev->right;
146             }
147             else {
148                 prev = cur;
149                 delete cur;
150                 cur = prev->right;
151                 prev = NULL;
152             }
153         }
154         else {
155             prev = cur;
156             cur = cur->right;
157         }
158     }
159     return 0;
160 }
161 
162 int remove_x_from_skip_list(skip_list * sl, int x)
163 {
164     for (int i = 0; i <= sl->max_level; ++i) {
165         remove_data_from_list(sl->header[i], x);
166     }
167     return 0;
168 }
169 
170 int print_list(skip_list *sl)
171 {
172     for (int i = sl->max_level; i >= 0; i--) {
173         data_node * current = sl->header[i];
174         while (current) {
175             cout << current->key << "  ";
176             current = current->right;
177         }
178         cout << endl;
179     }
180     return 0;
181 }
182 
183 int main()
184 {
185     int test_n = 1000;
186     skip_list * sl = skip_list_init();
187     for (int i = 0; i < test_n; i++) {
188         insert_x_into_skip_list(sl, i);
189     }
190     print_list(sl);
191     //    for(int i = -1; i< 20; i++) {
192     //        node * p = find_x_from_skip_list(sl, i);
193     //        if (p == NULL) {
194     //            cout<<"not found "<<i<<endl;
195     //        } else {
196     //            cout<<"find key "<<i<<endl;
197     //        }
198     //    }
199     //    for(int i = 0; i< test_n; ++i) {
200     //        cout<<"going to remove " <<i<<endl;
201     //        remove_x_from_skip_list(sl, i);
202     //        print_list(sl);
203     //        cout<<"after remove "<<i<<endl;
204     //    }
205     return 0;
206 }