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