From: Jim Starkey Date: October 7 2008 4:03pm Subject: Re: Understanding RefCounts in Falcon List-Archive: http://lists.mysql.com/falcon/23 Message-Id: <48EB8834.6050700@nimbusdb.com> MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="------------040107060506050508000308" --------------040107060506050508000308 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit 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 --------------040107060506050508000308 Content-Type: text/plain; name="LinkedList.h" Content-Transfer-Encoding: 7bit Content-Disposition: inline; filename="LinkedList.h" #ifndef __LINKEDLIST_H #define __LINKEDLIST_H #define FOR_OBJECTS(type,var,list) {for (LinkedList *lln = (list)->next; lln; lln = lln->next) { type var = lln->object; #define END_FOR }} template 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 --------------040107060506050508000308 Content-Type: text/plain; name="RefObject.cpp" Content-Transfer-Encoding: 7bit Content-Disposition: inline; filename="RefObject.cpp" // 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; } --------------040107060506050508000308 Content-Type: text/plain; name="RefObject.h" Content-Transfer-Encoding: 7bit Content-Disposition: inline; filename="RefObject.h" // 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_) --------------040107060506050508000308--