diff options
Diffstat (limited to 'protocols/Telegram/src/tgl/tree.h')
| -rw-r--r-- | protocols/Telegram/src/tgl/tree.h | 179 |
1 files changed, 0 insertions, 179 deletions
diff --git a/protocols/Telegram/src/tgl/tree.h b/protocols/Telegram/src/tgl/tree.h deleted file mode 100644 index 18feb3aed5..0000000000 --- a/protocols/Telegram/src/tgl/tree.h +++ /dev/null @@ -1,179 +0,0 @@ -/* - 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 |