Logo Search packages:      
Sourcecode: rapple version File versions  Download package

registry.c

Go to the documentation of this file.
/*
   Name: $RCSfile: registry.c,v $
   Author: Alan Moran
   $Date: 2005/11/13 20:57:21 $
   $Revision: 1.2 $
   $Id: registry.c,v 1.2 2005/11/13 20:57:21 a_j_moran Exp $

   Legal Notice:

   This program is free software; you can redistribute it and/or
   modify it under the terms of the license contained in the
   COPYING file that comes with this distribution.

 */

/**
   @file

   @brief Implementation to support the web asset registry.

   The registry stores references to all web assets created during processing.
   At the start of the workflow the registry is initialised during which time
   entries are created.   Each processing phase has access to and can update
   entries in the registry.  At the end of processing the registry can be
   traversed (e.g., for audit purposes).

   Throughout the documentation the following definitions apply:
   
   - a key is a means of looking up and identifying items in the registry.  
   Typically a key is the filename of the asset (relative to the website base
   directory).

   - an item refers to a node in the registry which in turn is a structure 
   containing a key, a reference to a web asset structure and other information 
   related to the registry implementation itself (e.g., RB indicators etc.)

   For inexpensive inserts and quick search access the registry is implemented
   as a RB BST (using a standard BST structure to represent a 2-3-4 tree).
*/


#include "globals.h"

static rpl_reg_link registry;
static rpl_reg_link RPL_REG_NULL;
/* represents a null entry in the registry */
rpl_web_asset RPL_REG_WA_NULL;
static long unsigned rpl_reg_sz;

/**
   Creates a new registry entry that wraps the item to be stored along with
   some registry specific information.
 */
static rpl_reg_link
00055 rpl_reg_new(rpl_reg_item item, rpl_reg_link left, rpl_reg_link right, unsigned long int count, rpl_reg_color color)
{
      rpl_reg_link t_lnk;

      /* a node must either be red or black */
      assert((color == RPL_REG_RED) || (color == RPL_REG_BLACK));

      t_lnk = (rpl_reg_link)rpl_me_malloc(sizeof(* t_lnk));
      t_lnk->item = item;
      t_lnk->left= left;
      t_lnk->right = right;
      t_lnk->count = count;
      t_lnk->color = color;

      return t_lnk;
}

/**
   Checks to see if first string is less than second according to order
   defined by function.

   @param str1 first string.
   @param str2 second string.

   @return 1 if str1 is lexiographically strictly less than str2, otherwise 0 (e.g., NULL values)
 */
static int
00082 rpl_reg_less(rpl_reg_key str1, rpl_reg_key str2)
{
      /* strcmp is undefined if str1 or str2 is NULL, so if str1 or str2 is
         NULL then we must return 0 to indicate failure (see 7.6.5)
       */
      return ((str1 != NULL) && (str2 != NULL)) ? (strcmp(str1, str2) < 0) : 0;
}

/**
   Checks to see if first string is equal to the second according to order
   defined by function.

   @param str1 first string.
   @param str2 second string.

   @return 1 if str1 is lexiographically equal to str2, otherwise 0
 */
static int
00100 rpl_reg_equal(rpl_reg_key str1, rpl_reg_key str2)
{
      /* see note in rpl_reg_less */
      return ((str1 != NULL) && (str2 != NULL)) ? (strcmp(str1, str2) == 0) : 0;
}

/**
   Extract key belonging to item (currently implemented as the concatentation of
   the relative directory, the separator "/" and the filename.

   @param item the item to be keyed.

   @return the (unique) registry key.
 */
static rpl_reg_key
00115 rpl_reg_get_key(rpl_reg_item item)
{
      /* item is implemented as a pointer to type rpl_webasset */
      return rpl_wa_get_key(*item);
}

/**
   Right rotation of registry node.  Rotations are primitive operations on BSTs that 
   preserve their characteristic property. 

   @param link pointer to node on which the rotation is to be performed.

   @return pointer to final position of rotated node.
 */
static rpl_reg_link
00130 rpl_reg_rot_r(rpl_reg_link link)
{
      rpl_reg_link t_lnk;

      t_lnk = link->left;
      link->left = t_lnk->right;
      t_lnk->right = link;

      return t_lnk;     
}

/**
   Left rotation of registry node.  Rotations are primitive operations on BSTs that 
   preserve their characteristic property. 

   @param link pointer to node on which the rotation is to be performed.

   @return pointer to final position of rotated node.
 */
static rpl_reg_link
00150 rpl_reg_rot_l(rpl_reg_link link)
{
      rpl_reg_link t_lnk;

      t_lnk = link->right;
      link->right = t_lnk->left;
      t_lnk->left = link;

      return t_lnk;
}

/**
   Perform local insertions required to insert an item into the registry.  This
   (recursive) function is called by the rpl_reg_insert function which starts
   the insertion from the registry root.

   @param link pointer to the (local) insert item.
   @param item the item to be inserted into the registry.
   @param type indicator of whether this is a red or black link.

   @return
 */
