summaryrefslogtreecommitdiff
path: root/Build/source/texk/xdvik/util.c
diff options
context:
space:
mode:
authorPeter Breitenlohner <peb@mppmu.mpg.de>2013-04-08 06:34:46 +0000
committerPeter Breitenlohner <peb@mppmu.mpg.de>2013-04-08 06:34:46 +0000
commit7e0f3484d8cd6eca4abe80d057391d14face5606 (patch)
tree92570fc98a476ecbf696c2ef16d046412d405995 /Build/source/texk/xdvik/util.c
parent824f7b0903de8ad7f6ee3d7656005e4c59155e06 (diff)
xdvik 22.86
git-svn-id: svn://tug.org/texlive/trunk@29732 c570f23f-e606-0410-a88d-b1316a301751
Diffstat (limited to 'Build/source/texk/xdvik/util.c')
-rw-r--r--Build/source/texk/xdvik/util.c150
1 files changed, 145 insertions, 5 deletions
diff --git a/Build/source/texk/xdvik/util.c b/Build/source/texk/xdvik/util.c
index 3915af93a82..8dbd1fa7cbd 100644
--- a/Build/source/texk/xdvik/util.c
+++ b/Build/source/texk/xdvik/util.c
@@ -1,6 +1,6 @@
/*========================================================================*\
-Copyright (c) 1990-2004 Paul Vojta and others
+Copyright (c) 1990-2013 Paul Vojta and others
Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to
@@ -83,6 +83,10 @@ extern void *malloc();
extern void *realloc();
#endif
+#if HAVE_XKB_BELL_EXT
+# include <X11/XKBlib.h>
+# define XBell(dpy, percent) XkbBell(dpy, mane.win, percent, (Atom) None)
+#endif
/* if POSIX O_NONBLOCK is not available, use O_NDELAY */
#if !defined O_NONBLOCK && defined O_NDELAY
@@ -206,8 +210,8 @@ struct debug_string_options debug_options[] = {
{ DBG_HTEX, "htex", ", " },
{ DBG_SRC_SPECIALS,"src", ", " },
{ DBG_CLIENT, "client", ", " },
- { DBG_T1, "t1", ", " },
- { DBG_T1_VERBOSE, "t1_verbose", ",\n"},
+ { DBG_FT, "ft", ", " },
+ { DBG_FT_VERBOSE, "ft_verbose", ",\n"},
{ DBG_GUI, "gui", ", " },
{ DBG_FIND, "find", ", " },
{ DBG_FILES, "files", ", " },
@@ -642,6 +646,7 @@ xstrdup(const char *str)
return new;
}
+#endif /* not KPATHSEA */
/*
@@ -658,8 +663,6 @@ xmemdup(const char *str, size_t len)
return new;
}
-#endif /* not KPATHSEA */
-
/* like xstrdup(), but with XtMalloc() */
char *
xt_strdup(const char *ptr)
@@ -1577,6 +1580,143 @@ put_str_int_hash(hashTableT *hashtable, const char *key, size_t val)
hash_insert(hashtable, key, (const string)ptr);
}
+
+#if FREETYPE || PS
+
+/*
+ * General AVL tree mechanism. Search for a node, and return it if found.
+ * Otherwise insert a node.
+ * This uses the AVL algorithm from Knuth Vol. 3.
+ */
+
+struct avl *
+avladd(const char *key, size_t key_len, struct avl **headp, size_t size)
+{
+ struct avl *ap;
+ struct avl **app;
+ struct avl *sp; /* place where rebalancing may be necessary */
+ struct avl **spp; /* points to sp */
+ int i;
+
+ /* Search */
+ spp = app = headp;
+ for (;;) {
+ ap = *app;
+ if (ap == NULL) /* bottom of tree */
+ break;
+ if (ap->bal != 0)
+ spp = app;
+ i = key_len - ap->key_len;
+ if (i == 0)
+ i = memcmp(key, ap->key, key_len);
+ if (i == 0) /* found record already */
+ return ap;
+ if (i < 0) /* move left */
+ app = &ap->left;
+ else
+ app = &ap->right;
+ }
+
+ /* Insert */
+ ap = xmalloc(size);
+ ap->key = key;
+ ap->key_len = key_len;
+ ap->bal = 0;
+ ap->left = ap->right = NULL;
+ *app = ap;
+
+ /* Adjust balance factors */
+ sp = *spp;
+ if (sp == ap)
+ return ap;
+ i = key_len - sp->key_len;
+ if (i == 0)
+ i = memcmp(key, sp->key, key_len);
+ sp = (i < 0 ? sp->left : sp->right);
+ while (sp != ap) {
+ i = key_len - sp->key_len;
+ if (i == 0)
+ i = memcmp(key, sp->key, key_len);
+ if (i < 0) {
+ sp->bal = -1;
+ sp = sp->left;
+ }
+ else {
+ sp->bal = 1;
+ sp = sp->right;
+ }
+ }
+
+ /* Balancing act */
+ sp = *spp;
+ i = key_len - sp->key_len;
+ if (i == 0)
+ i = memcmp(key, sp->key, key_len);
+ if (i < 0) {
+ if (sp->bal >= 0)
+ --sp->bal;
+ else { /* need to rebalance */
+ struct avl *left;
+
+ left = sp->left;
+ if (left->bal < 0) { /* single rotation */
+ sp->left = left->right;
+ left->right = sp;
+ sp->bal = left->bal = 0;
+ *spp = left;
+ }
+ else { /* double rotation */
+ struct avl *newtop;
+
+ newtop = left->right;
+ sp->left = newtop->right;
+ newtop->right = sp;
+ left->right = newtop->left;
+ newtop->left = left;
+ sp->bal = left->bal = 0;
+ if (newtop->bal < 0) ++sp->bal;
+ else if (newtop->bal > 0) --left->bal;
+ newtop->bal = 0;
+ *spp = newtop;
+ }
+ }
+ }
+ else {
+ if (sp->bal <= 0)
+ ++sp->bal;
+ else { /* need to rebalance */
+ struct avl *right;
+
+ right = sp->right;
+ if (right->bal > 0) { /* single rotation */
+ sp->right = right->left;
+ right->left = sp;
+ sp->bal = right->bal = 0;
+ *spp = right;
+ }
+ else { /* double rotation */
+ struct avl *newtop;
+
+ newtop = right->left;
+ sp->right = newtop->left;
+ newtop->left = sp;
+ right->left = newtop->right;
+ newtop->right = right;
+ sp->bal = right->bal = 0;
+ if (newtop->bal > 0) --sp->bal;
+ else if (newtop->bal < 0) ++right->bal;
+ newtop->bal = 0;
+ *spp = newtop;
+ }
+ }
+ }
+
+ return ap;
+}
+
+#endif /* FREETYPE || PS */
+
+
/* set globals.dvi_name, globals.dvi_file.dirname and globals.dvi_file.dirlen */
void
set_dvi_name_expand(const char *new_filename)