1 /*
2 Copyright 2004-2014 Han The Thanh, <thanh@pdftex.org>
3
4 This file is free software; you can redistribute it and/or modify it
5 under the terms of the GNU General Public License as published by Free
6 Software Foundation; either version 2 of the License, or (at your option)
7 any later version.
8
9 This file is distributed in the hope that it will be useful, but WITHOUT
10 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 for more details.
13
14 You should have received a copy of the GNU General Public License along
15 with this program. If not, see <http://www.gnu.org/licenses/>.
16
17
18 */
19
20 #include "ptexlib.h"
21 #include "avl.h"
22
23 static struct avl_table *PdfObjTree[pdfobjtypemax + 1] =
24 { NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL };
25
26 /**********************************************************************/
27 /* memory management functions for AVL */
28
avl_xmalloc(struct libavl_allocator * allocator,size_t size)29 static void *avl_xmalloc(struct libavl_allocator *allocator, size_t size)
30 {
31 assert(allocator != NULL && size > 0);
32 return xmalloc(size);
33 }
34
avl_xfree(struct libavl_allocator * allocator,void * block)35 static void avl_xfree(struct libavl_allocator *allocator, void *block)
36 {
37 assert(allocator != NULL && block != NULL);
38 xfree(block);
39 }
40
41 struct libavl_allocator avl_xallocator = {
42 avl_xmalloc,
43 avl_xfree
44 };
45
46 /**********************************************************************/
47 /* general AVL comparison functions */
48
comp_int_entry(const void * pa,const void * pb,void * p)49 int comp_int_entry(const void *pa, const void *pb, void *p)
50 {
51 cmp_return(*(const int *) pa, *(const int *) pb);
52 return 0;
53 }
54
comp_string_entry(const void * pa,const void * pb,void * p)55 int comp_string_entry(const void *pa, const void *pb, void *p)
56 {
57 return strcmp((const char *) pa, (const char *) pb);
58 }
59
60 /**********************************************************************/
61 /* One AVL tree for each obj_type 0...pdfobjtypemax */
62
63
64 typedef struct oentry_ {
65 integer int0;
66 integer objptr;
67 } oentry;
68
69 /* AVL sort oentry into avl_table[] */
70
compare_info(const void * pa,const void * pb,void * param)71 static int compare_info(const void *pa, const void *pb, void *param)
72 {
73 integer a, b;
74 int as, ae, bs, be, al, bl;
75
76 a = ((const oentry *) pa)->int0;
77 b = ((const oentry *) pb)->int0;
78 if (a < 0 && b < 0) { /* string comparison */
79 as = strstart[-a];
80 ae = strstart[-a + 1]; /* start of next string in pool */
81 bs = strstart[-b];
82 be = strstart[-b + 1];
83 al = ae - as;
84 bl = be - bs;
85 if (al < bl) /* compare first by string length */
86 return -1;
87 if (al > bl)
88 return 1;
89 for (; as < ae; as++, bs++) {
90 if (strpool[as] < strpool[bs])
91 return -1;
92 if (strpool[as] > strpool[bs])
93 return 1;
94 }
95 } else { /* integer comparison */
96 if (a < b)
97 return -1;
98 if (a > b)
99 return 1;
100 }
101 return 0;
102 }
103
avlputobj(integer objptr,integer t)104 void avlputobj(integer objptr, integer t)
105 {
106 static void **pp;
107 static oentry *oe;
108
109 if (PdfObjTree[t] == NULL) {
110 PdfObjTree[t] = avl_create(compare_info, NULL, &avl_xallocator);
111 if (PdfObjTree[t] == NULL)
112 pdftex_fail("avlstuff.c: avl_create() PdfObjTree failed");
113 }
114 oe = xtalloc(1, oentry);
115 oe->int0 = objtab[objptr].int0;
116 oe->objptr = objptr; /* allows to relocate objtab */
117 pp = avl_probe(PdfObjTree[t], oe);
118 if (pp == NULL)
119 pdftex_fail("avlstuff.c: avl_probe() out of memory in insertion");
120 }
121
122
123 /* replacement for linear search pascal function "find_obj()" */
124
avlfindobj(integer t,integer i,integer byname)125 integer avlfindobj(integer t, integer i, integer byname)
126 {
127 static oentry *p;
128 static oentry tmp;
129
130 if (byname > 0)
131 tmp.int0 = -i;
132 else
133 tmp.int0 = i;
134 if (PdfObjTree[t] == NULL)
135 return 0;
136 p = (oentry *) avl_find(PdfObjTree[t], &tmp);
137 if (p == NULL)
138 return 0;
139 return p->objptr;
140 }
141
142 /**********************************************************************/
143
144 struct avl_table *mf_tree = NULL;
145
146 typedef struct {
147 char *tfm_name;
148 internalfontnumber fontnum;
149 } mf_entry;
150
151 /**********************************************************************/
152 /* cleaning up... */
153
154 #if 0 /* unused */
155 static void destroy_oentry(void *pa, void *pb)
156 {
157 oentry *p = (oentry *) pa;
158 xfree(p);
159 }
160
161 static void PdfObjTree_free(void)
162 {
163 int i;
164
165 for (i = 0; i <= pdfobjtypemax; i++) {
166 if (PdfObjTree[i] != NULL)
167 avl_destroy(PdfObjTree[i], destroy_oentry);
168 }
169 }
170 #endif
171
172 /**********************************************************************/
173