diff options
Diffstat (limited to 'protocols/Telegram/src/tgl/tree.h')
| -rw-r--r-- | protocols/Telegram/src/tgl/tree.h | 179 |
1 files changed, 179 insertions, 0 deletions
diff --git a/protocols/Telegram/src/tgl/tree.h b/protocols/Telegram/src/tgl/tree.h new file mode 100644 index 0000000000..18feb3aed5 --- /dev/null +++ b/protocols/Telegram/src/tgl/tree.h @@ -0,0 +1,179 @@ +/* + This file is part of tgl-library + + This library is free software; you can redistribute it and/or + modify it under the terms of the GNU Lesser General Public + License as published by the Free Software Foundation; either + version 2.1 of the License, or (at your option) any later version. + + This library 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 + Lesser General Public License for more details. + + You should have received a copy of the GNU Lesser General Public + License along with this library; if not, write to the Free Software + Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA + + Copyright Vitaly Valtman 2013-2015 +*/ +#ifndef __TREE_H__ +#define __TREE_H__ +#include <stdio.h> + +#include <memory.h> +#include <assert.h> +#include "tools.h" + +#pragma pack(push,4) +#define DEFINE_TREE(X_NAME, X_TYPE, X_CMP, X_UNSET) \ +struct tree_ ## X_NAME { \ + struct tree_ ## X_NAME *left, *right;\ + X_TYPE x;\ + int y;\ +};\ +\ +static struct tree_ ## X_NAME *new_tree_node_ ## X_NAME (X_TYPE x, int y) {\ + struct tree_ ## X_NAME *T = talloc (sizeof (*T));\ + T->x = x;\ + T->y = y;\ + T->left = T->right = 0;\ + return T;\ +}\ +\ +static void delete_tree_node_ ## X_NAME (struct tree_ ## X_NAME *T) {\ + tfree (T, sizeof (*T));\ +}\ +\ +static void tree_split_ ## X_NAME (struct tree_ ## X_NAME *T, X_TYPE x, struct tree_ ## X_NAME **L, struct tree_ ## X_NAME **R) {\ + if (!T) {\ + *L = *R = 0;\ + } else {\ + int c = X_CMP (x, T->x);\ + if (c < 0) {\ + tree_split_ ## X_NAME (T->left, x, L, &T->left);\ + *R = T;\ + } else {\ + tree_split_ ## X_NAME (T->right, x, &T->right, R);\ + *L = T;\ + }\ + }\ +}\ +\ +static struct tree_ ## X_NAME *tree_insert_ ## X_NAME (struct tree_ ## X_NAME *T, X_TYPE x, int y) __attribute__ ((warn_unused_result,unused));\ +static struct tree_ ## X_NAME *tree_insert_ ## X_NAME (struct tree_ ## X_NAME *T, X_TYPE x, int y) {\ + if (!T) {\ + return new_tree_node_ ## X_NAME (x, y);\ + } else {\ + if (y > T->y) {\ + struct tree_ ## X_NAME *N = new_tree_node_ ## X_NAME (x, y);\ + tree_split_ ## X_NAME (T, x, &N->left, &N->right);\ + return N;\ + } else {\ + int c = X_CMP (x, T->x);\ + assert (c);\ + if (c < 0) { \ + T->left = tree_insert_ ## X_NAME (T->left, x, y);\ + } else { \ + T->right = tree_insert_ ## X_NAME (T->right, x, y);\ + } \ + return T; \ + }\ + }\ +}\ +\ +static struct tree_ ## X_NAME *tree_merge_ ## X_NAME (struct tree_ ## X_NAME *L, struct tree_ ## X_NAME *R) {\ + if (!L || !R) {\ + return L ? L : R;\ + } else {\ + if (L->y > R->y) {\ + L->right = tree_merge_ ## X_NAME (L->right, R);\ + return L;\ + } else {\ + R->left = tree_merge_ ## X_NAME (L, R->left);\ + return R;\ + }\ + }\ +}\ +\ +static struct tree_ ## X_NAME *tree_delete_ ## X_NAME (struct tree_ ## X_NAME *T, X_TYPE x) __attribute__ ((warn_unused_result,unused));\ +static struct tree_ ## X_NAME *tree_delete_ ## X_NAME (struct tree_ ## X_NAME *T, X_TYPE x) {\ + assert (T);\ + int c = X_CMP (x, T->x);\ + if (!c) {\ + struct tree_ ## X_NAME *N = tree_merge_ ## X_NAME (T->left, T->right);\ + delete_tree_node_ ## X_NAME (T);\ + return N;\ + } else {\ + if (c < 0) { \ + T->left = tree_delete_ ## X_NAME (T->left, x); \ + } else { \ + T->right = tree_delete_ ## X_NAME (T->right, x); \ + } \ + return T; \ + }\ +}\ +\ +static X_TYPE tree_get_min_ ## X_NAME (struct tree_ ## X_NAME *t) __attribute__ ((unused));\ +static X_TYPE tree_get_min_ ## X_NAME (struct tree_ ## X_NAME *T) {\ + if (!T) { return X_UNSET; } \ + while (T->left) { T = T->left; }\ + return T->x; \ +} \ +\ +static X_TYPE tree_lookup_ ## X_NAME (struct tree_ ## X_NAME *T, X_TYPE x) __attribute__ ((unused));\ +static X_TYPE tree_lookup_ ## X_NAME (struct tree_ ## X_NAME *T, X_TYPE x) {\ + int c;\ + while (T && (c = X_CMP (x, T->x))) {\ + T = (c < 0 ? T->left : T->right);\ + }\ + return T ? T->x : X_UNSET;\ +}\ +\ +static void tree_act_ ## X_NAME (struct tree_ ## X_NAME *T, void (*act)(X_TYPE)) __attribute__ ((unused));\ +static void tree_act_ ## X_NAME (struct tree_ ## X_NAME *T, void (*act)(X_TYPE)) {\ + if (!T) { return; } \ + tree_act_ ## X_NAME (T->left, act); \ + act (T->x); \ + tree_act_ ## X_NAME (T->right, act); \ +}\ +\ +static void tree_act_ex_ ## X_NAME (struct tree_ ## X_NAME *T, void (*act)(X_TYPE, void *), void *extra) __attribute__ ((unused));\ +static void tree_act_ex_ ## X_NAME (struct tree_ ## X_NAME *T, void (*act)(X_TYPE, void *), void *extra) {\ + if (!T) { return; } \ + tree_act_ex_ ## X_NAME (T->left, act, extra); \ + act (T->x, extra); \ + tree_act_ex_ ## X_NAME (T->right, act, extra); \ +}\ +\ +static int tree_count_ ## X_NAME (struct tree_ ## X_NAME *T) __attribute__ ((unused));\ +static int tree_count_ ## X_NAME (struct tree_ ## X_NAME *T) { \ + if (!T) { return 0; }\ + return 1 + tree_count_ ## X_NAME (T->left) + tree_count_ ## X_NAME (T->right); \ +}\ +static void tree_check_ ## X_NAME (struct tree_ ## X_NAME *T) __attribute__ ((unused));\ +static void tree_check_ ## X_NAME (struct tree_ ## X_NAME *T) { \ + if (!T) { return; }\ + if (T->left) { \ + assert (T->left->y <= T->y);\ + assert (X_CMP (T->left->x, T->x) < 0); \ + }\ + if (T->right) { \ + assert (T->right->y <= T->y);\ + assert (X_CMP (T->right->x, T->x) > 0); \ + }\ + tree_check_ ## X_NAME (T->left); \ + tree_check_ ## X_NAME (T->right); \ +}\ +static struct tree_ ## X_NAME *tree_clear_ ## X_NAME (struct tree_ ## X_NAME *T) __attribute__ ((unused));\ +static struct tree_ ## X_NAME *tree_clear_ ## X_NAME (struct tree_ ## X_NAME *T) { \ + if (!T) { return 0; }\ + tree_clear_ ## X_NAME (T->left); \ + tree_clear_ ## X_NAME (T->right); \ + delete_tree_node_ ## X_NAME (T); \ + return 0; \ +} \ + +#define int_cmp(a,b) ((a) - (b)) +#pragma pack(pop) +#endif |