/*
 * Copyright (c) 2004 Apple Computer, Inc. All rights reserved.
 *
 * @APPLE_LICENSE_HEADER_START@
 * 
 * This file contains Original Code and/or Modifications of Original Code
 * as defined in and that are subject to the Apple Public Source License
 * Version 2.0 (the 'License'). You may not use this file except in
 * compliance with the License. Please obtain a copy of the License at
 * http://www.opensource.apple.com/apsl/ and read it before using this
 * file.
 * 
 * The Original Code and all software distributed under the License are
 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
 * Please see the License for the specific language governing rights and
 * limitations under the License.
 * 
 * @APPLE_LICENSE_HEADER_END@
 */

#include "webdavd.h"

#include <sys/syslog.h>
#include <sys/errno.h>
#include <stdlib.h>
#include <strings.h>
#include <stdio.h>
#include <time.h>
#include <unistd.h>
#include <pthread.h>

#include "webdav_cache.h"
#include "OpaqueIDs.h"

/*****************************************************************************/

static int open_cache_files = 0;

pthread_mutex_t g_node_cache_lock;

/*****************************************************************************/

/*
 * The root node_entry.
 * The rest of the node_entry entries will be in the tree below the root node_entry.
 */
struct node_entry *g_root_node;

/*
 * The deleted root node_entry.
 * When an open file is deleted (including when something is renamed over an
 * existing node), it will be removed from the main tree and inserted as a child
 * of this "fake" node_entry. URLs cannot be created for children of this node
 * (but they should never need to talk to the server anyway -- they are deleted)
 * Nodes are freed (using nodecache_free_nodes()) only when they are children of this node. 
 */
struct node_entry *g_deleted_root_node;

/*
 * The next fileid number to be assigned.
*/
u_int32_t g_next_fileid;

/*
 * The file_cache_head list.
 * Entries are stored in the order inserted into the list.
 */
struct node_head g_file_list;

/* static prototypes */

static int internal_add_attributes(
	struct node_entry *node,
	uid_t uid,
	struct stat *statp,
	char *appledoubleheader);
static int internal_remove_attributes(
	struct node_entry *node,
	int remove_appledoubleheader);
static int internal_node_appledoubleheader_valid(
	struct node_entry *node,
	uid_t uid);
static void invalidate_level(
	struct node_entry *dir_node);
static void internal_remove_file_cache(
	struct node_entry *node);
static int internal_add_file_cache(
	struct node_entry *node,
	int fd);
static int internal_get_node(
	struct node_entry *parent,
	size_t name_length,
	const char *name,
	int make_entry,
	int client_created,
	webdav_filetype_t node_type,
	struct node_entry **node);
static void internal_free_nodes(void);
static int internal_move_node(
	struct node_entry *node,
	struct node_entry *new_parent,
	size_t new_name_length,
	char *new_name);
static int delete_node_tree(
	struct node_entry *node,
	int recursive);
static int internal_invalidate_directory_node_time(
	struct node_entry *dir_node);
static int internal_delete_invalid_directory_nodes(
	struct node_entry *dir_node);
static int internal_get_path_from_node(
	struct node_entry *target_node,
	char **path);

static int init_node_cache_lock(void);
static void lock_node_cache(void);
static void unlock_node_cache(void);

/*****************************************************************************/

/* this adds or replaces attribute information to node */
static int internal_add_attributes(
	struct node_entry *node,		/* the node_entry to update or add attributes_entry to */
	uid_t uid,						/* the uid these attributes are valid for */
	struct stat *statp,				/* the stat buffer */
	char *appledoubleheader)	/* pointer appledoubleheader or NULL */
{
	int error;
	time_t current_time;
	
	error = 0;
	
	/* first, clear out any old attributes */
	(void)internal_remove_attributes(node, (appledoubleheader != NULL));
	
	current_time = time(NULL);
	require_action(current_time != -1, time, error = errno);
	
	/* add appledoubleheader first since it could fail */
	if ( appledoubleheader != NULL )
	{
		node->attr_appledoubleheader = malloc(APPLEDOUBLEHEADER_LENGTH);
		require_action(node->attr_appledoubleheader != NULL, malloc_attr_appledoubleheader, error = ENOMEM);
		
		memcpy(node->attr_appledoubleheader, appledoubleheader, APPLEDOUBLEHEADER_LENGTH);
		node->attr_appledoubleheader_time = current_time;
	}
	/* fill in the rest of the fields */
	node->attr_uid = uid;
	node->attr_time = current_time;
	memcpy(&(node->attr_stat), statp, sizeof(struct stat));
	
malloc_attr_appledoubleheader:
time:
	
	return ( error );
}

