splaytree.c

video linux conference

		return NULL;
	
    splaynode = splay(key, splaynode, &match_type, compare);
	
	/* If entry wasn't found, quit here */
	if (match_type == CLOSEST_MATCH) 
		return NULL;
	
	/* If the targeted node's left pointer is null, then set the new root
	   equal to the splaynode's right child */
	if (splaynode->left == NULL) {
	    new_root = splaynode->right;
	} 
	
	/* Otherwise, do something I don't currently understand */
	else {
	    new_root = splay(key, splaynode->left, &match_type, compare);
	    new_root->right = splaynode->right;
	}

	/* Set splay nodes children pointers to null */
	splaynode->left = splaynode->right = NULL;
	
	/* Free the splaynode (and only this node since its children are now empty */
	free_splaynode(splaynode, free_key);
	
	/* Return the resulting tree */
	return new_root;
	
}

/* Create a new splay node type */
static inline splaynode_t * new_splaynode(int type, void * key, void * data) {
	splaynode_t * splaynode;	
	/* Argument checks */
	if (data == NULL)
		return NULL;
	
	if (key == NULL)
		return NULL;
	
	/* Creates the new splay node struct */
	if ((splaynode = (splaynode_t*)malloc(sizeof(splaynode_t))) == NULL)
		return NULL;
	
	splaynode->data = data;
	splaynode->type = type;
	splaynode->key = key;
	
	/* Return the new splay node */
	return splaynode;
}

/* Inserts a link into the splay tree */
inline int splay_insert_link(void * alias_key, void * orig_key, splaytree_t * splaytree) {

   splaynode_t * splaynode, * data_node;
   void * key_clone;

   /* Null arguments */	
   if (splaytree == NULL)
		return FAILURE;
   
   if (alias_key == NULL)
	   	return FAILURE;

   if (orig_key == NULL)
	   	return FAILURE;
   
   /* Find the splaynode corresponding to the original key */
   if ((data_node = get_splaynode_of(orig_key, splaytree)) == NULL)
	   return FAILURE;
   
   /* Create a new splay node of symbolic link type */
   if ((splaynode = new_splaynode(SYMBOLIC_NODE_TYPE, (key_clone = splaytree->copy_key(alias_key)), data_node)) == NULL) {
		splaytree->free_key(key_clone);
		return OUTOFMEM_ERROR;
   }

   /* Insert the splaynode into the given splaytree */
   if ((splay_insert_node(splaynode, splaytree)) < 0) {
     splaynode->left=splaynode->right = NULL;
     free_splaynode(splaynode, splaytree->free_key);
     return FAILURE;
   }		
	
   /* Done, return success */
   return SUCCESS;
}	

/* Inserts 'data' into the 'splaytree' paired with the passed 'key' */
inline int splay_insert(void * data, void * key, splaytree_t * splaytree) {

	splaynode_t * splaynode;
	void * key_clone;
	
	/* Null argument checks */
	if (splaytree == NULL) {
	    return FAILURE;
	}
	
	if (key == NULL)
		return FAILURE;
	
	/* Clone the key argument */
	key_clone = splaytree->copy_key(key);

	/* Create a new splaynode (of regular type) */
	if ((splaynode = new_splaynode(REGULAR_NODE_TYPE, key_clone, data)) == NULL) {
		splaytree->free_key(key_clone);
		return OUTOFMEM_ERROR;		
	}
       
	
	/* Inserts the splaynode into the splaytree */
	if (splay_insert_node(splaynode, splaytree) < 0) {
	  splaynode->left=splaynode->right=NULL;
	  free_splaynode(splaynode, splaytree->free_key);
	  return FAILURE;		
	}	
     

	return SUCCESS;
}

/* Helper function to insert splaynodes into the splaytree */
static inline int splay_insert_node(splaynode_t * splaynode, splaytree_t * splaytree) {
  int match_type;
  int cmpval;
  void * key;
  splaynode_t * t;
	
  /* Null argument checks */
  if (splaytree == NULL)
    return FAILURE;

  if (splaynode == NULL)
	return FAILURE;
  
  key = splaynode->key;
  
  t = splaytree->root; 


  /* Root is null, insert splaynode here */
  if (t == NULL) {
	splaynode->left = splaynode->right = NULL;
	splaytree->root = splaynode;
	return SUCCESS;

  }
  
  t = splay(key, t, &match_type, splaytree->compare);
  
  if ((cmpval = splaytree->compare(key,t->key)) < 0) {
	splaynode->left = t->left;
	splaynode->right = t;
	t->left = NULL;
	splaytree->root = splaynode;
	return SUCCESS;

  } 

  else if (cmpval > 0) {
	splaynode->right = t->right;
	splaynode->left = t;
	t->right = NULL; 
	splaytree->root = splaynode;
	return SUCCESS;
   } 
   
   /* Item already exists in tree, don't reinsert */
  else {
    
    return FAILURE;
  }
}

