1% pdfpagetree.w 2% 3% Copyright 2006-2011 Taco Hoekwater <taco@@luatex.org> 4% 5% This file is part of LuaTeX. 6% 7% LuaTeX is free software; you can redistribute it and/or modify it under 8% the terms of the GNU General Public License as published by the Free 9% Software Foundation; either version 2 of the License, or (at your 10% option) any later version. 11% 12% LuaTeX is distributed in the hope that it will be useful, but WITHOUT 13% ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 14% FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public 15% License for more details. 16% 17% You should have received a copy of the GNU General Public License along 18% with LuaTeX; if not, see <http://www.gnu.org/licenses/>. 19 20@ @c 21 22 23#include "ptexlib.h" 24 25@* Page diversions. 26 27@ @c 28#ifdef DEBUG 29# define PAGES_TREE_KIDSMAX 3 30#else 31# define PAGES_TREE_KIDSMAX 10 32#endif 33 34static struct avl_table *divert_list_tree = NULL; 35 36typedef struct pages_entry_ { 37 int objnum; /* object number of this /Pages object */ 38 int number_of_pages; /* total number of all pages below */ 39 int number_of_kids; /* number of direct kid objects */ 40 int kids[PAGES_TREE_KIDSMAX]; /* array of kid object numbers */ 41 struct pages_entry_ *next; 42} pages_entry; 43 44typedef struct divert_list_entry_ { 45 int divnum; 46 pages_entry *first; 47 pages_entry *last; 48} divert_list_entry; 49 50static int comp_divert_list_entry(const void *pa, const void *pb, void *p) 51{ 52 (void) p; 53 if (((const divert_list_entry *) pa)->divnum > 54 ((const divert_list_entry *) pb)->divnum) 55 return 1; 56 if (((const divert_list_entry *) pa)->divnum < 57 ((const divert_list_entry *) pb)->divnum) 58 return -1; 59 return 0; 60} 61 62@ @c 63static pages_entry *new_pages_entry(PDF pdf) 64{ 65 pages_entry *p; 66 int i; 67 p = xtalloc(1, pages_entry); 68 p->number_of_pages = p->number_of_kids = 0; 69 for (i = 0; i < PAGES_TREE_KIDSMAX; i++) 70 p->kids[i] = 0; 71 p->next = NULL; 72 p->objnum = pdf_create_obj(pdf, obj_type_pages, 0); 73 return p; 74} 75 76@ @c 77static divert_list_entry *new_divert_list_entry(void) 78{ 79 divert_list_entry *d; 80 d = xtalloc(1, divert_list_entry); 81 d->first = d->last = NULL; 82 return d; 83} 84 85@ @c 86static void ensure_list_tree(void) 87{ 88 if (divert_list_tree == NULL) { 89 divert_list_tree = 90 avl_create(comp_divert_list_entry, NULL, &avl_xallocator); 91 assert(divert_list_tree != NULL); 92 } 93} 94 95@ @c 96static divert_list_entry *get_divert_list(int divnum) 97{ 98 divert_list_entry *d, tmp; 99 void **aa; 100 tmp.divnum = divnum; 101 d = (divert_list_entry *) avl_find(divert_list_tree, &tmp); 102 if (d == NULL) { 103 d = new_divert_list_entry(); 104 d->divnum = divnum; 105 aa = avl_probe(divert_list_tree, d); 106 assert(aa != NULL); 107 } 108 return d; 109} 110 111@ |pdf_do_page_divert()| returns the current /Parent object number 112@c 113int pdf_do_page_divert(PDF pdf, int objnum, int divnum) 114{ 115 divert_list_entry *d; 116 pages_entry *p; 117#ifdef DEBUG 118 pages_entry *q; 119 struct avl_traverser t; 120 int i; 121#endif 122 /* initialize the tree */ 123 ensure_list_tree(); 124 /* make sure we have a list for this diversion */ 125 d = get_divert_list(divnum); 126 if (d->first == NULL || d->last->number_of_kids == PAGES_TREE_KIDSMAX) { 127 /* append a new |pages_entry| */ 128 p = new_pages_entry(pdf); 129 if (d->first == NULL) 130 d->first = p; 131 else 132 d->last->next = p; 133 d->last = p; 134 } 135 p = d->last; 136 p->kids[p->number_of_kids++] = objnum; 137 p->number_of_pages++; 138#ifdef DEBUG 139 printf("\n"); 140 avl_t_init(&t, divert_list_tree); 141 for (d = avl_t_first(&t, divert_list_tree); d != NULL; d = avl_t_next(&t)) { 142 printf("===== D-LIST %d: ", d->divnum); 143 for (q = d->first; q != NULL; q = q->next) { 144 printf("P=%d NK=%d (", q->objnum, q->number_of_kids); 145 for (i = 0; i < q->number_of_kids; i++) 146 printf("%d ", q->kids[i]); 147 printf(") "); 148 } 149 printf("\n"); 150 } 151 printf("\n"); 152#endif 153 return p->objnum; 154} 155 156@ @c 157static void movelist(divert_list_entry * d, divert_list_entry * dto) 158{ 159 if (d != NULL && d->first != NULL && d->divnum != dto->divnum) { /* no undivert of empty list or into self */ 160 if (dto->first == NULL) 161 dto->first = d->first; 162 else 163 dto->last->next = d->first; 164 dto->last = d->last; 165 d->first = d->last = NULL; /* one could as well remove this |divert_list_entry| */ 166 } 167} 168 169@ undivert from diversion |divnum| into diversion |curdivnum| 170@c 171void pdf_do_page_undivert(int divnum, int curdivnum) 172{ 173 divert_list_entry *d, *dto, tmp; 174 struct avl_traverser t; 175#ifdef DEBUG 176 pages_entry *p; 177 int i; 178#endif 179 /* initialize the tree */ 180 ensure_list_tree(); 181 /* find the diversion |curdivnum| list where diversion |divnum| should go */ 182 dto = get_divert_list(curdivnum); 183 if (divnum == 0) { /* 0 = special case: undivert {\it all\/} lists */ 184 avl_t_init(&t, divert_list_tree); 185 for (d = avl_t_first(&t, divert_list_tree); d != NULL; 186 d = avl_t_next(&t)) 187 movelist(d, dto); 188 } else { 189 tmp.divnum = divnum; 190 d = (divert_list_entry *) avl_find(divert_list_tree, &tmp); 191 movelist(d, dto); 192 } 193#ifdef DEBUG 194 printf("\n"); 195 avl_t_init(&t, divert_list_tree); 196 for (d = avl_t_first(&t, divert_list_tree); d != NULL; d = avl_t_next(&t)) { 197 printf("===== U-LIST %d: ", d->divnum); 198 for (p = d->first; p != NULL; p = p->next) { 199 printf("P=%d NK=%d (", p->objnum, p->number_of_kids); 200 for (i = 0; i < p->number_of_kids; i++) 201 printf("%d ", p->kids[i]); 202 printf(") "); 203 } 204 printf("\n"); 205 } 206 printf("\n"); 207#endif 208} 209 210@ write a /Pages object 211@c 212#define pdf_pages_attr equiv(pdf_pages_attr_loc) 213 214static void write_pages(PDF pdf, pages_entry * p, int parent) 215{ 216 int i; 217 assert(p != NULL); 218 pdf_begin_obj(pdf, p->objnum, OBJSTM_ALWAYS); 219 pdf_begin_dict(pdf); 220 pdf_dict_add_name(pdf, "Type", "Pages"); 221 if (parent == 0) { /* it's root */ 222 if (pdf_pages_attr != null) { 223 pdf_print_toks(pdf, pdf_pages_attr); 224 pdf_out(pdf, ' '); 225 } 226 print_pdf_table_string(pdf, "pagesattributes"); 227 pdf_out(pdf, ' '); 228 } else 229 pdf_dict_add_ref(pdf, "Parent", parent); 230 pdf_dict_add_int(pdf, "Count", (int) p->number_of_pages); 231 pdf_add_name(pdf, "Kids"); 232 pdf_begin_array(pdf); 233 for (i = 0; i < p->number_of_kids; i++) 234 pdf_add_ref(pdf, (int) p->kids[i]); 235 pdf_end_array(pdf); 236 pdf_end_dict(pdf); 237 pdf_end_obj(pdf); 238} 239 240@ loop over all /Pages objects, output them, create their parents, 241recursing bottom up, return the /Pages root object number 242@c 243static int output_pages_list(PDF pdf, pages_entry * pe) 244{ 245 pages_entry *p, *q, *r; 246 assert(pe != NULL); 247 if (pe->next == NULL) { /* everything fits into one |pages_entry| */ 248 write_pages(pdf, pe, 0); /* --> /Pages root found */ 249 return pe->objnum; 250 } 251 q = r = new_pages_entry(pdf); /* one level higher needed */ 252 for (p = pe; p != NULL; p = p->next) { 253 if (q->number_of_kids == PAGES_TREE_KIDSMAX) { 254 q->next = new_pages_entry(pdf); 255 q = q->next; 256 } 257 q->kids[q->number_of_kids++] = p->objnum; 258 q->number_of_pages += p->number_of_pages; 259 write_pages(pdf, p, q->objnum); 260 } 261 return output_pages_list(pdf, r); /* recurse through next higher level */ 262} 263 264@ @c 265int output_pages_tree(PDF pdf) 266{ 267 divert_list_entry *d; 268 pdf_do_page_undivert(0, 0); /* concatenate all diversions into diversion 0 */ 269 d = get_divert_list(0); /* get diversion 0 */ 270 return output_pages_list(pdf, d->first); 271} 272