/*****************************************************************************/

int nodecache_add_attributes(
	struct node_entry *node,		/* the node_entry to update or add attributes_entry to */
	uid_t uid,						/* the uid these attributes are valid for */
	struct stat *statp,				/* the stat buffer */
	char *appledoubleheader)	/* pointer appledoubleheader or NULL */
{
	int error;

	lock_node_cache();

	error = internal_add_attributes(node, uid, statp, appledoubleheader);

	unlock_node_cache();
	
	return ( error );
}

/*****************************************************************************/

/* clear out the attribute fields and release any memory */
static int internal_remove_attributes(
	struct node_entry *node,
	int remove_appledoubleheader)
{
	node->attr_uid = 0;
	node->attr_time = 0;
	memset(&node->attr_stat, 0, sizeof(struct stat));
	if ( remove_appledoubleheader && (node->attr_appledoubleheader != NULL) )
	{
		free(node->attr_appledoubleheader);
		node->attr_appledoubleheader = NULL;
		node->attr_appledoubleheader_time = 0;
	}
	return ( 0 );
}

/*****************************************************************************/

int nodecache_remove_attributes(
	struct node_entry *node)	/* the node to remove attributes from */
{
	int error;

	lock_node_cache();

	error = internal_remove_attributes(node, TRUE);

	unlock_node_cache();

	return ( error );
}

/*****************************************************************************/

static int internal_node_appledoubleheader_valid(
	struct node_entry *node,
	uid_t uid)
{
	int result;

	result = ( (node->attr_appledoubleheader != NULL) && /* is there attr_appledoubleheader? */
			 (node->attr_appledoubleheader_time != 0) && /* 0 attr_appledoubleheader_time is invalid */
			 ((uid == node->attr_uid) || (0 == node->attr_uid)) && /* does this user or root have access to the cached attributes? */
			 (time(NULL) < (node->attr_appledoubleheader_time + FILE_VALIDATION_TIMEOUT)) ); /* don't cache them too long */

	return ( result );
}

/*****************************************************************************/

int node_appledoubleheader_valid(
	struct node_entry *node,
	uid_t uid)
{
	int result;

	lock_node_cache();

	result = internal_node_appledoubleheader_valid(node, uid);

	unlock_node_cache();

	return ( result );
}

/*****************************************************************************/

int node_attributes_valid(
	struct node_entry *node,
	uid_t uid)
{
	int result;

	lock_node_cache();

	result = ( (node->attr_time != 0) && /* 0 attr_time is invalid */
			 ((uid == node->attr_uid) || (0 == node->attr_uid)) && /* does this user or root have access to the cached attributes */
			 (time(NULL) < (node->attr_time + ATTRIBUTES_TIMEOUT_MAX)) ); /* don't cache them too long */

	unlock_node_cache();

	return ( result );

#if 0 /* FUTURE */	
	int result;
	
	/* are the cached attributes possibly valid and does this user or root have access to them? */
	if ( (node->attr_time != 0) && ((uid == node->attr_uid) || (0 == node->attr_uid)) )
	{
		/*
		 * Determine attribute_time_out. It will be something between
		 * ATTRIBUTES_TIMEOUT_MIN and ATTRIBUTES_TIMEOUT_MAX where recently
		 * modified files have a short timeout and files that haven't been
		 * modified in a long time have a long timeout. This is the same
		 * algorithm used by NFS (with different min and max values).
		 */
		time_t current_time;
		time_t attribute_time_out;
		
		current_time = time(NULL);
		attribute_time_out = (current_time - node->attr_stat.st_mtimespec.tv_sec) / 10;
		if (attribute_time_out < ATTRIBUTES_TIMEOUT_MIN)
		{
			attribute_time_out = ATTRIBUTES_TIMEOUT_MIN;
		}
		else if (attribute_time_out > ATTRIBUTES_TIMEOUT_MAX)
		{
			attribute_time_out = ATTRIBUTES_TIMEOUT_MAX;
		}
		/* has too much time passed? */
		result = ((current_time - node->attr_time) <= attribute_time_out);
	}
	else
	{
		result = FALSE;
	}
	return ( result );
#endif /* FUTURE */
}

