List:Falcon Storage Engine« Previous MessageNext Message »
From:Jim Starkey Date:October 7 2008 4:03pm
Subject:Re: Understanding RefCounts in Falcon
View as plain text  
Vladislav Vaintroub wrote:
> I'll look at that, maybe on weekend. The first very short try failed, I
> realized for falcon it would not be overly simple. 
>
> The reason is that.
> Unlike STL for example, Falcon does not use specialized "container" classes,
> that can store anything.
> Every Falcon object that can potentially live in a list has a member named
> "next" . Objects that can live in 2 lists, have 2 next pointers (like
> DeferredIndex has "next"  and "nextInTransaction" pointers). Placing object
> into a list is often accomplished via object->next = head.  This operation
> is not a copy and does not increment reference counter magically. I conclude
> that automatic reference counting suck on self-backed linked structures.
>
> Yet, Falcon has at least one class, that resembles STL container a bit. It
> is DenseArray. I'll continue my experimentation with it.
>
> PS: Looks like an addition to Commandments of Manual RefCounting : increment
> the refcount when placing object into a list, and decrement when removing
> from a list.
>
>   
Lists in Falcon tend to be ad hoc.  When a class can appear in an 
arbitrary number of lists, we used a LinkedList, which requires a memory 
allocation/deallocation for element (in Nimbus, I've re-implemented 
LinkedList as a template, which I've attached).   When a class has a 
natural relationship a list control by another class, Falcon generally 
uses the template Queue to manage the list.  Unlike LinkedList, Queue 
uses pointers in the object itself (the aforementioned next and prior) 
to eliminate allocation/deallocation of a list node.

There are other container templates, notably SparseArray and DenseArray, 
available for other purposes.

There isn't a one-size-fits-all container because different instances 
have different requirements.  Also, different classes have different 
lifetime control policies.  Most Falcon classes are simply deleted when 
unneeded -- no reason to use reference counting at all.  Some use 
non-interlocked reference counts and other require interlocked reference 
counts.

Incidentally, Nimbus also has a class RefObject that implements 
interlocked reference counting, saving redundant code.  The signature of 
RefObject has been kicking around for a couple of years as part of 
StorageEngineInterface.h, my proposal for restructuring the storage 
handler interface.  I'm also attaching the files for RefObject.

-- 
Jim Starkey
President, NimbusDB, Inc.
978 526-1376



#ifndef __LINKEDLIST_H
#define __LINKEDLIST_H

#define FOR_OBJECTS(type,var,list)	{for (LinkedList<type> *lln = (list)->next;
lln; lln = lln->next) { type var = lln->object;
#define END_FOR						}}

template <class T>
class LinkedList
{
public:
	LinkedList()
		{
		next = NULL;
		prior = NULL;
		}

	LinkedList(T obj)
		{
		object = obj;
		}

	void append (T object)
		{
		LinkedList *node = new LinkedList(object);
		node->next = NULL;

		if ( (node->prior = prior) )
			prior->next = node;
		else
			next = node;

		prior = node;
		}

	void prepend (T object)
		{
		LinkedList *node = new LinkedList(object);
		node->prior = NULL;

		if ( (node->next = next) )
			next->prior = node;
		else
			prior = node;

		next = node;
		}

	LinkedList *insertAfter (LinkedList *link, T object)
		{
		LinkedList *node = new LinkedList(object);
		node->prior = link;

		if ( (node->next = link->next) )
			node->next->prior = link;
		else
			prior = node;

		link->next = node;

		return node;
		}

	bool appendUnique (T object)
		{
		for (LinkedList *node = next; node; node = node->next)
			if (node->object == object)
				return false;

		append(object);

		return true;
		}

	bool remove (T object)
		{
		for (LinkedList *node = next; node; node = node->next)
			if (node->object == object)
				{
				if (node->prior)
					node->prior->next = node->next;
				else
					next = node->next;

				if (node->next)
					node->next->prior = node->prior;
				else
					prior = node->prior;

				return true;
				}
		
		return false;
		}

	bool isMember (T object)
		{
		for (LinkedList *node = next; node; node = node->next)
			if (node->object == object)
				return true;

		return false;
		}

	bool isEmpty ()
		{
		return next == NULL;
		}

	int count ()
		{
		int n = 0;

		for (LinkedList *node = next; node; node = node->next)
			++n;

		return n;
		}

	T getElement (int which)
		{
		int n = 0;
		
		for (LinkedList *node = next; node; node = node->next, ++n)
			if (n == which)
				return node->object;
		
		return NULL;
		}
	
	void clear ()
		{
		for (LinkedList *node; (node = next);)
			{
			next = node->next;
			delete node;
			}
		}
		
	LinkedList		*next;
	LinkedList		*prior;
	T				object;
};

#endif

// RefObject.cpp: implementation of the RefObject class.
//
//////////////////////////////////////////////////////////////////////

#include "Cloud.h"
#include "RefObject.h"
#include "Interlock.h"

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

RefObject::RefObject()
{
	refCount = 1;
}

RefObject::~RefObject()
{

}

void RefObject::addRef()
{
	INTERLOCKED_INCREMENT(refCount);
}

void RefObject::release()
{
	int count = INTERLOCKED_DECREMENT(refCount);

	if (count == 0)
		delete this;
}

// RefObject.h: interface for the RefObject class.
//
//////////////////////////////////////////////////////////////////////

#if !defined(AFX_REFOBJECT_H__86575CEF_FCDE_4F02_87DA_8A81ADD35E31__INCLUDED_)
#define AFX_REFOBJECT_H__86575CEF_FCDE_4F02_87DA_8A81ADD35E31__INCLUDED_

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000

class RefObject  
{
public:
	virtual void release();
	virtual void addRef();
	RefObject();
	virtual ~RefObject();

	INTERLOCK_TYPE		refCount;
};

#endif // !defined(AFX_REFOBJECT_H__86575CEF_FCDE_4F02_87DA_8A81ADD35E31__INCLUDED_)

Thread
Understanding RefCounts in FalconKevin Lewis6 Oct
  • RE: Understanding RefCounts in FalconVladislav Vaintroub6 Oct
    • Re: Understanding RefCounts in FalconMARK CALLAGHAN6 Oct
      • RE: Understanding RefCounts in FalconVladislav Vaintroub6 Oct
      • Re: Understanding RefCounts in FalconKevin Lewis6 Oct
        • RE: Understanding RefCounts in FalconVladislav Vaintroub6 Oct
          • Re: Understanding RefCounts in FalconKevin Lewis6 Oct
            • RE: Understanding RefCounts in FalconVladislav Vaintroub7 Oct
              • Re: Understanding RefCounts in FalconJim Starkey7 Oct