/* Returns the 'maximum' key that is less than the given key in the splaytree */
inline void * splay_find_below_max(void * key, splaytree_t * splaytree) {
	
	void * closest_key;
	
	if (splaytree == NULL)
		return NULL;
	if (splaytree->root == NULL)
		return NULL;
	if (key == NULL)
		return NULL;
	
	closest_key = NULL;
	
	splay_find_below_max_helper(key, &closest_key, splaytree->root, splaytree->compare);

	if (closest_key == NULL) return NULL;
	return splay_find(closest_key, splaytree);
}


/* Returns the 'minimum' key that is greater than the given key in the splaytree */
inline void * splay_find_above_min(void * key, splaytree_t * splaytree) {
	
	void * closest_key;
	
	if (splaytree == NULL)
		return NULL;
	if (splaytree->root == NULL)
		return NULL;
	if (key == NULL)
		return NULL;
	closest_key = NULL;
	
	splay_find_above_min_helper(key, &closest_key, splaytree->root, splaytree->compare);

	if (closest_key == NULL) { 
		return NULL;
	}
	
	return splay_find(closest_key, splaytree);
}

/* Helper function */
static inline void splay_find_below_max_helper(void * min_key, void ** closest_key, splaynode_t * root, int (*compare)()) {

		/* Empty root, return*/	
		if (root == NULL)
			return;
			
		/* The root key is less than the previously found closest key.
		   Also try to make the key non null if the value is less than the max key */
		
		if ((*closest_key == NULL) || (compare(root->key, *closest_key) < 0)) {
			
			/*  The root key is less than the given max key, so this is the
				smallest change from the given max key */
			if (compare(root->key, min_key) > 0) {
				
				*closest_key = root->key;
				
				/* Look right again in case even a greater key exists that is 
				   still less than the given max key */
				splay_find_below_max_helper(min_key, closest_key, root->left, compare);
			}
			
			/* The root key is greater than the given max key, and greater than 
			   the closest key, so search left */
			else {
				splay_find_below_max_helper(min_key, closest_key, root->right, compare);				
			}	
		}	
		
		/* The root key is less than the found closest key, search right */
		else {
				splay_find_below_max_helper(min_key, closest_key, root->left, compare);				
		}
	
}

/* Helper function */
static inline void splay_find_above_min_helper(void * max_key, void ** closest_key, splaynode_t * root, int (*compare)()) {

		/* Empty root, stop */	
		if (root == NULL)
			return;
			
		/* The root key is greater than the previously found closest key.
		   Also try to make the key non null if the value is less than the min key */
		
		if ((*closest_key == NULL) || (compare(root->key, *closest_key) > 0)) {
			
			/*  The root key is greater than the given min key, so this is the
				smallest change from the given min key */
			if (compare(root->key, max_key) < 0) {
				
				*closest_key = root->key;
				
			   /* Look left again in case even a smaller key exists that is 
				  still greater than the given min key */
				splay_find_above_min_helper(max_key, closest_key, root->right, compare);
			}
			
			/* The root key is less than the given min key, and less than 
			   the closest key, so search right */
			else {
				splay_find_above_min_helper(max_key, closest_key, root->left, compare);				
			}	
		}	
		
		/* The root key is greater than the found closest key, search left */
		else {
				splay_find_above_min_helper(max_key, closest_key, root->right, compare);				
		}
}	

/* Find the minimum entry of the splay tree */
inline void * splay_find_min(splaytree_t * t) {

	splaynode_t * splaynode;
	
	if (t == NULL)
		return NULL;
	if (t->root == NULL)
		return NULL;
	
	splaynode = t->root;
	
	while (splaynode->left != NULL)
		splaynode= splaynode->left;
	
	return splaynode->data;
}


/* Find the maximum entry of the splay tree */
inline void * splay_find_max(splaytree_t * t) {

	splaynode_t * splaynode;
	
	if (t == NULL)
		return NULL;
	if (t->root == NULL)
		return NULL;
	
	splaynode = t->root;
	 
	while (splaynode->right != NULL) {
	  printf("data:%d\n", *(int*)splaynode->key);
		splaynode = splaynode->right;
	}
	return splaynode->data;
}

inline int splay_size(splaytree_t * t) {

	if (t == NULL)
	  return 0;
	if (t->root == NULL)
	  return 0;
	
	return splay_rec_size(t->root);
	 
}

static inline int splay_rec_size(splaynode_t * splaynode) {

  if (!splaynode)
    return 0;

  return 1 + splay_rec_size(splaynode->left) + splay_rec_size(splaynode->right);

}