Fri, 07 Mar 2003 11:28:45 +0000
more work on pdf_add_tree_element().
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.2 2003/03/07 03:28:45 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 return (tree);
84 }
87 static void pdf_split_name_tree_node (struct pdf_name_tree *tree,
88 struct pdf_name_tree_node *node)
89 {
90 struct pdf_name_tree_node *new_node;
92 if (node == tree->root)
93 {
94 /* create new root above current root */
95 struct pdf_name_tree_node *new_root_node;
97 new_root_node = pdf_calloc (1, sizeof (struct pdf_name_tree_node));
99 new_root_node->parent = NULL;
100 new_root_node->leaf = 0;
102 new_root_node->count = 1;
103 new_root_node->kids [0] = node;
105 new_root_node->min_key = node->min_key;
106 new_root_node->max_key = node->max_key;
108 node->parent = new_root_node;
109 tree->root = new_root_node;
110 }
112 new_node = pdf_calloc (1, sizeof (struct pdf_name_tree_node));
113 new_node->parent = node->parent;
114 new_node->leaf = node->leaf;
115 }
118 static void pdf_add_tree_element (struct pdf_name_tree *tree,
119 struct pdf_obj *key,
120 struct pdf_obj *val)
121 {
122 struct pdf_name_tree_node *node;
123 int i;
125 /* find node which should contain element */
126 node = tree->root;
127 while (! node->leaf)
128 {
129 for (i = 0; i < (node->count - 1); i++)
130 if (pdf_compare_obj (key, node->kids [i + 1]->min_key) < 0)
131 break;
132 node = node->kids [i];
133 }
135 /* if node is full, split, recursing to root if necessary */
136 if (node->count == MAX_NAME_TREE_NODE_ENTRIES)
137 {
138 pdf_split_name_tree_node (tree, node);
139 pdf_add_tree_element (tree, key, val);
140 return;
141 }
143 /* $$$ figure out in which slot to insert it */
145 /* update limits, recursing upwards if necessary */
146 if (i == 0)
147 {
148 node->min_key = key;
149 while (node->parent && (node->parent->kids [0] == node))
150 {
151 node = node->parent;
152 node->min_key = key;
153 }
154 }
155 else if (i == (node->count - 1))
156 {
157 node->max_key = key;
158 while (node->parent && (node->parent->kids [node->parent->count - 1] == node))
159 {
160 node = node->parent;
161 node->max_key = key;
162 }
163 }
165 }
168 void pdf_add_name_tree_element (struct pdf_name_tree *tree,
169 char *key,
170 struct pdf_obj *val)
171 {
172 struct pdf_obj *key_obj = pdf_new_string (key);
173 pdf_add_tree_element (tree, key_obj, val);
174 }
177 void pdf_add_number_tree_element (struct pdf_name_tree *tree,
178 long key,
179 struct pdf_obj *val)
180 {
181 struct pdf_obj *key_obj = pdf_new_integer (key);
182 pdf_add_tree_element (tree, key_obj, val);
183 }
186 static void pdf_finalize_name_tree_node (struct pdf_name_tree *tree,
187 struct pdf_name_tree_node *node)
188 {
189 int i;
191 node->dict = pdf_new_ind_ref (tree->pdf_file, pdf_new_obj (PT_DICTIONARY));
193 if (node->leaf)
194 {
195 /* write Names or Nums array */
196 struct pdf_obj *names = pdf_new_obj (PT_ARRAY);
197 for (i = 0; i < node->count; i++)
198 {
199 pdf_add_array_elem (names, node->keys [i]);
200 pdf_add_array_elem (names, node->values [i]);
201 }
202 pdf_set_dict_entry (node->dict,
203 tree->number_tree ? "Nums" : "Names",
204 names);
205 }
206 else
207 {
208 /* finalize the children first so that their dict ind ref is
209 available */
210 for (i = 0; i < node->count; i++)
211 pdf_finalize_name_tree_node (tree, node->kids [i]);
213 /* write Kids array */
214 struct pdf_obj *kids = pdf_new_obj (PT_ARRAY);
215 for (i = 0; i < node->count; i++)
216 pdf_add_array_elem (kids, node->kids [i]->dict);
217 pdf_set_dict_entry (node->dict, "Kids", kids);
218 }
220 if (! node->parent)
221 {
222 /* write Limits array */
223 struct pdf_obj *limits = pdf_new_obj (PT_ARRAY);
224 pdf_add_array_elem (limits, node->min_key);
225 pdf_add_array_elem (limits, node->max_key);
226 pdf_set_dict_entry (node->dict, "Limits", limits);
227 }
228 }
231 void pdf_finalize_name_tree (struct pdf_name_tree *tree)
232 {
233 pdf_finalize_name_tree_node (tree, tree->root);
234 }