1 files changed, 178 insertions, 0 deletions
diff --git a/libs/tgl/tl-parser/src/tl-parser-tree.h b/libs/tgl/tl-parser/src/tl-parser-tree.h
new file mode 100644
index 0000000000..fba7c67521
--- /dev/null
+++ b/libs/tgl/tl-parser/src/tl-parser-tree.h
@@ -0,0 +1,178 @@
+/* 
+    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-2014
+*/
+#ifndef __TREE_H__
+#define __TREE_H__
+#include <stdio.h>
+
+#include <memory.h>
+#include <assert.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 = malloc (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) {\
+  free (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