/*****************************************************************************/

/* invalidate the node attribute and file cache caches for dir_node's children */
static void invalidate_level(struct node_entry *dir_node)
{
	struct node_entry *node;
	
	/* invalidate each child node */
	LIST_FOREACH(node, &(dir_node->children), entries)
	{
		node->attr_time = 0;
		node->file_validated_time = 0;
		/* invalidate this node's children (if any) */
		invalidate_level(node);
	}
}

/* filesystem_invalidate_caches will call this to do all the work */
void nodecache_invalidate_caches(void)
{
	struct node_entry *node;
	
	lock_node_cache();
	
	node = g_root_node;
	node->attr_time = 0;
	node->file_validated_time = 0;
	/* invalidate this node's children (if any) */
	invalidate_level(node);
	
	unlock_node_cache();
}

/*****************************************************************************/

#if 0

static int gtabs;

static void display_node_tree_level(struct node_entry *dir_node)
{
	struct node_entry *node;
	
	LIST_FOREACH(node, &(dir_node->children), entries)
	{
		++gtabs;
		syslog(LOG_ERR, "%*s%s: %ld %s, node ino %ld, attr ino %u", gtabs*3, "", node->name, (unsigned long)node, node->node_type == WEBDAV_DIR_TYPE ? "d" : "f", node->fileid, node->attr_stat.st_ino);
		display_node_tree_level(node);
		--gtabs;
	}
}

void nodecache_display_node_tree(void)
{
	struct node_entry *node;
	
	lock_node_cache();
	
	node = g_root_node;
	gtabs = 0;
	syslog(LOG_ERR, "%*s%s: %ld %s, node ino %ld, attr ino %u", gtabs*3, "", node->name, (unsigned long)node, node->node_type == WEBDAV_DIR_TYPE ? "d" : "f", node->fileid, node->attr_stat.st_ino);
	display_node_tree_level(node);
	syslog(LOG_ERR, "-----");
	
	unlock_node_cache();
}

void nodecache_display_file_cache(void)
{
	struct node_entry *node;
	unsigned long count;
	
	count = 0;
	
	lock_node_cache();

	LIST_FOREACH(node, &g_file_list, file_list)
	{
		++count;
		
		if ( !NODE_IS_DELETED(node) )
		{
			syslog(LOG_ERR, "fd: %d, ino %ld %s%s %s",
				node->file_fd,
				node->fileid,
				node->node_type == WEBDAV_DIR_TYPE ? "d" : "f",
				NODE_FILE_IS_OPEN(node) ? "+ " : "- ",
				node->name);
		}
		else
		{
			syslog(LOG_ERR, "fd: %d, ino %ld %s%s %s",
				node->file_fd,
				node->fileid,
				node->node_type == WEBDAV_DIR_TYPE ? "d" : "f",
				NODE_FILE_IS_OPEN(node) ? "+X" : "-X",
				node->name);
		}
	}
	syslog(LOG_ERR, "----- %ld -----", count);

	unlock_node_cache();
}

#endif

/*****************************************************************************/

static struct node_entry *g_next_file_cache_node = NULL;

struct node_entry *nodecache_get_next_file_cache_node(
	int get_first)					/* if true, return first file cache node; otherwise, the next one */
{
	struct node_entry *node;
	
	lock_node_cache();
	
	if ( get_first )
	{
		node = g_file_list.lh_first;
	}
	else
	{
		node = g_next_file_cache_node;
	}
	
	if ( node != NULL )
	{
		g_next_file_cache_node = node->file_list.le_next;
	}
	else
	{
		g_next_file_cache_node = NULL;
	}
	
	unlock_node_cache();
	
	return ( node );
}

/*****************************************************************************/

