more code for pdf_split_name_tree_node().

Sat, 08 Mar 2003 07:45:46 +0000

author
eric
date
Sat, 08 Mar 2003 07:45:46 +0000
changeset 87
870a093b587c
parent 86
7de78f7789ef
child 88
a9991578aa3f

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