1/*
2 This file is part of Mtproto-proxy Library.
3
4 Mtproto-proxy Library is free software: you can redistribute it and/or modify
5 it under the terms of the GNU Lesser General Public License as published by
6 the Free Software Foundation, either version 2 of the License, or
7 (at your option) any later version.
8
9 Mtproto-proxy Library is distributed in the hope that it will be useful,
10 but WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 GNU Lesser General Public License for more details.
13
14 You should have received a copy of the GNU Lesser General Public License
15 along with Mtproto-proxy Library. If not, see <http://www.gnu.org/licenses/>.
16
17 Copyright 2012-2013 Vkontakte Ltd
18 2012-2013 Vitaliy Valtman
19
20 Copyright 2014-2016 Telegram Messenger Inc
21 2014-2016 Vitaly Valtman
22*/
23
24struct tree_any_ptr {
25 struct tree_any_ptr *left, *right;
26 void *x;
27 int y;
28};
29
30static inline void tree_act_any (struct tree_any_ptr *T, void (*f)(void *)) {
31 if (!T) { return; }
32 tree_act_any (T->left, f);
33 f (T->x);
34 tree_act_any (T->right, f);
35}
36
37static inline void tree_act_any_ex (struct tree_any_ptr *T, void (*f)(void *, void *), void *extra) {
38 if (!T) { return; }
39 tree_act_any_ex (T->left, f, extra);
40 f (T->x, extra);
41 tree_act_any_ex (T->right, f, extra);
42}
43
44static inline void tree_act_any_ex2 (struct tree_any_ptr *T, void (*f)(void *, void *, void *), void *extra, void *extra2) {
45 if (!T) { return; }
46 tree_act_any_ex2 (T->left, f, extra, extra2);
47 f (T->x, extra, extra2);
48 tree_act_any_ex2 (T->right, f, extra, extra2);
49}
50
51static inline void tree_act_any_ex3 (struct tree_any_ptr *T, void (*f)(void *, void *, void *, void *), void *extra, void *extra2, void *extra3) {
52 if (!T) { return; }
53 tree_act_any_ex3 (T->left, f, extra, extra2, extra3);
54 f (T->x, extra, extra2, extra3);
55 tree_act_any_ex3 (T->right, f, extra, extra2, extra3);
56}
57
58
59#define DEFINE_HASH(prefix,name,value_t,value_compare,value_hash) \
60 prefix hash_elem_ ## name ## _t *hash_lookup_ ## name (hash_table_ ## name ## _t *T, value_t x) __attribute__ ((unused)); \
61 prefix void hash_insert_ ## name (hash_table_ ## name ## _t *T, value_t x) __attribute__ ((unused)); \
62 prefix int hash_delete_ ## name (hash_table_ ## name ## _t *T, value_t x) __attribute__ ((unused)); \
63 prefix void hash_clear_ ## name (hash_table_ ## name ## _t *T) __attribute__ ((unused)); \
64 prefix void hash_clear_act_ ## name (hash_table_ ## name ## _t *T, void (*act)(value_t)) __attribute__ ((unused)); \
65 prefix hash_elem_ ## name ## _t *hash_lookup_ ## name (hash_table_ ## name ## _t *T, value_t x) { \
66 long long hash = value_hash (x); if (hash < 0) { hash = -hash; } if (hash < 0) { hash = 0;} \
67 if (T->mask) { hash = hash & T->mask;} \
68 else { hash %= (T->size);} \
69 if (!T->E[hash]) { return 0; } \
70 hash_elem_ ## name ## _t *E = T->E[hash]; \
71 do { \
72 if (!value_compare (E->x, x)) { return E; } \
73 E = E->next; \
74 } while (E != T->E[hash]); \
75 return 0; \
76 } \
77 \
78 prefix void hash_insert_ ## name (hash_table_ ## name ## _t *T, value_t x) { \
79 long long hash = value_hash (x); if (hash < 0) { hash = -hash; } if (hash < 0) { hash = 0;} \
80 if (T->mask) { hash = hash & T->mask;} \
81 else { hash %= (T->size);} \
82 hash_elem_ ## name ## _t *E = hash_alloc_ ## name (x); \
83 if (T->E[hash]) { \
84 E->next = T->E[hash]; \
85 E->prev = T->E[hash]->prev; \
86 E->next->prev = E; \
87 barrier (); \
88 E->prev->next = E; \
89 } else { \
90 E->next = E; \
91 E->prev = E; \
92 barrier (); \
93 T->E[hash] = E; \
94 } \
95 } \
96 \
97 prefix int hash_delete_ ## name (hash_table_ ## name ## _t *T, value_t x) { \
98 long long hash = value_hash (x); if (hash < 0) { hash = -hash; } if (hash < 0) { hash = 0;} \
99 if (T->mask) { hash = hash & T->mask;} \
100 else { hash %= (T->size);} \
101 if (!T->E[hash]) { return 0; } \
102 hash_elem_ ## name ## _t *E = T->E[hash]; \
103 int ok = 0; \
104 do { \
105 if (!value_compare (E->x, x)) { ok = 1; break; } \
106 E = E->next; \
107 } while (E != T->E[hash]); \
108 if (!ok) { return 0; } \
109 E->next->prev = E->prev; \
110 E->prev->next = E->next; \
111 if (T->E[hash] != E) { \
112 hash_free_ ## name (E); \
113 } else if (E->next == E) { \
114 T->E[hash] = 0; \
115 hash_free_ ## name (E); \
116 } else { \
117 T->E[hash] = E->next; \
118 hash_free_ ## name (E); \
119 } \
120 return 1; \
121 } \
122 \
123 prefix void hash_clear_ ## name (hash_table_ ## name ## _t *T) { \
124 int i; \
125 for (i = 0; i < T->size; i++) { \
126 if (T->E[i]) { \
127 hash_elem_ ## name ## _t *cur = T->E[i]; \
128 hash_elem_ ## name ## _t *first = cur; \
129 do { \
130 void *next = cur->next; \
131 hash_free_ ## name (cur); \
132 cur = next; \
133 } while (cur != first); \
134 T->E[i] = 0; \
135 } \
136 } \
137 } \
138 \
139 prefix void hash_clear_act_ ## name (hash_table_ ## name ## _t *T, void (*act)(value_t)) { \
140 int i; \
141 for (i = 0; i < T->size; i++) { \
142 if (T->E[i]) { \
143 hash_elem_ ## name ## _t *cur = T->E[i]; \
144 hash_elem_ ## name ## _t *first = cur; \
145 do { \
146 void *next = cur->next; \
147 act (cur->x); \
148 hash_free_ ## name (cur); \
149 cur = next; \
150 } while (cur != first); \
151 T->E[i] = 0; \
152 } \
153 } \
154 } \
155
156
157#define DEFINE_HASH_STD_ALLOC_PREFIX(prefix,name,value_t,value_compare,value_hash)\
158 DECLARE_HASH_TYPE(name,value_t) \
159 prefix hash_elem_ ## name ## _t *hash_alloc_ ## name (value_t x); \
160 prefix void hash_free_ ## name (hash_elem_ ## name ## _t *T); \
161 DEFINE_HASH(prefix,name,value_t,value_compare,value_hash); \
162 hash_elem_ ## name ## _t *hash_alloc_ ## name (value_t x) { \
163 hash_elem_ ## name ## _t *E = zmalloc (sizeof (*E)); \
164 E->x = x; \
165 return E; \
166 } \
167 void hash_free_ ## name (hash_elem_ ## name ## _t *E) { \
168 zfree (E, sizeof (*E)); \
169 } \
170
171#define DEFINE_HASH_STDNOZ_ALLOC_PREFIX(prefix,name,value_t,value_compare,value_hash)\
172 DECLARE_HASH_TYPE(name,value_t) \
173 prefix hash_elem_ ## name ## _t *hash_alloc_ ## name (value_t x); \
174 prefix void hash_free_ ## name (hash_elem_ ## name ## _t *T); \
175 DEFINE_HASH(prefix,name,value_t,value_compare,value_hash); \
176 hash_elem_ ## name ## _t *hash_alloc_ ## name (value_t x) { \
177 hash_elem_ ## name ## _t *E = malloc (sizeof (*E)); \
178 E->x = x; \
179 return E; \
180 } \
181 void hash_free_ ## name (hash_elem_ ## name ## _t *E) { \
182 free (E); \
183 } \
184
185#define DEFINE_HASH_STD_ALLOC(name,value_t,value_compare,value_hash) \
186 DEFINE_HASH_STD_ALLOC_PREFIX(static,name,value_t,value_compare,value_hash)
187
188#define DEFINE_HASH_STDNOZ_ALLOC(name,value_t,value_compare,value_hash) \
189 DEFINE_HASH_STDNOZ_ALLOC_PREFIX(static,name,value_t,value_compare,value_hash)
190
191#define DECLARE_HASH_TYPE(name,value_t) \
192 struct hash_elem_ ## name { \
193 struct hash_elem_ ## name *next, *prev;\
194 value_t x;\
195 }; \
196 struct hash_table_ ## name {\
197 struct hash_elem_ ## name **E; \
198 int size; \
199 int mask; \
200 }; \
201 typedef struct hash_elem_ ## name hash_elem_ ## name ## _t; \
202 typedef struct hash_table_ ## name hash_table_ ## name ## _t; \
203
204#define HASH_DEG2(name,deg) \
205 static struct hash_elem_ ## name *_hash_arr_ ## name[(1 << (deg))]; \
206 static struct hash_table_ ## name hash_table_ ## name ## _ptr = { \
207 .E = _hash_arr_ ## name, \
208 .size = (1 << (deg)), \
209 .mask = (1 << (deg)) - 1 \
210 }; \
211 static struct hash_table_ ## name *hash_table_ ## name = & hash_table_ ## name ## _ptr;
212
213
214#define std_int_compare(a,b) ((a) - (b))
215#define std_ll_ptr_compare(a,b) ((*(long long *)(a)) - (*(long long *)(b)))
216#define std_int_hash(x) ((x) >= 0 ? (x) : -(x) >= 0 ? -(x) : 0)
217