static int internal_add_file_cache(
	struct node_entry *node,		/* the node_entry to add a file_cache_entry to */
	int fd)							/* the file descriptor of the cache file */
{
	int error;
	
	error = 0;
	
	/* only add it if it's not already cached */
	require_quiet(!NODE_FILE_IS_CACHED(node), already_cached);
	
	while ( open_cache_files >= WEBDAV_MAX_OPEN_FILES )
	{
		struct node_entry *file_node;
		struct node_entry *victim_node;
		
		/* find oldest victim node */
		victim_node = NULL;
		LIST_FOREACH(file_node, &g_file_list, file_list)
		{
			if ( !NODE_FILE_IS_OPEN(file_node) )
			{
				victim_node = file_node;
			}
		}
		
		require_action(victim_node != NULL, too_many_files_open, error = ENFILE);

		internal_remove_file_cache(victim_node);
	}
	
	++open_cache_files;
	node->flags |= nodeInFileListMask;
	node->file_fd = fd;
	node->file_status = WEBDAV_DOWNLOAD_NEVER;
	node->file_validated_time = 0;
	node->file_inactive_time = 0;
	node->file_last_modified = -1;
	if ( node->file_entity_tag != NULL )
	{
		free(node->file_entity_tag);
		node->file_entity_tag = NULL;
	}
	node->file_locktoken_uid = 0;
	if ( node->file_locktoken != NULL )
	{
		free(node->file_locktoken);
		node->file_locktoken = NULL;
	}
	
	/* add it to the head of the g_file_active_list */
	LIST_INSERT_HEAD(&g_file_list, node, file_list);
	
too_many_files_open:
already_cached:
	
	return ( error );
}

/*****************************************************************************/

int nodecache_add_file_cache(
	struct node_entry *node,		/* the node_entry to add a file_cache_entry to */
	int fd)							/* the file descriptor of the cache file */
{
	int error;

	lock_node_cache();

	error = internal_add_file_cache(node, fd);

	unlock_node_cache();

	return ( error );
}

/*****************************************************************************/

static void internal_remove_file_cache(struct node_entry *node)
{
	if ( NODE_FILE_IS_CACHED(node) )
	{
		if (open_cache_files > 0)
		{
			--open_cache_files;
		}
		else
		{
			debug_string("internal_remove_file_cache: open_cache_files was zero");
		}
		node->flags &= ~nodeInFileListMask;
		close(node->file_fd);
		node->file_fd = -1;
		if ( node == g_next_file_cache_node )
		{
			g_next_file_cache_node = node->file_list.le_next;
		}
		/* remove from g_file_list */
		LIST_REMOVE(node, file_list);
		node->file_list.le_next = NULL;
		node->file_list.le_prev = NULL;
		node->file_status = WEBDAV_DOWNLOAD_NEVER;
		node->file_validated_time = 0;
		node->file_inactive_time = 0;
		node->file_last_modified = -1;
		if ( node->file_entity_tag != NULL )
		{
			free(node->file_entity_tag);
			node->file_entity_tag = NULL;
		}
		node->file_locktoken_uid = 0;
		if ( node->file_locktoken != NULL )
		{
			free(node->file_locktoken);
			node->file_locktoken = NULL;
		}
	}
}

/*****************************************************************************/

void nodecache_remove_file_cache(struct node_entry *node)
{
	lock_node_cache();
	
	internal_remove_file_cache(node);
	
	unlock_node_cache();
}

/*****************************************************************************/

/* called at mount time to initialize */
int nodecache_init(
	size_t name_length,				/* length of root node name */
	char *name,						/* the utf8 name of root node */
	struct node_entry **root_node)	/* the root node */
{
	int error;

	error = 0;
	
	g_next_fileid = WEBDAV_ROOTFILEID;
		
	/* allocate space for g_root_node and its name */
	g_root_node = calloc(1, sizeof(struct node_entry));
	require_action(g_root_node != NULL, calloc_g_root_node, error = ENOMEM);
	
	*root_node = g_root_node;
	g_root_node->name = malloc(name_length + 1);
	require_action(g_root_node->name != NULL, malloc_name, error = ENOMEM);
	
	/* initialize the node_entry */
	g_root_node->parent = NULL;
	LIST_INIT(&g_root_node->children);
	g_root_node->name_length = name_length;
	memcpy(g_root_node->name, name, name_length);
	g_root_node->name[name_length] = '\0';
	g_root_node->name_ref = CFStringCreateWithCStringNoCopy(kCFAllocatorDefault, g_root_node->name, kCFStringEncodingUTF8, kCFAllocatorNull);
	g_root_node->fileid = g_next_fileid++;
	g_root_node->node_type = WEBDAV_DIR_TYPE;
	g_root_node->node_time = time(NULL);
	error = AssignOpaqueID(g_root_node, &g_root_node->nodeid);
	require_noerr(error, AssignOpaqueID);