static rpl_reg_link
00173 rpl_reg_insert_r(rpl_reg_link link, rpl_reg_item item, rpl_reg_color color)
{
      rpl_reg_key item_key; 

      item_key = rpl_reg_get_key(item);
      if(link == RPL_REG_NULL)
            return rpl_reg_new(item, RPL_REG_NULL, RPL_REG_NULL, 1, RPL_REG_RED);
      if((link->left->color == RPL_REG_RED) && (link->right->color == RPL_REG_RED))
      {
            link->color = RPL_REG_RED;
            link->left->color = RPL_REG_BLACK;
            link->right->color = RPL_REG_BLACK;
      }
      if(rpl_reg_less(item_key, rpl_reg_get_key(link->item)))
      {
            link->left = rpl_reg_insert_r(link->left, item, RPL_REG_BLACK);
            if((link->color == RPL_REG_RED) 
                        && (link->left->color == RPL_REG_RED) 
                              && (color == RPL_REG_RED))
            {
                  link = rpl_reg_rot_r(link);
            }
            if((link->left->color == RPL_REG_RED) && (link->left->left->color == RPL_REG_RED))
            {
                  link = rpl_reg_rot_r(link);
                  link->color = RPL_REG_BLACK;
                  link->right->color = RPL_REG_RED;
                  
            }
      } else {
            link->right = rpl_reg_insert_r(link->right, item, RPL_REG_RED);
            if((link->color == RPL_REG_RED) 
                        && (link->right->color == RPL_REG_RED) 
                              && (color == RPL_REG_BLACK))
            {
                  link = rpl_reg_rot_l(link);
            }
            if((link->right->color == RPL_REG_RED) && (link->right->right->color == RPL_REG_RED))
            {
                  link = rpl_reg_rot_l(link);
                  link->color = RPL_REG_BLACK;
                  link->left->color = RPL_REG_RED;
            }
      }
      /* fixN(link) ?? */
      return link;
}

/**
   Performs recusrive search of the registry looking for the first key that matches
   the key parameter.  This function is invoked by rpl_reg_search which commences
   the search from the registry root.

   @param link the node from which to base the search.
   @param key the key to match nodes against. 
 */
static rpl_reg_item
00230 rpl_reg_search_r(rpl_reg_link link, rpl_reg_key key)
{
      rpl_reg_key t_key;

      assert(key != NULL);

      t_key = rpl_reg_get_key(link->item);
      if(link == RPL_REG_NULL)
            return &RPL_REG_WA_NULL;
      if(rpl_reg_equal(key, t_key))
            return link->item;
      if(rpl_reg_less(key, t_key))
            return rpl_reg_search_r(link->left, key);
      else
            return rpl_reg_search_r(link->right, key);
}


/**
   Performs local traversal of the registry in key order redefined by rpl_reg_less. 
   Invoked by rpl_reg_traverse which starts the traveral at the registry root and
   passes the function to be applied to each item.

   @param fn a visitation function that satisfies the registry traversal prototype.
 */
static void
00256 rpl_reg_traverse_r(rpl_reg_link link, rpl_reg_tr_fp fn)
{
      if(link == RPL_REG_NULL)
            return;
      rpl_reg_traverse_r(link->left, fn);
      fn(link->item);
      rpl_reg_traverse_r(link->right, fn);
}

/**
   Initialises the registry. 
 */
void
00269 rpl_reg_init()
{
    rpl_reg_sz = 0;
      rpl_wa_init(&RPL_REG_WA_NULL);
      registry = (RPL_REG_NULL = rpl_reg_new(&RPL_REG_WA_NULL,NULL,NULL,0, RPL_REG_BLACK));
}

rpl_str_t
rpl_reg_create_key(rpl_str_t rel_dir, rpl_str_t file)
{
    rpl_str_t key;

      key = (rpl_str_t)rpl_me_malloc(strlen(rel_dir) + strlen(file) + 2);
      if(strlen(rel_dir) > 0)
      {
            sprintf(key, "%s/%s", rel_dir, file);
      } else {
            strcpy(key, file);
      }

      return key;
}

/**
   Insert an item into the registry. 

   @param item the item to be inserted into the registry.
 */
void
00298 rpl_reg_insert(rpl_reg_item item)
{
      registry = rpl_reg_insert_r(registry, item, RPL_REG_BLACK);
      registry->color = RPL_REG_BLACK;
      rpl_reg_sz++;
}

/**
   Search the registry for an entry matching the key.

   @param key the key to be matched against the nodes.
   
   @return pointer to the web asset corresponding to the key, otherwise 
 */
rpl_reg_item
00313 rpl_reg_search(rpl_reg_key key)
{
      return rpl_reg_search_r(registry, key);
}


/**
  Traverse the registry and apply the function fn to each item visited.

  @param fn a visitation function that satisfies the registry traversal prototype.
*/
void
00325 rpl_reg_traverse(rpl_reg_tr_fp fn)
{
      assert(fn != NULL);

      rpl_reg_traverse_r(registry, fn);
}

/**
   Reports on the contents of the registry (used for debugging).  Invoked by
   the registry walker rpl_reg_traverse.

   @param item the item to be reported.
 */
void 
00339 rpl_reg_report(rpl_reg_item item)
{
      printf("-\n");
      printf("key:          %s\n", rpl_wa_get_key(*item));
      printf("filename:     %s\n", rpl_wa_get_filename(*item));
      printf("relative dir: %s\n", rpl_wa_get_rel_dir(*item));
      printf("mime type:    %s\n", rpl_wa_get_mime_type(*item));
      printf("tidy status:  %s\n", rpl_wa_get_tidy_stat_desc(*item));
      printf("xslt status:  %s\n", rpl_wa_get_tmpl_stat_desc(*item));
}

/**
   Counts the number of entries in the registry
 */
unsigned long 
00354 rpl_reg_count()
{
      /* registry maintains an eager count implementation */
      return rpl_reg_sz;
}





Generated by  Doxygen 1.6.0   Back to index