-
Notifications
You must be signed in to change notification settings - Fork 42
/
bst-aravind.h
132 lines (105 loc) · 3.37 KB
/
bst-aravind.h
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
129
130
131
132
/*
* File: bst-aravind.h
* Author: Tudor David <[email protected]>
* Description: Aravind Natarajan and Neeraj Mittal.
* Fast Concurrent Lock-free Binary Search Trees. PPoPP 2014
* bst-aravind.h is part of ASCYLIB
*
* Copyright (c) 2014 Vasileios Trigonakis <[email protected]>,
* Tudor David <[email protected]>
* Distributed Programming Lab (LPD), EPFL
*
* ASCYLIB is free software: you can redistribute it and/or
* modify it under the terms of the GNU General Public License
* as published by the Free Software Foundation, version 2
* of the License.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
*/
#ifndef _BST_ARAVIND_H_INCLUDED_
#define _BST_ARAVIND_H_INCLUDED_
#include <stdio.h>
#include <stdlib.h>
#include "utils.h"
#include "lock_if.h"
#include "common.h"
#include "atomic_ops_if.h"
#include "ssalloc.h"
#include "ssmem.h"
#define max(a,b) \
({ __typeof__ (a) _a = (a); \
__typeof__ (b) _b = (b); \
_a > _b ? _a : _b; })
#define TRUE 1
#define FALSE 0
#define INF2 (KEY_MAX + 2)
#define INF1 (KEY_MAX + 1)
#define INF0 (KEY_MAX)
#define MAX_KEY KEY_MAX
#define MIN_KEY 0
typedef uint8_t bool_t;
extern __thread ssmem_allocator_t* alloc;
typedef ALIGNED(64) struct node_t node_t;
struct node_t{
skey_t key;
sval_t value;
volatile node_t* right;
volatile node_t* left;
uint8_t padding[32];
};
#ifndef __tile__
#ifndef __sparc__
static inline void set_bit(volatile uintptr_t* *array, int bit) {
asm("bts %1,%0" : "+m" (*array) : "r" (bit));
}
static inline bool_t set_bit2(volatile uintptr_t *array, int bit) {
// asm("bts %1,%0" : "+m" (*array): "r" (bit));
bool_t flag;
__asm__ __volatile__("lock bts %2,%1; setb %0" : "=q" (flag) : "m" (*array), "r" (bit)); return flag;
return flag;
}
#endif
#endif
typedef ALIGNED(CACHE_LINE_SIZE) struct seek_record_t{
node_t* ancestor;
node_t* successor;
node_t* parent;
node_t* leaf;
uint8_t padding[32];
} seek_record_t;
//extern __thread seek_record_t* seek_record;
node_t* initialize_tree();
void bst_init_local();
node_t* create_node(skey_t k, sval_t value, int initializing);
seek_record_t * bst_seek(skey_t key, node_t* node_r);
sval_t bst_search(skey_t key, node_t* node_r);
bool_t bst_insert(skey_t key, sval_t val, node_t* node_r);
sval_t bst_remove(skey_t key, node_t* node_r);
bool_t bst_cleanup(skey_t key);
uint32_t bst_size(volatile node_t* r);
static inline uint64_t GETFLAG(volatile node_t* ptr) {
return ((uint64_t)ptr) & 1;
}
static inline uint64_t GETTAG(volatile node_t* ptr) {
return ((uint64_t)ptr) & 2;
}
static inline uint64_t FLAG(node_t* ptr) {
return (((uint64_t)ptr)) | 1;
}
static inline uint64_t TAG(node_t* ptr) {
return (((uint64_t)ptr)) | 2;
}
static inline uint64_t UNTAG(node_t* ptr) {
return (((uint64_t)ptr) & 0xfffffffffffffffd);
}
static inline uint64_t UNFLAG(node_t* ptr) {
return (((uint64_t)ptr) & 0xfffffffffffffffe);
}
static inline node_t* ADDRESS(volatile node_t* ptr) {
return (node_t*) (((uint64_t)ptr) & 0xfffffffffffffffc);
}
#endif