	/* attribute fields are already zeroed */
	/* file cache fields are already zeroed - set file_fd to indicate there is no cache file */
	g_root_node->file_fd = -1;
	
	/* allocate space for g_deleted_root_node and its empty name */
	g_deleted_root_node = calloc(1, sizeof(struct node_entry));
	require_action(g_root_node != NULL, calloc_g_deleted_root_node, error = ENOMEM);
	
	g_deleted_root_node->name = malloc(1);
	require_action(g_root_node->name != NULL, malloc_g_deleted_root_node_name, error = ENOMEM);
	
	/* initialize the node_entry */
	g_deleted_root_node->parent = NULL;
	LIST_INIT(&g_deleted_root_node->children);
	g_deleted_root_node->name_length = 0;
	g_deleted_root_node->name[0] = '\0';
	g_deleted_root_node->name_ref = CFStringCreateWithCStringNoCopy(kCFAllocatorDefault, g_deleted_root_node->name, kCFStringEncodingUTF8, kCFAllocatorNull);
	/* attribute fields are already zeroed */
	/* file cache fields are already zeroed - set file_fd to indicate there is no cache file */
	g_deleted_root_node->file_fd = -1;
	
	/* initialize g_file_list header */
	LIST_INIT(&g_file_list);

	error = init_node_cache_lock();

malloc_g_deleted_root_node_name:
calloc_g_deleted_root_node:
malloc_name:
AssignOpaqueID:
calloc_g_root_node:
	
	return ( error );
}

/*****************************************************************************/

/*
 * Finds a node by name in the parent node's children. If the node is
 * not found and make_entry is TRUE, then internal_get_node creates a new node.
 */
static int internal_get_node(
	struct node_entry *parent,		/* the parent node_entry */
	size_t name_length,				/* length of name */
	const char *name,				/* the utf8 name of the node */
	int make_entry,					/* TRUE if a new node_entry should be created if needed */
	int client_created,				/* TRUE if this client created the node (used in conjunction with make_entry */
	webdav_filetype_t node_type,	/* if make_entry is TRUE, the type of node to create */
	struct node_entry **node)		/* the found (or new) node_entry */
{
	struct node_entry *node_ptr;
	int error;
	
	node_ptr = NULL;
	error = 0;
	
	if ( name_length != 0 && name != NULL )
	{
		CFStringRef name_string;
		
		name_string = CFStringCreateWithBytes(kCFAllocatorDefault, (const UInt8 *)name, name_length, kCFStringEncodingUTF8, false);
		require_action(name_string != NULL, out, error = EINVAL);

		/* search for an existing node_entry */
		LIST_FOREACH(node_ptr, &(parent->children), entries)
		{
			if ( CFStringCompare(name_string, node_ptr->name_ref, kCFCompareNonliteral) == kCFCompareEqualTo )
			{
				break;
			}
		}
		
		CFRelease(name_string);
	}
	else
	{
		node_ptr = parent;
	}
	
