view release on metacpan or  search on metacpan

libjit/jit/jit-memory-cache.c  view on Meta::CPAN

		else if(key > node->start)
		{
			return 1;
		}
		else
		{
			return 0;
		}
	}
}

/*
 * Rotate a sub-tree around a specific node.
 */
static jit_cache_node_t
CacheRotate(jit_cache_t cache, unsigned char *key, jit_cache_node_t around)
{
	jit_cache_node_t child, grandChild;
	int setOnLeft;
	if(CacheCompare(cache, key, around) < 0)
	{
		child = GetLeft(around);
		setOnLeft = 1;
	}
	else
	{
		child = GetRight(around);
		setOnLeft = 0;
	}
	if(CacheCompare(cache, key, child) < 0)
	{
		grandChild = GetLeft(child);
		SetLeft(child, GetRight(grandChild));
		SetRight(grandChild, child);
	}
	else
	{
		grandChild = GetRight(child);
		SetRight(child, GetLeft(grandChild));
		SetLeft(grandChild, child);
	}
	if(setOnLeft)
	{
		SetLeft(around, grandChild);
	}
	else
	{
		SetRight(around, grandChild);
	}
	return grandChild;
}

/*
 * Split a red-black tree at the current position.
 */
#define	Split()		\
			do { \
				SetRed(temp); \
				SetBlack(GetLeft(temp)); \
				SetBlack(GetRight(temp)); \
				if(GetRed(parent)) \
				{ \
					SetRed(grandParent); \
					if((CacheCompare(cache, key, grandParent) < 0) != \
							(CacheCompare(cache, key, parent) < 0)) \
					{ \
						parent = CacheRotate(cache, key, grandParent); \
					} \
					temp = CacheRotate(cache, key, greatGrandParent); \
					SetBlack(temp); \
				} \
			} while (0)

/*
 * Add a method region block to the red-black lookup tree
 * that is associated with a method cache.
 */
static void
AddToLookupTree(jit_cache_t cache, jit_cache_node_t method)
{
	unsigned char *key = method->start;
	jit_cache_node_t temp;
	jit_cache_node_t greatGrandParent;
	jit_cache_node_t grandParent;
	jit_cache_node_t parent;
	jit_cache_node_t nil = &(cache->nil);
	int cmp;

	/* Search for the insert position */
	temp = &(cache->head);
	greatGrandParent = temp;
	grandParent = temp;
	parent = temp;
	while(temp != nil)
	{
		/* Adjust our ancestor pointers */
		greatGrandParent = grandParent;
		grandParent = parent;
		parent = temp;

		/* Compare the key against the current node */
		cmp = CacheCompare(cache, key, temp);
		if(cmp == 0)
		{
			/* This is a duplicate, which normally shouldn't happen.
			   If it does happen, then ignore the node and bail out */
			return;
		}
		else if(cmp < 0)
		{
			temp = GetLeft(temp);
		}
		else
		{
			temp = GetRight(temp);
		}

		/* Do we need to split this node? */
		if(GetRed(GetLeft(temp)) && GetRed(GetRight(temp)))
		{
			Split();
		}
	}

	/* Insert the new node into the current position */
	method->left = (jit_cache_node_t)(((jit_nuint)nil) | ((jit_nuint)1));
	method->right = nil;
	if(CacheCompare(cache, key, parent) < 0)
	{
		SetLeft(parent, method);
	}
	else
	{
		SetRight(parent, method);
	}
	Split();
	SetBlack(cache->head.right);
}

jit_cache_t
_jit_cache_create(jit_context_t context)
{
	jit_cache_t cache;
	long limit, cache_page_size;
	int max_page_factor;
	unsigned long exec_page_size;

	limit = (long)
		jit_context_get_meta_numeric(context, JIT_OPTION_CACHE_LIMIT);
	cache_page_size = (long)
		jit_context_get_meta_numeric(context, JIT_OPTION_CACHE_PAGE_SIZE);
	max_page_factor = (int)
		jit_context_get_meta_numeric(context, JIT_OPTION_CACHE_MAX_PAGE_FACTOR);

	/* Allocate space for the cache control structure */
	if((cache = (jit_cache_t )jit_malloc(sizeof(struct jit_cache))) == 0)
	{
		return 0;
	}

	/* determine the default cache page size */
	exec_page_size = jit_vmem_page_size();
	if(cache_page_size <= 0)
	{
		cache_page_size = JIT_CACHE_PAGE_SIZE;
	}
	if(cache_page_size < exec_page_size)
	{
		cache_page_size = exec_page_size;
	}
	else
	{
		cache_page_size = (cache_page_size / exec_page_size) * exec_page_size;
	}

	/* determine the maximum page size factor */
	if(max_page_factor <= 0)
	{
		max_page_factor = JIT_CACHE_MAX_PAGE_FACTOR;
	}

	/* Initialize the rest of the cache fields */
	cache->pages = 0;
	cache->numPages = 0;
	cache->maxNumPages = 0;
	cache->pageSize = cache_page_size;
	cache->maxPageFactor = max_page_factor;
	cache->free_start = 0;
	cache->free_end = 0;
	if(limit > 0)
	{
		cache->pagesLeft = limit / cache_page_size;
		if(cache->pagesLeft < 1)
		{