Wed, 12 Mar 2003 08:38:04 +0000
updated copyright notice.
1 /*
2 * t2p: Create a PDF file from the contents of one or more TIFF
3 * bilevel image files. The images in the resulting PDF file
4 * will be compressed using ITU-T T.6 (G4) fax encoding.
5 *
6 * PDF routines
7 * $Id: pdf_name_tree.c,v 1.7 2003/03/08 01:31:23 eric Exp $
8 * Copyright 2003 Eric Smith <eric@brouhaha.com>
9 *
10 * This program is free software; you can redistribute it and/or modify
11 * it under the terms of the GNU General Public License version 2 as
12 * published by the Free Software Foundation. Note that permission is
13 * not granted to redistribute this program under the terms of any
14 * other version of the General Public License.
15 *
16 * This program is distributed in the hope that it will be useful,
17 * but WITHOUT ANY WARRANTY; without even the implied warranty of
18 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
19 * GNU General Public License for more details.
20 *
21 * You should have received a copy of the GNU General Public License
22 * along with this program; if not, write to the Free Software
23 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111 USA
24 */
27 #include <stdbool.h>
28 #include <stdint.h>
29 #include <stdio.h>
30 #include <stdlib.h>
31 #include <string.h>
34 #include "bitblt.h"
35 #include "pdf.h"
36 #include "pdf_util.h"
37 #include "pdf_prim.h"
38 #include "pdf_private.h"
39 #include "pdf_name_tree.h"
42 #define MAX_NAME_TREE_NODE_ENTRIES 16
45 struct pdf_name_tree_node
46 {
47 struct pdf_obj *dict; /* indirect reference */
49 struct pdf_name_tree_node *parent; /* NULL for root */
50 bool leaf;
52 int count; /* how many kids or names/numbers are
53 attached to this node */
55 struct pdf_name_tree_node *kids [MAX_NAME_TREE_NODE_ENTRIES]; /* non-leaf only */
57 struct pdf_obj *min_key;
58 struct pdf_obj *max_key;
60 /* following fields valid in leaf nodes only: */
62 struct pdf_obj *keys [MAX_NAME_TREE_NODE_ENTRIES];
63 struct pdf_obj *values [MAX_NAME_TREE_NODE_ENTRIES];
64 };
67 struct pdf_name_tree *pdf_new_name_tree (pdf_file_handle pdf_file,
68 bool number_tree)
69 {
70 struct pdf_name_tree *tree;
71 struct pdf_name_tree_node *root;
73 root = pdf_calloc (1, sizeof (struct pdf_name_tree_node));
74 tree = pdf_calloc (1, sizeof (struct pdf_name_tree));
76 tree->pdf_file = pdf_file;
77 tree->root = root;
78 tree->number_tree = number_tree;
80 root->parent = NULL;
81 root->leaf = 1;
83 tree->next = pdf_file->name_tree_list;
84 pdf_file->name_tree_list = tree;
86 return (tree);
87 }
90 static void pdf_split_name_tree_node (struct pdf_name_tree *tree,
91 struct pdf_name_tree_node *node)
92 {
93 struct pdf_name_tree_node *parent;
94 struct pdf_name_tree_node *new_node;
95 int i, j;
97 parent = node->parent;
98 if (! parent)
99 {
100 /* create new root above current root */
101 struct pdf_name_tree_node *new_root_node;
103 new_root_node = pdf_calloc (1, sizeof (struct pdf_name_tree_node));
105 new_root_node->parent = NULL;
106 new_root_node->leaf = 0;
108 new_root_node->count = 1;
109 new_root_node->kids [0] = node;
111 new_root_node->min_key = node->min_key;
112 new_root_node->max_key = node->max_key;
114 parent = new_root_node;
115 node->parent = new_root_node;
116 tree->root = new_root_node;
117 }
119 if (parent->count == MAX_NAME_TREE_NODE_ENTRIES)
120 {
121 pdf_split_name_tree_node (tree, parent);
122 parent = node->parent;
123 }
125 new_node = pdf_calloc (1, sizeof (struct pdf_name_tree_node));
126 new_node->parent = parent;
127 new_node->leaf = node->leaf;
129 /* move half the node's entries into the new node */
130 i = node->count / 2;
131 j = node->count - i;
133 memcpy (& new_node->kids [0],
134 & node->kids [i],
135 j * sizeof (struct pdf_name_tree_node *));
136 memcpy (& new_node->keys [0],
137 & node->keys [i],
138 j * sizeof (struct pdf_obj *));
139 memcpy (& new_node->values [0],
140 & node->values [i],
141 j * sizeof (struct pdf_obj *));
143 node->count = i;
144 new_node->count = j;
146 if (! new_node->leaf)
147 for (i = 0; i < j; i++)
148 new_node->kids [i]->parent = new_node;
150 /* set max_key of the old node */
151 if (node->leaf)
152 node->max_key = node->keys [node->count - 1];
153 else
154 node->max_key = node->kids [node->count - 1]->max_key;
156 /* set min_key and max_key in the new node */
157 if (new_node->leaf)
158 {
159 new_node->min_key = new_node->keys [0];
160 new_node->max_key = new_node->keys [new_node->count - 1];
161 }
162 else
163 {
164 new_node->min_key = new_node->kids [0]->min_key;
165 new_node->max_key = new_node->kids [new_node->count - 1]->max_key;
166 }
168 /* insert new node in parent's kids array */
169 /* find entry of old node */
170 for (i = 0; i < parent->count; i++)
171 if (parent->kids [i] == node)
172 break;
174 /* it had better have been there! */
175 pdf_assert (i < parent->count);
177 /* the new node goes in the slot to the right of the old node */
178 i++;
180 /* move other entries right one position */
181 if (i != parent->count)
182 {
183 memmove (& parent->kids [i+1],
184 & parent->kids [i],
185 (parent->count - i) * sizeof (struct pdf_name_tree_node *));
186 }
188 parent->kids [i] = new_node;
189 parent->count++;
190 }
193 static void pdf_add_tree_element (struct pdf_name_tree *tree,
194 struct pdf_obj *key,
195 struct pdf_obj *val)
196 {
197 struct pdf_name_tree_node *node;
198 int i;
200 /* find node which should contain element */
201 node = tree->root;
202 while (! node->leaf)
203 {
204 for (i = 0; i < (node->count - 1); i++)
205 if (pdf_compare_obj (key, node->kids [i + 1]->min_key) < 0)
206 break;
207 node = node->kids [i];
208 }
210 /* if node is full, split, recursing to root if necessary */
211 if (node->count == MAX_NAME_TREE_NODE_ENTRIES)
212 {
213 pdf_split_name_tree_node (tree, node);
214 pdf_add_tree_element (tree, key, val);
215 return;
216 }
218 /* figure out in which slot to insert it */
219 for (i = 0; i < node->count; i++)
220 if (pdf_compare_obj (key, node->keys [i]) < 0)
221 break;
223 /* move other entries right one position */
224 if (i != node->count)
225 {
226 memmove (& node->keys [i+1],
227 & node->keys [i],
228 (node->count - i) * sizeof (struct pdf_obj *));
229 memmove (& node->values [i+1],
230 & node->values [i],
231 (node->count - i) * sizeof (struct pdf_obj *));
232 }
234 node->keys [i] = key;
235 node->values [i] = val;
237 node->count++;
239 /* update limits, recursing upwards if necessary */
240 if (i == 0)
241 {
242 node->min_key = key;
243 while (node->parent && (node->parent->kids [0] == node))
244 {
245 node = node->parent;
246 node->min_key = key;
247 }
248 }
249 if (i == (node->count - 1))
250 {
251 node->max_key = key;
252 while (node->parent && (node->parent->kids [node->parent->count - 1] == node))
253 {
254 node = node->parent;
255 node->max_key = key;
256 }
257 }
258 }
261 void pdf_add_name_tree_element (struct pdf_name_tree *tree,
262 char *key,
263 struct pdf_obj *val)
264 {
265 struct pdf_obj *key_obj = pdf_new_string (key);
266 pdf_add_tree_element (tree, key_obj, val);
267 }
270 void pdf_add_number_tree_element (struct pdf_name_tree *tree,
271 long key,
272 struct pdf_obj *val)
273 {
274 struct pdf_obj *key_obj = pdf_new_integer (key);
275 pdf_add_tree_element (tree, key_obj, val);
276 }
279 static void pdf_finalize_name_tree_node (struct pdf_name_tree *tree,
280 struct pdf_name_tree_node *node)
281 {
282 int i;
284 node->dict = pdf_new_ind_ref (tree->pdf_file, pdf_new_obj (PT_DICTIONARY));
286 if (node->leaf)
287 {
288 /* write Names or Nums array */
289 struct pdf_obj *names = pdf_new_obj (PT_ARRAY);
290 for (i = 0; i < node->count; i++)
291 {
292 pdf_add_array_elem (names, node->keys [i]);
293 pdf_add_array_elem (names, node->values [i]);
294 }
295 pdf_set_dict_entry (node->dict,
296 tree->number_tree ? "Nums" : "Names",
297 names);
298 }
299 else
300 {
301 /* finalize the children first so that their dict ind ref is
302 available */
303 for (i = 0; i < node->count; i++)
304 pdf_finalize_name_tree_node (tree, node->kids [i]);
306 /* write Kids array */
307 struct pdf_obj *kids = pdf_new_obj (PT_ARRAY);
308 for (i = 0; i < node->count; i++)
309 pdf_add_array_elem (kids, node->kids [i]->dict);
310 pdf_set_dict_entry (node->dict, "Kids", kids);
311 }
313 if (node->parent)
314 {
315 /* write Limits array */
316 struct pdf_obj *limits = pdf_new_obj (PT_ARRAY);
317 pdf_add_array_elem (limits, node->min_key);
318 pdf_add_array_elem (limits, node->max_key);
319 pdf_set_dict_entry (node->dict, "Limits", limits);
320 }
321 }
324 void pdf_finalize_name_trees (pdf_file_handle pdf_file)
325 {
326 struct pdf_name_tree *tree;
328 for (tree = pdf_file->name_tree_list; tree; tree = tree->next)
329 pdf_finalize_name_tree_node (tree, tree->root);
330 }