	/* if we didn't find it and we're supposed to create it... */
	if ( node_ptr == NULL )
	{
		if ( make_entry )
		{
			/* allocate new node_entry */
			node_ptr = calloc(1, sizeof(struct node_entry));
			require_action(node_ptr != NULL, calloc_node_ptr, error = ENOMEM; webdav_kill(-1));
			
			/* allocate space for its name */
			node_ptr->name = malloc(name_length + 1);
			require_action(node_ptr->name != NULL, malloc_name, node_ptr = NULL; error = ENOMEM; webdav_kill(-1));
			
			/* initialize the node_entry */
			node_ptr->parent = parent;
			LIST_INIT(&node_ptr->children);
			node_ptr->name_length = name_length;
			memcpy(node_ptr->name, name, name_length);
			node_ptr->name[name_length] = '\0';
			node_ptr->name_ref = CFStringCreateWithCStringNoCopy(kCFAllocatorDefault, node_ptr->name, kCFStringEncodingUTF8, kCFAllocatorNull);
			node_ptr->fileid = g_next_fileid++;
			node_ptr->node_type = node_type;
			node_ptr->node_time = time(NULL);
			if ( client_created )
			{
				node_ptr->flags |= nodeRecentMask;
			}
			error = AssignOpaqueID(node_ptr, &node_ptr->nodeid);
			require_noerr_action(error, AssignOpaqueID, node_ptr = NULL; webdav_kill(-1));
			
			/* attribute fields are already zeroed */
			/* file cache fields are already zeroed - set file_fd to indicate there is no cache file */
			node_ptr->file_fd = -1;
			
			/* insert the node_entry into the parent's children list */
			LIST_INSERT_HEAD(&parent->children, node_ptr, entries);
		}
		else
		{
			error = ENOENT;
		}
	}
	else
	{
		/* update node_time of existing node */
		if ( make_entry )
		{
			node_ptr->node_time = time(NULL);
		}
		/* set or clear the recent flag */
		if ( client_created )
		{
			node_ptr->flags |= nodeRecentMask;
		}
		else
		{
			node_ptr->flags &= ~nodeRecentMask;
		}
	}
	
AssignOpaqueID:
malloc_name:
calloc_node_ptr:
out:

	/* return node_entry */
	if ( error == 0 )
	{
		*node = node_ptr;
	}
	else
	{
		*node = NULL;
	}
	
	return ( error );
}

/*****************************************************************************/

int nodecache_get_node(
	struct node_entry *parent,		/* the parent node_entry */
	size_t name_length,				/* length of name */
	const char *name,				/* the utf8 name of the node */
	int make_entry,					/* TRUE if a new node_entry should be created if needed*/
	int client_created,				/* TRUE if this client created the node (used in conjunction with make_entry */
	webdav_filetype_t node_type,	/* if make_entry is TRUE, the type of node to create */
	struct node_entry **node)		/* the found (or new) node */
{
	int error;

	lock_node_cache();
	
	error = internal_get_node(parent, name_length, name, make_entry, client_created, node_type, node);

	unlock_node_cache();

	return ( error );
}

/*****************************************************************************/

/*
 * internal_free_nodes
 * This function frees uncached nodes on the deleted list.
 */
static void internal_free_nodes(void)
{
	struct node_entry *node;

	node = g_deleted_root_node->children.lh_first;
	while ( node != NULL )
	{
		struct node_entry *next_node;

		next_node = node->entries.le_next;
		/* free this node ONLY if it's  NOT on the file list */
		if ( !NODE_FILE_IS_CACHED(node) )
		{
			/* remove the node_entry from the list it is in */
			LIST_REMOVE(node, entries);
			
			/* invalidate the nodeid */
			(void) DeleteOpaqueID(node->nodeid);
			node->nodeid = kInvalidOpaqueID;

			if ( node->file_entity_tag != NULL )
			{
				free(node->file_entity_tag);
				node->file_entity_tag = NULL;
			}
			node->file_locktoken_uid = 0;
			if ( node->file_locktoken != NULL )
			{
				free(node->file_locktoken);
				node->file_locktoken = NULL;
			}

			/* free memory used by the node */
			free(node->name);
			CFRelease(node->name_ref);
			(void) internal_remove_attributes(node, TRUE);

			free(node);
		}
		node = next_node;
	}
}

/*****************************************************************************/

void nodecache_free_nodes(void)
{
	lock_node_cache();

	internal_free_nodes();

	unlock_node_cache();
}

/*****************************************************************************/

