1 /*
2 * Copyright (C) 2022 Huawei Device Co., Ltd.
3 * Licensed under the Apache License, Version 2.0 (the "License");
4 * you may not use this file except in compliance with the License.
5 * You may obtain a copy of the License at
6 *
7 * http://www.apache.org/licenses/LICENSE-2.0
8 *
9 * Unless required by applicable law or agreed to in writing, software
10 * distributed under the License is distributed on an "AS IS" BASIS,
11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 * See the License for the specific language governing permissions and
13 * limitations under the License.
14 */
15
16 #ifndef SKIPLIST_H
17 #define SKIPLIST_H
18 #include "queue.h"
19
20 #ifdef __cplusplus
21 extern "C" {
22 #endif
23
24 #define MAX_SKIPLIST_LEVEL 16
25
26 typedef FILLP_INT (*funcSkiplistCompair)(void *v1, void *v2);
27
28 struct SkipListNode {
29 void *item; /* value */
30 struct SkipListNode *forward[MAX_SKIPLIST_LEVEL]; /* level next */
31 struct SkipListNode *pre[MAX_SKIPLIST_LEVEL];
32 FILLP_INT level;
33 #ifdef FILLP_64BIT_ALIGN
34 FILLP_UINT8 padd[4];
35 #endif
36 };
37
38 struct SkipList {
39 struct SkipListNode *head;
40 struct SkipListNode *tail;
41
42 struct SkipListNode *hnode[MAX_SKIPLIST_LEVEL]; /* point to the first node of each level */
43 struct SkipListNode *tnode[MAX_SKIPLIST_LEVEL]; /* point to the last node of each level */
44 FILLP_INT level; /* the current max level of list */
45 FILLP_UINT32 nodeNum;
46 funcSkiplistCompair funcCmp;
47 FILLP_UINT8 randomLev[MAX_RANDOM_LEV];
48 FILLP_UINT32 randomIndex;
49 };
50
51 /*******************************************************************************
52 Function : SkipListGetPop
53
54 Description : This function will be invoked to pop the head node from
55 SkipList.
56
57 Input : list - SkipList pointer
58
59 Output : None
60
61 Return : None
62 *******************************************************************************/
SkipListGetPop(struct SkipList * list)63 static __inline struct SkipListNode *SkipListGetPop(struct SkipList *list)
64 {
65 return ((list == FILLP_NULL_PTR) || (list->head == FILLP_NULL_PTR)) ? FILLP_NULL_PTR : list->head;
66 }
67
68 /*******************************************************************************
69 Function : SkipListGetTail
70
71 Description : This function will be invoked to pop the head node from
72 SkipList.
73
74 Input : list - SkipList pointer
75
76 Output : None
77
78 Return : None
79 *******************************************************************************/
SkipListGetTail(struct SkipList * list)80 static __inline struct SkipListNode *SkipListGetTail(struct SkipList *list)
81 {
82 return ((list == FILLP_NULL_PTR) || (list->tail == FILLP_NULL_PTR)) ? FILLP_NULL_PTR : list->tail;
83 }
84
85 /*******************************************************************************
86 Function : SkiplistInit
87
88 Description : This function will be invoked to init the SkipList.
89
90 Input : list - SkipList to be initialised
91 cmp - SkipList compare function
92
93 Output : None
94
95 Return : If success, returns ERR_OK. Otherwise, returns Error code.
96 *******************************************************************************/
97 FILLP_INT SkiplistInit(struct SkipList *list, funcSkiplistCompair cmp);
98
99 /*******************************************************************************
100 Function : SkipListInsert
101
102 Description : This function will be invoked to insert a node to SkipList.
103
104 Input : list - SkipList pointer
105 item - value of the SkipList node
106 node - SkipList node to be inserted to SkipList
107 err_if_conflict - Flag to decide whether to give error if any
108 conflicts between item of node to be inserted and existing
109 node
110
111 Output : None
112
113 Return : ERR_OK, if success. Error codes on failures.
114 *******************************************************************************/
115 FILLP_INT SkipListInsert(struct SkipList *list, void *item, struct SkipListNode *node, FILLP_BOOL errIfConflict);
116
117 /*******************************************************************************
118 Function : SkipListPopValue
119
120 Description : This function will be invoked to pop a value from SkipList.
121
122 Input : list - SkipList to be destroyed
123
124 Output : None
125
126 Return : None
127 *******************************************************************************/
128 void *SkipListPopValue(struct SkipList *list);
129
130
131 /*******************************************************************************
132 Function : SkipListPopTail
133
134 Description : This function will be invoked to pop tail value from SkipList.
135
136 Input : list - SkipList pointer
137
138 Output : None
139
140 Return : None
141 *******************************************************************************/
142 void *SkipListPopTail(struct SkipList *list);
143
144
145 /*******************************************************************************
146 Function : SkiplistDestroy
147
148 Description : This function will be invoked to destroy the SkipList.
149
150 Input : list - SkipList to be destroyed
151
152 Output : None
153
154 Return : None
155 *******************************************************************************/
156 void SkiplistDestroy(struct SkipList *list);
157
158 FILLP_UINT32 SkiplistGetNodeNum(struct SkipList *list);
159
160 #ifdef __cplusplus
161 }
162 #endif
163 #endif /* SKIPLIST_H */