Sat, 08 Mar 2003 07:45:46 +0000
more code for pdf_split_name_tree_node().
pdf_name_tree.c | file | annotate | diff | revisions |
1.1 --- a/pdf_name_tree.c Sat Mar 08 07:23:49 2003 +0000 1.2 +++ b/pdf_name_tree.c Sat Mar 08 07:45:46 2003 +0000 1.3 @@ -4,7 +4,7 @@ 1.4 * will be compressed using ITU-T T.6 (G4) fax encoding. 1.5 * 1.6 * PDF routines 1.7 - * $Id: pdf_name_tree.c,v 1.4 2003/03/07 22:52:09 eric Exp $ 1.8 + * $Id: pdf_name_tree.c,v 1.5 2003/03/07 23:45:46 eric Exp $ 1.9 * Copyright 2003 Eric Smith <eric@brouhaha.com> 1.10 * 1.11 * This program is free software; you can redistribute it and/or modify 1.12 @@ -90,9 +90,12 @@ 1.13 static void pdf_split_name_tree_node (struct pdf_name_tree *tree, 1.14 struct pdf_name_tree_node *node) 1.15 { 1.16 + struct pdf_name_tree_node *parent; 1.17 struct pdf_name_tree_node *new_node; 1.18 + int i, j; 1.19 1.20 - if (node == tree->root) 1.21 + parent = node->parent; 1.22 + if (! parent) 1.23 { 1.24 /* create new root above current root */ 1.25 struct pdf_name_tree_node *new_root_node; 1.26 @@ -108,15 +111,71 @@ 1.27 new_root_node->min_key = node->min_key; 1.28 new_root_node->max_key = node->max_key; 1.29 1.30 + parent = new_root_node; 1.31 node->parent = new_root_node; 1.32 tree->root = new_root_node; 1.33 } 1.34 1.35 new_node = pdf_calloc (1, sizeof (struct pdf_name_tree_node)); 1.36 - new_node->parent = node->parent; 1.37 + new_node->parent = parent; 1.38 new_node->leaf = node->leaf; 1.39 1.40 - /* $$$ insert new node in parent's kids array */ 1.41 + /* move half the node's entries into the new node */ 1.42 + i = node->count / 2; 1.43 + j = node->count - i; 1.44 + 1.45 + memcpy (& new_node->kids [0], 1.46 + & node->kids [i], 1.47 + j * sizeof (struct pdf_name_tree_node *)); 1.48 + memcpy (& new_node->keys [0], 1.49 + & node->keys [i], 1.50 + j * sizeof (struct pdf_obj *)); 1.51 + memcpy (& new_node->values [0], 1.52 + & node->values [i], 1.53 + j * sizeof (struct pdf_obj *)); 1.54 + node->count = i; 1.55 + new_node->count = j; 1.56 + 1.57 + /* set max_key of the old node */ 1.58 + if (node->leaf) 1.59 + node->max_key = node->keys [node->count - 1]; 1.60 + else 1.61 + node->max_key = node->kids [node->count - 1]->max_key; 1.62 + 1.63 + /* set min_key and max_key in the new node */ 1.64 + if (new_node->leaf) 1.65 + { 1.66 + new_node->min_key = new_node->keys [0]; 1.67 + new_node->max_key = new_node->keys [new_node->count - 1]; 1.68 + } 1.69 + else 1.70 + { 1.71 + new_node->min_key = new_node->kids [0]->min_key; 1.72 + new_node->max_key = new_node->kids [new_node->count - 1]->max_key; 1.73 + } 1.74 + 1.75 + /* insert new node in parent's kids array */ 1.76 + /* find entry of old node */ 1.77 + for (i = 0; i < parent->count; i++) 1.78 + if (parent->kids [i] == node) 1.79 + break; 1.80 + 1.81 + /* it had better have been there! */ 1.82 + pdf_assert (i < parent->count); 1.83 + 1.84 + /* the new node goes in the slot to the right of the old node */ 1.85 + i++; 1.86 + 1.87 + /* move other entries right one position */ 1.88 + if (i != node->count) 1.89 + { 1.90 + memmove (& parent->kids [i+1], 1.91 + & parent->kids [i], 1.92 + (parent->count - i) * sizeof (struct pdf_name_tree_node *)); 1.93 + } 1.94 + 1.95 + parent->kids [i] = new_node; 1.96 + parent->count++; 1.97 } 1.98 1.99