static int internal_move_node(
	struct node_entry *node,		/* the node_entry to move */
	struct node_entry *new_parent,  /* the new parent node_entry */
	size_t new_name_length,			/* length of new_name or 0 if not renaming */
	char *new_name)					/* the utf8 new name of the node or NULL */
{
	int error;
	
	error = 0;
	
	/* new name? */
	if ( (new_name_length != 0) && (new_name != NULL) )
	{
		CFStringRef name_string;
		CFComparisonResult compare_result;
			
		name_string = CFStringCreateWithBytes(kCFAllocatorDefault, (const UInt8 *)new_name, new_name_length, kCFStringEncodingUTF8, false);
		compare_result = CFStringCompare(name_string, node->name_ref, kCFCompareNonliteral);
		CFRelease(name_string);
		
		/* did the name change? */
		if ( compare_result != kCFCompareEqualTo )
		{
			char *name;
			
			/* allocate space for new name */
			name = malloc(new_name_length + 1);
			require_action(name != NULL, malloc_name, error = errno; webdav_kill(-1));
			
			free(node->name);
			CFRelease(node->name_ref);
			node->name = name;
			memcpy(node->name, new_name, new_name_length);
			node->name[new_name_length] = '\0';
			node->name_ref = CFStringCreateWithCStringNoCopy(kCFAllocatorDefault, node->name, kCFStringEncodingUTF8, kCFAllocatorNull);
			node->name_length = new_name_length;
		}
	}

	/* change parents? */
	if ( node->parent != new_parent )
	{
		/* move the node_entry to the new parent */
		LIST_REMOVE(node, entries);
		LIST_INSERT_HEAD(&new_parent->children, node, entries);
		node->parent = new_parent;
	}

malloc_name:

	return ( error );
}

/*****************************************************************************/

int nodecache_move_node(
	struct node_entry *node,		/* the node_entry to move */
	struct node_entry *new_parent,  /* the new parent node_entry */
	size_t new_name_length,			/* length of new_name or 0 if not renaming */
	char *new_name)					/* the utf8 new name of the node or NULL */
{
	int error;

	lock_node_cache();

	error = internal_move_node(node, new_parent, new_name_length, new_name);

	unlock_node_cache();

	return ( error );
}

/*****************************************************************************/

/* delete dir_node's descendents and then delete dir_node */
static int delete_node_tree(
	struct node_entry *node,		/* the node_entry to delete */
	int recursive)					/* delete recursively if node is a directory */
{
	int error;
	
	error = 0;
		
	if ( recursive )
	{
		struct node_entry *child_node;
		
		child_node = (node->children).lh_first;
		while ( child_node != NULL )
		{
			struct node_entry *next_node;
			
			next_node = child_node->entries.le_next;
			error = delete_node_tree(child_node, TRUE);
			require_noerr(error, delete_child_node);
			
			child_node = next_node;
		}
	}
	else
	{
		require_action((node->children).lh_first == NULL, has_children, error = EBUSY);
	}
	
	/* move node over to the deleted list and mark it as deleted  */
	error = internal_move_node(node, g_deleted_root_node, 0, NULL);
	require_noerr(error, internal_move_node);
	
	node->flags |= nodeDeletedMask;
	node->attr_time = 0;
	
internal_move_node:
has_children:
delete_child_node:

	return ( error );
}

/*****************************************************************************/

int nodecache_delete_node(
	struct node_entry *node,		/* the node_entry to delete */
	int recursive)					/* delete recursively if node is a directory */
{
	int error;

	lock_node_cache();

	error = delete_node_tree(node, recursive);

	unlock_node_cache();

	return ( error );
}

/*****************************************************************************/

/* invalidate dir_node's children's node_times */
static int internal_invalidate_directory_node_time(struct node_entry *dir_node)
{
	int error;
	struct node_entry *node;

	error = 0;

	require_action(dir_node->node_type == WEBDAV_DIR_TYPE, not_directory, error = ENOTDIR);

	LIST_FOREACH(node, &(dir_node->children), entries)
	{
		node->node_time = 0;
	}

not_directory:

	return ( error );
}

/*****************************************************************************/

int nodecache_invalidate_directory_node_time(
	struct node_entry *dir_node)		/* parent directory node */
{
	int error;

	lock_node_cache();

	error = internal_invalidate_directory_node_time(dir_node);

	unlock_node_cache();

	return ( error );
}

/*****************************************************************************/

/* invalidate dir_node's children's node_times */
static int internal_delete_invalid_directory_nodes(struct node_entry *dir_node)
{
	int error;
	struct node_entry *node;
	
	error = 0;
	
	require_action(dir_node->node_type == WEBDAV_DIR_TYPE, not_directory, error = ENOTDIR);

	node = (&(dir_node->children))->lh_first;
	while ( node != NULL )
	{
		struct node_entry *next_node;
		
		next_node = node->entries.le_next;
		if ( node->node_time == 0 )
		{
			error = delete_node_tree(node, TRUE);
			require_noerr(error, delete_node_tree);
		}
		node = next_node;
	}

delete_node_tree:
not_directory:

	return ( error );
}

