1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
|
/**************************************************************************/
/* */
/* OCaml */
/* */
/* Sadiq Jaffer, OCaml Labs Consultancy Ltd */
/* Xavier Leroy, projet Cambium, INRIA Paris */
/* */
/* Copyright 2021 OCaml Labs Consultancy Ltd */
/* Copyright 2020 Institut National de Recherche en Informatique et */
/* en Automatique. */
/* */
/* All rights reserved. This file is distributed under the terms of */
/* the GNU Lesser General Public License version 2.1, with the */
/* special exception on linking described in the file LICENSE. */
/* */
/**************************************************************************/
/* A concurrent dictionary data structure implemented as skip lists. See
implementation for much more detail. */
/* Keys and associated data are natural-width integers (type [uintnat]).
Key values 0 and uintnat_max are reserved for internal use; do not use.
Pointers can be used too, modulo conversion to [uintnat]. */
#ifndef CAML_SKIPLIST_H
#define CAML_SKIPLIST_H
#ifdef CAML_INTERNALS
#include "config.h"
#define NUM_LEVELS 17
/* The head of a skip list */
struct lf_skiplist {
struct lf_skipcell *head;
struct lf_skipcell *tail;
uintnat _Atomic search_level; /* racy level to start searches at */
struct lf_skipcell *_Atomic garbage_head;
};
/* The cells of a skip list */
struct lf_skipcell {
uintnat key;
uintnat data;
uintnat top_level;
void *stat_block;
struct lf_skipcell *_Atomic garbage_next;
#if (__STDC_VERSION__ >= 199901L)
struct lf_skipcell *_Atomic forward[]; /* variable-length array */
#else
struct lf_skipcell *_Atomic forward[1]; /* variable-length array */
#endif
};
/* Initialize a skip list */
extern void caml_lf_skiplist_init(struct lf_skiplist *sk);
/* Search a skip list.
If [key] is found, store associated data in [*data] and return 1.
If [key] is not found, return 0 and leave [*data] unchanged. */
extern int caml_lf_skiplist_find(struct lf_skiplist *sk, uintnat key,
/*out*/ uintnat *data);
/* Search the entry of the skip list that has the largest key less than
or equal to [k].
If such an entry exists, store its key in [*key], the associated data in
[*data], and return 1.
If no such entry exists (all keys in the skip list are strictly greater
than [k]), return 0 and leave [*key] and [*data] unchanged. */
extern int caml_lf_skiplist_find_below(struct lf_skiplist *sk, uintnat k,
/*out*/ uintnat *key,
/*out*/ uintnat *data);
/* Insertion in a skip list. [key] must be between 1 and UINTNAT_MAX-1.
If [key] was already there, change the associated data and return 1.
If [key] was not there, insert new [key, data] binding and return 0. */
extern int caml_lf_skiplist_insert(struct lf_skiplist *sk, uintnat key,
uintnat data);
/* Deletion in a skip list.
If [key] was there, remove it and return 1.
If [key] was not there, leave the skip list unchanged and return 0. */
extern int caml_lf_skiplist_remove(struct lf_skiplist *sk, uintnat key);
/* This must only be called by a single domain during a stop-the world
protected by global barriers. */
extern void caml_lf_skiplist_free_garbage(struct lf_skiplist *sk);
/* Macros used for marking pointers and that are unfortunately necessary
in the header for FOREACH_LF_SKIPLIST_ELEMENT to work */
#define LF_SK_IS_MARKED(p) ((p)&1)
#define LF_SK_MARKED(p) ((struct lf_skipcell *)(((uintptr_t)(p)) | 1))
#define LF_SK_UNMARK(p) ((struct lf_skipcell *)(((uintptr_t)(p)) & ~1))
#define LF_SK_EXTRACT(from, mark_to, ptr_to) \
{ \
uintptr_t tmp = \
(uintptr_t)atomic_load_explicit(&from, memory_order_acquire); \
mark_to = LF_SK_IS_MARKED(tmp); \
ptr_to = LF_SK_UNMARK(tmp); \
}
/* Iterate over a skip list, in increasing order of keys.
[var] designates the current element.
[action] can refer to [var->key] and [var->data].
[action] can safely remove the current element, i.e. call
[caml_skiplist_remove] on [var->key]. The traversal will
continue with the skiplist element following the removed element.
Other operations performed over the skiplist during its traversal have
unspecified effects on the traversal. */
#define FOREACH_LF_SKIPLIST_ELEMENT(var, sk, action) \
{ \
struct lf_skipcell *var, *caml__next; \
int caml__marked; \
var = (sk)->head->forward[0]; \
while (var != (sk)->tail) { \
LF_SK_EXTRACT(var->forward[0], caml__marked, caml__next); \
if (!caml__marked) { \
action; \
} \
var = caml__next; \
} \
}
#endif /* CAML_INTERNALS */
#endif /* CAML_SKIPLIST_H */
|
