Fri, 14 Mar 2003 07:08:52 +0000
bookmarks should only be created for first page in a group.
1 /*
2 * tumble: build a PDF file from image files
3 *
4 * PDF routines
5 * $Id: pdf_name_tree.c,v 1.9 2003/03/13 00:57:05 eric Exp $
6 * Copyright 2003 Eric Smith <eric@brouhaha.com>
7 *
8 * This program is free software; you can redistribute it and/or modify
9 * it under the terms of the GNU General Public License version 2 as
10 * published by the Free Software Foundation. Note that permission is
11 * not granted to redistribute this program under the terms of any
12 * other version of the General Public License.
13 *
14 * This program is distributed in the hope that it will be useful,
15 * but WITHOUT ANY WARRANTY; without even the implied warranty of
16 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 * GNU General Public License for more details.
18 *
19 * You should have received a copy of the GNU General Public License
20 * along with this program; if not, write to the Free Software
21 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111 USA
22 */
25 #include <stdbool.h>
26 #include <stdint.h>
27 #include <stdio.h>
28 #include <stdlib.h>
29 #include <string.h>
32 #include "bitblt.h"
33 #include "pdf.h"
34 #include "pdf_util.h"
35 #include "pdf_prim.h"
36 #include "pdf_private.h"
37 #include "pdf_name_tree.h"
40 #define MAX_NAME_TREE_NODE_ENTRIES 16
43 struct pdf_name_tree_node
44 {
45 struct pdf_obj *dict; /* indirect reference */
47 struct pdf_name_tree_node *parent; /* NULL for root */
48 bool leaf;
50 int count; /* how many kids or names/numbers are
51 attached to this node */
53 struct pdf_name_tree_node *kids [MAX_NAME_TREE_NODE_ENTRIES]; /* non-leaf only */
55 struct pdf_obj *min_key;
56 struct pdf_obj *max_key;
58 /* following fields valid in leaf nodes only: */
60 struct pdf_obj *keys [MAX_NAME_TREE_NODE_ENTRIES];
61 struct pdf_obj *values [MAX_NAME_TREE_NODE_ENTRIES];
62 };
65 struct pdf_name_tree *pdf_new_name_tree (pdf_file_handle pdf_file,
66 bool number_tree)
67 {
68 struct pdf_name_tree *tree;
69 struct pdf_name_tree_node *root;
71 root = pdf_calloc (1, sizeof (struct pdf_name_tree_node));
72 tree = pdf_calloc (1, sizeof (struct pdf_name_tree));
74 tree->pdf_file = pdf_file;
75 tree->root = root;
76 tree->number_tree = number_tree;
78 root->parent = NULL;
79 root->leaf = 1;
81 tree->next = pdf_file->name_tree_list;
82 pdf_file->name_tree_list = tree;
84 return (tree);
85 }
88 static void pdf_split_name_tree_node (struct pdf_name_tree *tree,
89 struct pdf_name_tree_node *node)
90 {
91 struct pdf_name_tree_node *parent;
92 struct pdf_name_tree_node *new_node;
93 int i, j;
95 parent = node->parent;
96 if (! parent)
97 {
98 /* create new root above current root */
99 struct pdf_name_tree_node *new_root_node;
101 new_root_node = pdf_calloc (1, sizeof (struct pdf_name_tree_node));
103 new_root_node->parent = NULL;
104 new_root_node->leaf = 0;
106 new_root_node->count = 1;
107 new_root_node->kids [0] = node;
109 new_root_node->min_key = node->min_key;
110 new_root_node->max_key = node->max_key;
112 parent = new_root_node;
113 node->parent = new_root_node;
114 tree->root = new_root_node;
115 }
117 if (parent->count == MAX_NAME_TREE_NODE_ENTRIES)
118 {
119 pdf_split_name_tree_node (tree, parent);
120 parent = node->parent;
121 }
123 new_node = pdf_calloc (1, sizeof (struct pdf_name_tree_node));
124 new_node->parent = parent;
125 new_node->leaf = node->leaf;
127 /* move half the node's entries into the new node */
128 i = node->count / 2;
129 j = node->count - i;
131 memcpy (& new_node->kids [0],
132 & node->kids [i],
133 j * sizeof (struct pdf_name_tree_node *));
134 memcpy (& new_node->keys [0],
135 & node->keys [i],
136 j * sizeof (struct pdf_obj *));
137 memcpy (& new_node->values [0],
138 & node->values [i],
139 j * sizeof (struct pdf_obj *));
141 node->count = i;
142 new_node->count = j;
144 if (! new_node->leaf)
145 for (i = 0; i < j; i++)
146 new_node->kids [i]->parent = new_node;
148 /* set max_key of the old node */
149 if (node->leaf)
150 node->max_key = node->keys [node->count - 1];
151 else
152 node->max_key = node->kids [node->count - 1]->max_key;
154 /* set min_key and max_key in the new node */
155 if (new_node->leaf)
156 {
157 new_node->min_key = new_node->keys [0];
158 new_node->max_key = new_node->keys [new_node->count - 1];
159 }
160 else
161 {
162 new_node->min_key = new_node->kids [0]->min_key;
163 new_node->max_key = new_node->kids [new_node->count - 1]->max_key;
164 }
166 /* insert new node in parent's kids array */
167 /* find entry of old node */
168 for (i = 0; i < parent->count; i++)
169 if (parent->kids [i] == node)
170 break;
172 /* it had better have been there! */
173 pdf_assert (i < parent->count);
175 /* the new node goes in the slot to the right of the old node */
176 i++;
178 /* move other entries right one position */
179 if (i != parent->count)
180 {
181 memmove (& parent->kids [i+1],
182 & parent->kids [i],
183 (parent->count - i) * sizeof (struct pdf_name_tree_node *));
184 }
186 parent->kids [i] = new_node;
187 parent->count++;
188 }
191 static void pdf_add_tree_element (struct pdf_name_tree *tree,
192 struct pdf_obj *key,
193 struct pdf_obj *val)
194 {
195 struct pdf_name_tree_node *node;
196 int i;
198 /* find node which should contain element */
199 node = tree->root;
200 while (! node->leaf)
201 {
202 for (i = 0; i < (node->count - 1); i++)
203 if (pdf_compare_obj (key, node->kids [i + 1]->min_key) < 0)
204 break;
205 node = node->kids [i];
206 }
208 /* if node is full, split, recursing to root if necessary */
209 if (node->count == MAX_NAME_TREE_NODE_ENTRIES)
210 {
211 pdf_split_name_tree_node (tree, node);
212 pdf_add_tree_element (tree, key, val);
213 return;
214 }
216 /* figure out in which slot to insert it */
217 for (i = 0; i < node->count; i++)
218 if (pdf_compare_obj (key, node->keys [i]) < 0)
219 break;
221 /* move other entries right one position */
222 if (i != node->count)
223 {
224 memmove (& node->keys [i+1],
225 & node->keys [i],
226 (node->count - i) * sizeof (struct pdf_obj *));
227 memmove (& node->values [i+1],
228 & node->values [i],
229 (node->count - i) * sizeof (struct pdf_obj *));
230 }
232 node->keys [i] = key;
233 node->values [i] = val;
235 node->count++;
237 /* update limits, recursing upwards if necessary */
238 if (i == 0)
239 {
240 node->min_key = key;
241 while (node->parent && (node->parent->kids [0] == node))
242 {
243 node = node->parent;
244 node->min_key = key;
245 }
246 }
247 if (i == (node->count - 1))
248 {
249 node->max_key = key;
250 while (node->parent && (node->parent->kids [node->parent->count - 1] == node))
251 {
252 node = node->parent;
253 node->max_key = key;
254 }
255 }
256 }
259 void pdf_add_name_tree_element (struct pdf_name_tree *tree,
260 char *key,
261 struct pdf_obj *val)
262 {
263 struct pdf_obj *key_obj = pdf_new_string (key);
264 pdf_add_tree_element (tree, key_obj, val);
265 }
268 void pdf_add_number_tree_element (struct pdf_name_tree *tree,
269 long key,
270 struct pdf_obj *val)
271 {
272 struct pdf_obj *key_obj = pdf_new_integer (key);
273 pdf_add_tree_element (tree, key_obj, val);
274 }
277 static void pdf_finalize_name_tree_node (struct pdf_name_tree *tree,
278 struct pdf_name_tree_node *node)
279 {
280 int i;
282 node->dict = pdf_new_ind_ref (tree->pdf_file, pdf_new_obj (PT_DICTIONARY));
284 if (node->leaf)
285 {
286 /* write Names or Nums array */
287 struct pdf_obj *names = pdf_new_obj (PT_ARRAY);
288 for (i = 0; i < node->count; i++)
289 {
290 pdf_add_array_elem (names, node->keys [i]);
291 pdf_add_array_elem (names, node->values [i]);
292 }
293 pdf_set_dict_entry (node->dict,
294 tree->number_tree ? "Nums" : "Names",
295 names);
296 }
297 else
298 {
299 /* finalize the children first so that their dict ind ref is
300 available */
301 struct pdf_obj *kids;
303 for (i = 0; i < node->count; i++)
304 pdf_finalize_name_tree_node (tree, node->kids [i]);
306 /* write Kids array */
307 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 }