Sun, 16 Mar 2003 13:58:26 +0000
spec files are now called control files.
1 /*
2 * tumble: build a PDF file from image files
3 *
4 * PDF routines
5 * $Id: pdf_name_tree.c,v 1.10 2003/03/14 00:24:37 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 struct pdf_name_tree *pdf_new_name_tree (pdf_file_handle pdf_file,
41 bool number_tree)
42 {
43 struct pdf_name_tree *tree;
44 struct pdf_name_tree_node *root;
46 root = pdf_calloc (1, sizeof (struct pdf_name_tree_node));
47 tree = pdf_calloc (1, sizeof (struct pdf_name_tree));
49 tree->pdf_file = pdf_file;
50 tree->root = root;
51 tree->number_tree = number_tree;
53 root->parent = NULL;
54 root->leaf = 1;
56 tree->next = pdf_file->name_tree_list;
57 pdf_file->name_tree_list = tree;
59 return (tree);
60 }
63 static void pdf_split_name_tree_node (struct pdf_name_tree *tree,
64 struct pdf_name_tree_node *node)
65 {
66 struct pdf_name_tree_node *parent;
67 struct pdf_name_tree_node *new_node;
68 int i, j;
70 parent = node->parent;
71 if (! parent)
72 {
73 /* create new root above current root */
74 struct pdf_name_tree_node *new_root_node;
76 new_root_node = pdf_calloc (1, sizeof (struct pdf_name_tree_node));
78 new_root_node->parent = NULL;
79 new_root_node->leaf = 0;
81 new_root_node->count = 1;
82 new_root_node->kids [0] = node;
84 new_root_node->min_key = node->min_key;
85 new_root_node->max_key = node->max_key;
87 parent = new_root_node;
88 node->parent = new_root_node;
89 tree->root = new_root_node;
90 }
92 if (parent->count == MAX_NAME_TREE_NODE_ENTRIES)
93 {
94 pdf_split_name_tree_node (tree, parent);
95 parent = node->parent;
96 }
98 new_node = pdf_calloc (1, sizeof (struct pdf_name_tree_node));
99 new_node->parent = parent;
100 new_node->leaf = node->leaf;
102 /* move half the node's entries into the new node */
103 i = node->count / 2;
104 j = node->count - i;
106 memcpy (& new_node->kids [0],
107 & node->kids [i],
108 j * sizeof (struct pdf_name_tree_node *));
109 memcpy (& new_node->keys [0],
110 & node->keys [i],
111 j * sizeof (struct pdf_obj *));
112 memcpy (& new_node->values [0],
113 & node->values [i],
114 j * sizeof (struct pdf_obj *));
116 node->count = i;
117 new_node->count = j;
119 if (! new_node->leaf)
120 for (i = 0; i < j; i++)
121 new_node->kids [i]->parent = new_node;
123 /* set max_key of the old node */
124 if (node->leaf)
125 node->max_key = node->keys [node->count - 1];
126 else
127 node->max_key = node->kids [node->count - 1]->max_key;
129 /* set min_key and max_key in the new node */
130 if (new_node->leaf)
131 {
132 new_node->min_key = new_node->keys [0];
133 new_node->max_key = new_node->keys [new_node->count - 1];
134 }
135 else
136 {
137 new_node->min_key = new_node->kids [0]->min_key;
138 new_node->max_key = new_node->kids [new_node->count - 1]->max_key;
139 }
141 /* insert new node in parent's kids array */
142 /* find entry of old node */
143 for (i = 0; i < parent->count; i++)
144 if (parent->kids [i] == node)
145 break;
147 /* it had better have been there! */
148 pdf_assert (i < parent->count);
150 /* the new node goes in the slot to the right of the old node */
151 i++;
153 /* move other entries right one position */
154 if (i != parent->count)
155 {
156 memmove (& parent->kids [i+1],
157 & parent->kids [i],
158 (parent->count - i) * sizeof (struct pdf_name_tree_node *));
159 }
161 parent->kids [i] = new_node;
162 parent->count++;
163 }
166 static void pdf_add_tree_element (struct pdf_name_tree *tree,
167 struct pdf_obj *key,
168 struct pdf_obj *val)
169 {
170 struct pdf_name_tree_node *node;
171 int i;
173 /* find node which should contain element */
174 node = tree->root;
175 while (! node->leaf)
176 {
177 for (i = 0; i < (node->count - 1); i++)
178 if (pdf_compare_obj (key, node->kids [i + 1]->min_key) < 0)
179 break;
180 node = node->kids [i];
181 }
183 /* if node is full, split, recursing to root if necessary */
184 if (node->count == MAX_NAME_TREE_NODE_ENTRIES)
185 {
186 pdf_split_name_tree_node (tree, node);
187 pdf_add_tree_element (tree, key, val);
188 return;
189 }
191 /* figure out in which slot to insert it */
192 for (i = 0; i < node->count; i++)
193 if (pdf_compare_obj (key, node->keys [i]) < 0)
194 break;
196 /* move other entries right one position */
197 if (i != node->count)
198 {
199 memmove (& node->keys [i+1],
200 & node->keys [i],
201 (node->count - i) * sizeof (struct pdf_obj *));
202 memmove (& node->values [i+1],
203 & node->values [i],
204 (node->count - i) * sizeof (struct pdf_obj *));
205 }
207 node->keys [i] = key;
208 node->values [i] = val;
210 node->count++;
212 /* update limits, recursing upwards if necessary */
213 if (i == 0)
214 {
215 node->min_key = key;
216 while (node->parent && (node->parent->kids [0] == node))
217 {
218 node = node->parent;
219 node->min_key = key;
220 }
221 }
222 if (i == (node->count - 1))
223 {
224 node->max_key = key;
225 while (node->parent && (node->parent->kids [node->parent->count - 1] == node))
226 {
227 node = node->parent;
228 node->max_key = key;
229 }
230 }
231 }
234 void pdf_add_name_tree_element (struct pdf_name_tree *tree,
235 char *key,
236 struct pdf_obj *val)
237 {
238 struct pdf_obj *key_obj = pdf_new_string (key);
239 pdf_add_tree_element (tree, key_obj, val);
240 }
243 void pdf_add_number_tree_element (struct pdf_name_tree *tree,
244 long key,
245 struct pdf_obj *val)
246 {
247 struct pdf_obj *key_obj = pdf_new_integer (key);
248 pdf_add_tree_element (tree, key_obj, val);
249 }
252 static void pdf_finalize_name_tree_node (struct pdf_name_tree *tree,
253 struct pdf_name_tree_node *node)
254 {
255 int i;
257 node->dict = pdf_new_ind_ref (tree->pdf_file, pdf_new_obj (PT_DICTIONARY));
259 if (node->leaf)
260 {
261 /* write Names or Nums array */
262 struct pdf_obj *names = pdf_new_obj (PT_ARRAY);
263 for (i = 0; i < node->count; i++)
264 {
265 pdf_add_array_elem (names, node->keys [i]);
266 pdf_add_array_elem (names, node->values [i]);
267 }
268 pdf_set_dict_entry (node->dict,
269 tree->number_tree ? "Nums" : "Names",
270 names);
271 }
272 else
273 {
274 /* finalize the children first so that their dict ind ref is
275 available */
276 struct pdf_obj *kids;
278 for (i = 0; i < node->count; i++)
279 pdf_finalize_name_tree_node (tree, node->kids [i]);
281 /* write Kids array */
282 kids = pdf_new_obj (PT_ARRAY);
283 for (i = 0; i < node->count; i++)
284 pdf_add_array_elem (kids, node->kids [i]->dict);
285 pdf_set_dict_entry (node->dict, "Kids", kids);
286 }
288 if (node->parent)
289 {
290 /* write Limits array */
291 struct pdf_obj *limits = pdf_new_obj (PT_ARRAY);
292 pdf_add_array_elem (limits, node->min_key);
293 pdf_add_array_elem (limits, node->max_key);
294 pdf_set_dict_entry (node->dict, "Limits", limits);
295 }
296 }
299 void pdf_finalize_name_trees (pdf_file_handle pdf_file)
300 {
301 struct pdf_name_tree *tree;
303 for (tree = pdf_file->name_tree_list; tree; tree = tree->next)
304 pdf_finalize_name_tree_node (tree, tree->root);
305 }