/*****************************************************************************/

int nodecache_delete_invalid_directory_nodes(
	struct node_entry *dir_node)		/* parent directory node */
{
	int error;

	lock_node_cache();

	error = internal_delete_invalid_directory_nodes(dir_node);

	unlock_node_cache();

	return ( error );
}

/*****************************************************************************/

/*
 * nodecache_get_path_from_node
 *
 * Builds a UTF-8 slash '/' delimited NULL terminated path from
 * the root node (but not including the root node) to target_node.
 * If the node is directory, the path MUST end with a slash.
 * The path will MUST NOT start with a slash since this is always a relative path.
 * If result is 0 (no error), then a newly allocated buffer containing the
 * path is returned and the caller is responsible for freeing it.
 */
static int internal_get_path_from_node(
	struct node_entry *target_node,
	char **path)
{
	int error;
	struct node_entry *cur_node;
	char *cur_ptr;
	char *pathbuf;
	size_t path_len;
	
	error = 0;
	pathbuf = NULL;
	path_len = 0;
	
	require_action(!NODE_IS_DELETED(target_node), node_deleted, error = ENOENT);
	
	pathbuf = malloc(PATH_MAX);
	require_action(pathbuf != NULL, malloc_pathbuf, error = errno);
		
	if ( target_node == g_root_node )
	{
		/* nothing to do */
		*pathbuf = '\0';
	}
	else
	{
		/* point at last character and put in the string terminator */
		cur_ptr = pathbuf + PATH_MAX - 1;
		*cur_ptr = '\0';
		
		cur_node = target_node;
		while ( cur_node != g_root_node )
		{
			require_action(cur_node != NULL, name_too_long, error = ENAMETOOLONG);
			
			/* make sure there's enough room for the next node name and a slash */
			require_action((cur_ptr - cur_node->name_length + 1) >= pathbuf,
				name_too_long, error = ENAMETOOLONG);
			
			/* add a slash */
			--cur_ptr;
			*cur_ptr = '/';
			
			/* copy in the name */
			cur_ptr -= cur_node->name_length;
			memcpy(cur_ptr, cur_node->name, cur_node->name_length);
			cur_node = cur_node->parent;
		}
		
		/* move the path to the front of the buffer */
		path_len = strlen(cur_ptr);
		memmove(pathbuf, cur_ptr, path_len + 1);
		
		/* remove trailing slash if not directory */
		if ( target_node->node_type != WEBDAV_DIR_TYPE )
		{
			--(path_len);
			pathbuf[path_len] = '\0';
		}
	}

name_too_long:
malloc_pathbuf:
node_deleted:

	if ( error )
	{
		if ( pathbuf != NULL )
		{
			free(pathbuf);
			pathbuf = NULL;
		}
	}

	*path = pathbuf;

	return ( error );
}

/*****************************************************************************/

int nodecache_get_path_from_node(
	struct node_entry *node,		/* -> node */
	char **path)					/* <- relative path to root node */
{
	int error;

	lock_node_cache();

	error = internal_get_path_from_node(node, path);

	unlock_node_cache();

	return ( error );
}

/*****************************************************************************/
/*****************************************************************************/

static int init_node_cache_lock(void)
{
	int error;
	pthread_mutexattr_t mutexattr;
	
	error = pthread_mutexattr_init(&mutexattr);
	require_noerr(error, pthread_mutexattr_init);
	
	error = pthread_mutex_init(&g_node_cache_lock, &mutexattr);
	require_noerr(error, pthread_mutex_init);

pthread_mutex_init:
pthread_mutexattr_init:

	return ( error );
}

/*****************************************************************************/

static void lock_node_cache(void)
{
	int error;
	
	error = pthread_mutex_lock(&g_node_cache_lock);
	require_noerr_action(error, pthread_mutex_lock, webdav_kill(-1));

pthread_mutex_lock:
	
	return;
}

/*****************************************************************************/

static void unlock_node_cache(void)
{
	int error;
	
	error = pthread_mutex_unlock(&g_node_cache_lock);
	require_noerr_action(error, pthread_mutex_unlock, webdav_kill(-1));

pthread_mutex_unlock:
	
	return;
}

/*****************************************************************************/