[Pvfs2-cvs] commit by kunkel in pvfs2/src/io/trove/trove-tas:
red-black-tree.h tas-queue.c red-black-tree.c README tas.c
tas-queue.h
CVS commit program
cvs at parl.clemson.edu
Tue Oct 31 03:42:07 EST 2006
Update of /projects/cvsroot/pvfs2/src/io/trove/trove-tas
In directory parlweb1:/tmp/cvs-serv1027/src/io/trove/trove-tas
Modified Files:
Tag: pvfs2-kunkel-tas-branch
red-black-tree.h tas-queue.c red-black-tree.c README tas.c
tas-queue.h
Log Message:
Fixed lazy caps for support methods.
Index: red-black-tree.h
===================================================================
RCS file: /projects/cvsroot/pvfs2/src/io/trove/trove-tas/Attic/red-black-tree.h,v
diff -p -u -r1.1.2.2 -r1.1.2.3
--- red-black-tree.h 30 Oct 2006 21:17:37 -0000 1.1.2.2
+++ red-black-tree.h 31 Oct 2006 08:42:07 -0000 1.1.2.3
@@ -4,12 +4,7 @@
#ifndef REDBLACKTREE_H_
#define REDBLACKTREE_H_
-#include<stdlib.h>
-
-#ifndef TRUE
-#define TRUE 1
-#define FALSE 0
-#endif
+#include <stdlib.h>
enum node_color
{
@@ -27,7 +22,7 @@ struct red_black_tree_node
struct red_black_tree_node *right;
RBData *data;
- char color;
+ enum node_color color;
};
typedef struct red_black_tree_node tree_node;
@@ -35,54 +30,49 @@ typedef struct red_black_tree_node tree_
struct red_black_tree_
{
tree_node *head;
- int (
- *compare) (
- RBData * data,
- RBKey * key);
- int (
- *compare2) (
- RBData * data,
- RBData * data2);
+ int (*compare) (RBData * data,RBKey * key);
+ int (*compare2) ( RBData * data, RBData * data2);
};
typedef struct red_black_tree_ red_black_tree;
/* functions */
-tree_node *lookupTree(
+tree_node *lookup_tree(
RBKey * key,
red_black_tree * tree);
-red_black_tree *newRedBlackTree(
+
+red_black_tree *new_red_black_tree(
int (*compare) (RBData * data,
RBKey * key),
int (*compare2) (RBData * data,
RBData * data2));
-void freeEmptyRedBlackTree(
+
+void free_empty_red_black_tree(
red_black_tree ** tree);
-tree_node *insertKeyIntoTree(
+tree_node *insert_key_into_tree(
RBData * data,
red_black_tree * tree);
-void deleteNodeFromTree(
+void delete_node_from_tree(
tree_node * node,
red_black_tree * tree);
/* this function returns NULL if the node is deleted, or the node which
* changed position
* this is necessary if the data contains references to the node :) */
-tree_node *deleteNodeFromTree2(
+tree_node *delete_node_from_tree2(
tree_node * node,
red_black_tree * tree);
-void iterateRedBlackTree(
- void (*callback) (RBData * data,
- void *funcData),
+void iterate_red_black_tree(
+ void (*callback) (RBData * data, void *funcData),
red_black_tree * tree,
void *funcData);
/* example compare functions: */
-int compareInt64(
+int compare_int64(
RBData * data,
RBKey * key);
Index: tas-queue.c
===================================================================
RCS file: /projects/cvsroot/pvfs2/src/io/trove/trove-tas/Attic/tas-queue.c,v
diff -p -u -r1.1.2.2 -r1.1.2.3
--- tas-queue.c 30 Oct 2006 21:17:37 -0000 1.1.2.2
+++ tas-queue.c 31 Oct 2006 08:42:07 -0000 1.1.2.3
@@ -1,7 +1,11 @@
#include<stdio.h>
#include "tas-queue.h"
-tas_queue *newTasQueue(
+#ifdef HAVE_MALLOC_H
+#include <malloc.h>
+#endif
+
+tas_queue *new_tas_queue(
void)
{
tas_queue *ret = malloc(sizeof(tas_queue));
@@ -9,7 +13,7 @@ tas_queue *newTasQueue(
return ret;
}
-void relinkFront(
+void relink_front(
queue_elem * elem,
tas_queue * queue)
{
@@ -30,29 +34,29 @@ void relinkFront(
}
}
-void *insertKeyIntoQueue(
- queueKey key,
+void *insert_key_into_queue(
+ queue_key key,
void *data,
tas_queue * queue)
{
- queue_elem *elem = lookupQueue(key, queue);
+ queue_elem *elem = lookup_queue(key, queue);
void *olddata = NULL;
if (elem == NULL)
{
- pushFrontKey(key, data, queue);
+ push_front_key(key, data, queue);
}
else
{
/* replace existing data */
olddata = elem->data;
elem->data = data;
- relinkFront(elem, queue);
+ relink_front(elem, queue);
}
return olddata;
}
-queue_elem *pushFrontKey(
- queueKey key,
+queue_elem *push_front_key(
+ queue_key key,
void *data,
tas_queue * queue)
{
@@ -69,8 +73,8 @@ queue_elem *pushFrontKey(
return elem;
}
-queue_elem *lookupQueue(
- queueKey key,
+queue_elem *lookup_queue(
+ queue_key key,
tas_queue * queue)
{
queue_elem *found = *queue;
@@ -96,7 +100,7 @@ queue_elem *lookupQueue(
return NULL;
}
-void deleteElementFromList(
+void delete_element_from_list(
queue_elem * found,
tas_queue * queue)
{
@@ -118,14 +122,14 @@ void deleteElementFromList(
}
}
-void *deleteKeyFromList(
- queueKey key,
+void *delete_key_from_list(
+ queue_key key,
tas_queue * queue)
{
- queue_elem *found = lookupQueue(key, queue);
+ queue_elem *found = lookup_queue(key, queue);
if (found == NULL)
return NULL;
- deleteElementFromList(found, queue);
+ delete_element_from_list(found, queue);
void *data;
data = found->data;
free(found);
Index: red-black-tree.c
===================================================================
RCS file: /projects/cvsroot/pvfs2/src/io/trove/trove-tas/Attic/red-black-tree.c,v
diff -p -u -r1.1.2.2 -r1.1.2.3
--- red-black-tree.c 30 Oct 2006 21:17:37 -0000 1.1.2.2
+++ red-black-tree.c 31 Oct 2006 08:42:07 -0000 1.1.2.3
@@ -1,10 +1,14 @@
/*
* Author: Julian Kunkel 2005
*/
+
+#ifdef HAVE_MALLOC_H
+#include <malloc.h>
+#endif
#include "red-black-tree.h"
-int compareInt64(
+int compare_int64(
RBData * data,
RBKey * key)
{
@@ -39,7 +43,7 @@ static void inorderWalkthrough(
}
}
-void iterateRedBlackTree(
+void iterate_red_black_tree(
void (*callback) (RBData * data,
void *funcData),
red_black_tree * tree,
@@ -51,7 +55,7 @@ void iterateRedBlackTree(
}
/* take care of memory managment of the data by yourself ! */
-tree_node *lookupTree(
+tree_node *lookup_tree(
RBKey * key,
red_black_tree * tree)
{
@@ -77,7 +81,7 @@ tree_node *lookupTree(
}
-red_black_tree *newRedBlackTree(
+red_black_tree *new_red_black_tree(
int (*compare) (RBData * data,
RBKey * key),
int (*compare2) (RBData * data,
@@ -90,7 +94,7 @@ red_black_tree *newRedBlackTree(
return tree;
}
-void freeEmptyRedBlackTree(
+void free_empty_red_black_tree(
red_black_tree ** tree)
{
if (*tree != NULL)
@@ -251,7 +255,7 @@ static void rebuildRBTree(
}
}
-tree_node *insertKeyIntoTree(
+tree_node *insert_key_into_tree(
RBData * data,
red_black_tree * tree)
{
@@ -409,18 +413,18 @@ static void rebuildTreeAfterDeletion(
}
}
-void deleteNodeFromTree(
+void delete_node_from_tree(
tree_node * node,
red_black_tree * tree)
{
- tree_node *changed = deleteNodeFromTree2(node, tree);
+ tree_node *changed = delete_node_from_tree2(node, tree);
if (changed != NULL)
{
- deleteNodeFromTree2(changed, tree);
+ delete_node_from_tree2(changed, tree);
}
}
-tree_node *deleteNodeFromTree2(
+tree_node *delete_node_from_tree2(
tree_node * node,
red_black_tree * tree)
{
@@ -437,14 +441,14 @@ tree_node *deleteNodeFromTree2(
}
tree_node *child = node->left == NULL ? node->right : node->left;
- int createdChild = FALSE;
+ int createdChild = 0;
/* delete node which now has at most one child
* use node as dummy child */
if (node->color == BLACK && node->parent != NULL && child == NULL)
{
child = node;
child->data = NULL;
- createdChild = TRUE;
+ createdChild = 1;
}
/* relink nodes */
Index: README
===================================================================
RCS file: /projects/cvsroot/pvfs2/src/io/trove/trove-tas/Attic/README,v
diff -p -u -r1.1.2.1 -r1.1.2.2
--- README 29 Oct 2006 13:19:13 -0000 1.1.2.1
+++ README 31 Oct 2006 08:42:07 -0000 1.1.2.2
@@ -1,3 +1,8 @@
This is an implementation of the trove interface which will not save persitent data.
TAS = Trove analysis stub should be used to measure the performance overhead of the
-pvfs2 layers between application and storage space.
+pvfs2 layers between application and storage space.
+
+Notes:
+The implementation is not completed and does not intend to provide all
+functionality and a well defined or even correct error handling as DBPF.
+It is intendet to be used for performance evualuation only.
\ No newline at end of file
Index: tas.c
===================================================================
RCS file: /projects/cvsroot/pvfs2/src/io/trove/trove-tas/Attic/tas.c,v
diff -p -u -r1.1.2.5 -r1.1.2.6
--- tas.c 30 Oct 2006 21:17:37 -0000 1.1.2.5
+++ tas.c 31 Oct 2006 08:42:07 -0000 1.1.2.6
@@ -6,6 +6,9 @@
#include <stdio.h>
#include <string.h>
+#ifdef HAVE_MALLOC_H
+#include <malloc.h>
+#endif
/* for unlink: */
#include <unistd.h>
#include <assert.h>
@@ -346,10 +349,10 @@ static void insert_cache_element(
#if defined(TAS_USE_RED_BLACKTREE)
found->pair_list = NULL;
found->pair_tree = NULL;
- insertKeyIntoTree((RBData *) found, tas_meta_cache);
+ insert_key_into_tree((RBData *) found, tas_meta_cache);
#elif defined(TAS_USE_QUEUE)
found->pairs = NULL;
- pushFrontKey(new_handle, found, tas_meta_cache);
+ push_front_key(new_handle, found, tas_meta_cache);
#endif
meta_count++;
@@ -364,7 +367,7 @@ static keyvalpair *find_pair_of_cached_e
{
return FALSE;
}
- tree_node *node = (tree_node *) (lookupTree(key_p, cache_entry->pair_tree));
+ tree_node *node = (tree_node *) (lookup_tree(key_p, cache_entry->pair_tree));
if (node == NULL)
return FALSE;
@@ -421,7 +424,7 @@ static int remove_pair_of_cached_entry(
{
return FALSE;
}
- tree_node *node = lookupTree(key_p, cache_entry->pair_tree);
+ tree_node *node = lookup_tree(key_p, cache_entry->pair_tree);
if( node == NULL )
{
return FALSE;
@@ -434,7 +437,7 @@ static int remove_pair_of_cached_entry(
keyval_copy(key_p, val_p, 0, found_pair);
/* delete Node from Tree: */
- deleteNodeFromTree(node, cache_entry->pair_tree);
+ delete_node_from_tree(node, cache_entry->pair_tree);
/* relink pair_list: */
if (found_pair->next != NULL)
@@ -448,7 +451,7 @@ static int remove_pair_of_cached_entry(
if (found_pair->next == NULL)
{
/* The Tree is now empty */
- freeEmptyRedBlackTree(&cache_entry->pair_tree);
+ free_empty_red_black_tree(&cache_entry->pair_tree);
}
else
{
@@ -523,19 +526,19 @@ static inline handle_cache *find_cached_
handle_fsid key;
key.handle = handle;
key.fs_id = fs_id;
- tree_node *node = lookupTree(&key, tas_meta_cache);
+ tree_node *node = lookup_tree(&key, tas_meta_cache);
if (node == NULL)
{
return NULL;
}
return (handle_cache *) node->data;
#elif defined(TAS_USE_QUEUE)
- queue_elem *elem = lookupQueue(handle, tas_meta_cache);
+ queue_elem *elem = lookup_queue(handle, tas_meta_cache);
if (elem == NULL)
{
return NULL;
}
- relinkFront(elem, tas_meta_cache); /* push element to front of cache */
+ relink_front(elem, tas_meta_cache); /* push element to front of cache */
return (handle_cache *) elem->data;
#endif
}
@@ -551,13 +554,13 @@ static int remove_cached_entry(
handle_fsid key;
key.handle = handle;
key.fs_id = fs_id;
- tree_node *node = lookupTree(&key, tas_meta_cache);
+ tree_node *node = lookup_tree(&key, tas_meta_cache);
if (node == NULL)
return FALSE;
result = node->data;
- deleteNodeFromTree(node, tas_meta_cache);
+ delete_node_from_tree(node, tas_meta_cache);
#elif defined(TAS_USE_QUEUE)
- result = deleteKeyFromList(handle, tas_meta_cache);
+ result = delete_key_from_list(handle, tas_meta_cache);
#endif
if (result != NULL)
{
@@ -577,7 +580,7 @@ static inline void insert_keyval_pair(
if (found->pair_tree == NULL)
{ /* create new RedBlackTree */
found->pair_tree =
- newRedBlackTree(compare_keyval_pairs, compare_keyval_pairs2);
+ new_red_black_tree(compare_keyval_pairs, compare_keyval_pairs2);
pair->next = NULL;
found->pair_list = pair;
@@ -589,7 +592,7 @@ static inline void insert_keyval_pair(
found->pair_list = pair;
}
pair->prev = NULL;
- insertKeyIntoTree((void *) pair, found->pair_tree);
+ insert_key_into_tree((void *) pair, found->pair_tree);
#elif defined(TAS_USE_QUEUE)
int64_t key_hash = queue_key_hash_func(pair->key.buffer, pair->key.buffer_sz);
@@ -612,9 +615,9 @@ static int tas_initialize(
return -1;
}
#if defined(TAS_USE_RED_BLACKTREE)
- tas_meta_cache = newRedBlackTree(compare_handle, compare_handle2);
+ tas_meta_cache = new_red_black_tree(compare_handle, compare_handle2);
#elif defined(TAS_USE_QUEUE)
- tas_meta_cache = newTasQueue();
+ tas_meta_cache = new_tas_queue();
#endif
fclose(file);
@@ -705,7 +708,7 @@ static void datawrite(
if (found->pair_tree != NULL)
{
fdata->keyval_mem_size += sizeof(red_black_tree);
- iterateRedBlackTree(keyvalwrite, found->pair_tree, fdata);
+ iterate_red_black_tree(keyvalwrite, found->pair_tree, fdata);
}
#elif defined(TAS_USE_QUEUE)
keyvalpair *pair = found->pairs;
@@ -740,7 +743,7 @@ static int tas_finalize(
fdata->keyval_mem_size = 0;
#if defined(TAS_USE_RED_BLACKTREE)
- iterateRedBlackTree(datawrite, tas_meta_cache, fdata);
+ iterate_red_black_tree(datawrite, tas_meta_cache, fdata);
#elif defined(TAS_USE_QUEUE)
iterate_tas_queue(datawrite(elem->data, &elem->key, fdata), elem,
tas_meta_cache);
@@ -1908,12 +1911,12 @@ static int tas_collection_setinfo(TROVE_
keyvalpair *akt_pair;
#if defined(TAS_USE_RED_BLACKTREE)
- insertKeyIntoTree((RBData *) found, tas_meta_cache);
+ insert_key_into_tree((RBData *) found, tas_meta_cache);
found->pair_list = NULL;
found->pair_tree = NULL;
#elif defined(TAS_USE_QUEUE)
found->pairs = NULL;
- pushFrontKey(found->handle, found, tas_meta_cache);
+ push_front_key(found->handle, found, tas_meta_cache);
#endif
akt_pair = NULL;
Index: tas-queue.h
===================================================================
RCS file: /projects/cvsroot/pvfs2/src/io/trove/trove-tas/Attic/tas-queue.h,v
diff -p -u -r1.1.2.2 -r1.1.2.3
--- tas-queue.h 30 Oct 2006 21:17:37 -0000 1.1.2.2
+++ tas-queue.h 31 Oct 2006 08:42:07 -0000 1.1.2.3
@@ -7,7 +7,7 @@
#ifndef TASQUEUE_H_
#define TASQUEUE_H_
-#include<stdlib.h>
+#include <stdlib.h>
/*
* Print a warning if lookup takes more than WARNING_NUM iterations
@@ -15,14 +15,14 @@
*/
#define WARNING_NUM 40
-typedef int64_t queueKey;
+typedef int64_t queue_key;
struct tas_queue_elem_
{
struct tas_queue_elem_ *next;
struct tas_queue_elem_ *prev;
- queueKey key;
+ queue_key key;
void *data;
};
@@ -34,34 +34,36 @@ typedef struct tas_queue_elem_ *tas_queu
/* functions: */
-tas_queue *newTasQueue(
+tas_queue *new_tas_queue(
void);
-queue_elem *lookupQueue(
- queueKey key,
+queue_elem *lookup_queue(
+ queue_key key,
tas_queue * queue);
-void deleteElementFromList(
+void delete_element_from_list(
queue_elem * elem,
tas_queue * queue);
-void *deleteKeyFromList(
- queueKey key,
+
+void *delete_key_from_list(
+ queue_key key,
tas_queue * queue);
+
/* lookup key and replace data if possible, else pushfront.
* returns replaced data (if key exists)
* Queue element is put to head of queue */
-void *insertKeyIntoQueue(
- queueKey key,
+void *insert_key_into_queue(
+ queue_key key,
void *data,
tas_queue * queue);
-queue_elem *pushFrontKey(
- queueKey key,
+queue_elem *push_front_key(
+ queue_key key,
void *data,
tas_queue * queue);
/* remove data from current possition and push it to head of queue, */
-void relinkFront(
+void relink_front(
queue_elem * elem,
tas_queue * queue);
More information about the Pvfs2-cvs
mailing list