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 "mem_pool.h"
19 #include "log.h"
20
21 #ifdef __cplusplus
22 extern "C" {
23 #endif
24
25 #define MAX_SKIPLIST_LEVEL 16
26
27 typedef FILLP_INT (*funcSkiplistCompair)(void *v1, void *v2);
28
29 struct SkipListNode {
30 void *item; /* value */
31 struct SkipListNode *forward[MAX_SKIPLIST_LEVEL]; /* level next */
32 struct SkipListNode *pre[MAX_SKIPLIST_LEVEL];
33 FILLP_INT level;
34 #ifdef FILLP_64BIT_ALIGN
35 FILLP_UINT8 padd[4];
36 #endif
37 };
38
39 struct SkipList {
40 struct SkipListNode *head;
41 struct SkipListNode *tail;
42
43 struct SkipListNode *hnode[MAX_SKIPLIST_LEVEL]; /* point to the first node of each level */
44 struct SkipListNode *tnode[MAX_SKIPLIST_LEVEL]; /* point to the last node of each level */
45 FILLP_INT level; /* the current max level of list */
46 FILLP_UINT32 nodeNum;
47 funcSkiplistCompair funcCmp;
48 FILLP_UINT8 randomLev[MAX_RANDOM_LEV];
49 FILLP_UINT32 randomIndex;
50 };
51
52 /*******************************************************************************
53 Function : SkipListGetPop
54
55 Description : This function will be invoked to pop the head node from
56 SkipList.
57
58 Input : list - SkipList pointer
59
60 Output : None
61
62 Return : None
63 *******************************************************************************/
SkipListGetPop(struct SkipList * list)64 static __inline struct SkipListNode *SkipListGetPop(struct SkipList *list)
65 {
66 return ((list == FILLP_NULL_PTR) || (list->head == FILLP_NULL_PTR)) ? FILLP_NULL_PTR : list->head;
67 }
68
69 /*******************************************************************************
70 Function : SkipListGetTail
71
72 Description : This function will be invoked to pop the head node from
73 SkipList.
74
75 Input : list - SkipList pointer
76
77 Output : None
78
79 Return : None
80 *******************************************************************************/
SkipListGetTail(struct SkipList * list)81 static __inline struct SkipListNode *SkipListGetTail(struct SkipList *list)
82 {
83 return ((list == FILLP_NULL_PTR) || (list->tail == FILLP_NULL_PTR)) ? FILLP_NULL_PTR : list->tail;
84 }
85
86 /*******************************************************************************
87 Function : SkiplistInit
88
89 Description : This function will be invoked to init the SkipList.
90
91 Input : list - SkipList to be initialised
92 cmp - SkipList compare function
93
94 Output : None
95
96 Return : If success, returns ERR_OK. Otherwise, returns Error code.
97 *******************************************************************************/
98 FILLP_INT SkiplistInit(struct SkipList *list, funcSkiplistCompair cmp);
99
100 /*******************************************************************************
101 Function : SkipListInsert
102
103 Description : This function will be invoked to insert a node to SkipList.
104
105 Input : list - SkipList pointer
106 item - value of the SkipList node
107 node - SkipList node to be inserted to SkipList
108 err_if_conflict - Flag to decide whether to give error if any
109 conflicts between item of node to be inserted and existing
110 node
111
112 Output : None
113
114 Return : ERR_OK, if success. Error codes on failures.
115 *******************************************************************************/
116 FILLP_INT SkipListInsert(struct SkipList *list, void *item, struct SkipListNode *node, FILLP_BOOL errIfConflict);
117
118 /*******************************************************************************
119 Function : SkipListPopValue
120
121 Description : This function will be invoked to pop a value from SkipList.
122
123 Input : list - SkipList to be destroyed
124
125 Output : None
126
127 Return : None
128 *******************************************************************************/
129 void *SkipListPopValue(struct SkipList *list);
130
131
132 /*******************************************************************************
133 Function : SkipListPopTail
134
135 Description : This function will be invoked to pop tail value from SkipList.
136
137 Input : list - SkipList pointer
138
139 Output : None
140
141 Return : None
142 *******************************************************************************/
143 void *SkipListPopTail(struct SkipList *list);
144
145
146 /*******************************************************************************
147 Function : SkiplistDestroy
148
149 Description : This function will be invoked to destroy the SkipList.
150
151 Input : list - SkipList to be destroyed
152
153 Output : None
154
155 Return : None
156 *******************************************************************************/
157 void SkiplistDestroy(struct SkipList *list);
158
159 FILLP_UINT32 SkiplistGetNodeNum(struct SkipList *list);
160
161 #ifdef __cplusplus
162 }
163 #endif
164 #endif /* SKIPLIST_H */