Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > Reference counting

Reply
Thread Tools

Reference counting

 
 
daknok
Guest
Posts: n/a
 
      06-05-2011
Hi,

If I want to do simple reference counting for different structures I
would go like this:

struct String {
unsigned references;
char *cString;
size_t length;
};

void StringRelease(struct String *str) {
str->references--;
if (str->references == 0) {
free(str->cString);
free(str);
}
}

struct String *StringRetain(struct String *str) {
str->references++;
return str;
}

Though if I have about ten structs, I have ten different functions to
increase and decrease the reference count. Is it, in some way, possible
to just provide one function for increasing and one function for
decreasing the reference count which can be used for all structs with a
reference count?

 
Reply With Quote
 
 
 
 
Angel
Guest
Posts: n/a
 
      06-05-2011
On 2011-06-05, daknok <(E-Mail Removed)> wrote:
> Hi,
>
> If I want to do simple reference counting for different structures I
> would go like this:
>
> struct String {
> unsigned references;
> char *cString;
> size_t length;
> };
>
> void StringRelease(struct String *str) {
> str->references--;
> if (str->references == 0) {
> free(str->cString);
> free(str);
> }
> }
>
> struct String *StringRetain(struct String *str) {
> str->references++;
> return str;
> }
>
> Though if I have about ten structs, I have ten different functions to
> increase and decrease the reference count. Is it, in some way, possible
> to just provide one function for increasing and one function for
> decreasing the reference count which can be used for all structs with a
> reference count?


There are number of ways to do this. One of the easiest (but least
flexible) is to start all your structures with the same reference
variable, of the same type, like this:

struct a
{
int ref_count;
char *data;
char *more_data;
};

struct b
{
int ref_count;
int number;
int another_number;
};

Now you can safely read the ref_count from any of these structures, for
example like this:

struct ref_count
{
int ref_count;
};

void increase_refcount(void *data)
{
((struct refcount *) data)->refcount++;
}

You can safely pass either pointers to struct a or struct b to this
function, and it will work as expected. The standard guarantees that
shared fields at the beginning of structures are compatible. In a way,
this is a primitive C implementation of inheritance.

The other way I used this same principle to create a generic linked
list. Similar tricks are also used in the Linux kernel, and in the
network parts of glibc.


--
"C provides a programmer with more than enough rope to hang himself.
C++ provides a firing squad, blindfold and last cigarette."
- seen in comp.lang.c
 
Reply With Quote
 
 
 
 
BartC
Guest
Posts: n/a
 
      06-05-2011


"daknok" <(E-Mail Removed)> wrote in message
news:4deb6008$0$28457$(E-Mail Removed)...
> Hi,
>
> If I want to do simple reference counting for different structures I would
> go like this:
>
> struct String {
> unsigned references;
> char *cString;
> size_t length;
> };
>
> void StringRelease(struct String *str) {
> str->references--;
> if (str->references == 0) {
> free(str->cString);
> free(str);
> }
> }
>
> struct String *StringRetain(struct String *str) {
> str->references++;
> return str;
> }
>
> Though if I have about ten structs, I have ten different functions to
> increase and decrease the reference count. Is it, in some way, possible to
> just provide one function for increasing and one function for decreasing
> the reference count which can be used for all structs with a reference
> count?


How different are these structs? It looks like each struct needs other
things doing to it apart from the reference count.

I might go for a single, more elaborate struct that does everything, with
perhaps a tag in it saying what kind of struct it is. Then you need one set
of functions, although they will be more complex (and might still delegate
the work to multiple functions).

> str->references--;
> if (str->references == 0) {
> free(str->cString);
> free(str);


Could this be called when ->references is already zero? I might check for
this.

--
Bartc


 
Reply With Quote
 
daknok
Guest
Posts: n/a
 
      06-05-2011
On 2011-06-05 14:14:25 +0200, BartC said:

> "daknok" <(E-Mail Removed)> wrote in message
> news:4deb6008$0$28457$(E-Mail Removed)...
>> Hi,
>>
>> If I want to do simple reference counting for different structures I
>> would go like this:
>>
>> struct String {
>> unsigned references;
>> char *cString;
>> size_t length;
>> };
>>
>> void StringRelease(struct String *str) {
>> str->references--;
>> if (str->references == 0) {
>> free(str->cString);
>> free(str);
>> }
>> }
>>
>> struct String *StringRetain(struct String *str) {
>> str->references++;
>> return str;
>> }
>>
>> Though if I have about ten structs, I have ten different functions to
>> increase and decrease the reference count. Is it, in some way, possible
>> to just provide one function for increasing and one function for
>> decreasing the reference count which can be used for all structs with a
>> reference count?

>
> How different are these structs? It looks like each struct needs other
> things doing to it apart from the reference count.


Well I have structs for strings, dates, files, data and URLs basically.
They all use reference counting.

>
> I might go for a single, more elaborate struct that does everything,
> with perhaps a tag in it saying what kind of struct it is. Then you
> need one set of functions, although they will be more complex (and
> might still delegate the work to multiple functions).
>
>> str->references--;
>> if (str->references == 0) {
>> free(str->cString);
>> free(str);

>
> Could this be called when ->references is already zero? I might check for this.


This should indeed always be called when the number of references
reaches zero, because in that case it isn't anymore in use.

 
Reply With Quote
 
daknok
Guest
Posts: n/a
 
      06-05-2011
Of course this will only be for strings. I need a deallocator for each
struct, though I could do this with a type field:

typedef enum {
ReferenceCountTypeString,
ReferenceCountTypeDate,
ReferenceCountTypeData,
ReferenceCountTypeURL,
} ReferenceCountType;

struct ReferenceCount {
unsigned references;
ReferenceCountType type;
};

struct String {
struct ReferenceCount refCount;
char *cString;
size_t length;
};

 
Reply With Quote
 
BartC
Guest
Posts: n/a
 
      06-05-2011
"daknok" <(E-Mail Removed)> wrote in message
news:4deb74f0$0$28443$(E-Mail Removed)...
> On 2011-06-05 14:14:25 +0200, BartC said:


>>> str->references--;
>>> if (str->references == 0) {
>>> free(str->cString);
>>> free(str);

>>
>> Could this be called when ->references is already zero? I might check for
>> this.

>
> This should indeed always be called when the number of references reaches
> zero, because in that case it isn't anymore in use.


I meant the str->references-- bit.

If StringRelease() is called on something that already has a reference count
of 0, then it might go wrong.

And because such a function is likely to be called from many places where
the caller does not know/care how many active references remain, then that
might be an issue.

--
bartc

 
Reply With Quote
 
daknok
Guest
Posts: n/a
 
      06-05-2011
On 2011-06-05 15:45:41 +0200, BartC said:

> "daknok" <(E-Mail Removed)> wrote in message
> news:4deb74f0$0$28443$(E-Mail Removed)...
>> On 2011-06-05 14:14:25 +0200, BartC said:

>
>>>> str->references--;
>>>> if (str->references == 0) {
>>>> free(str->cString);
>>>> free(str);
>>>
>>> Could this be called when ->references is already zero? I might check for
>>> this.

>>
>> This should indeed always be called when the number of references reaches
>> zero, because in that case it isn't anymore in use.

>
> I meant the str->references-- bit.
>
> If StringRelease() is called on something that already has a reference count
> of 0, then it might go wrong.
>
> And because such a function is likely to be called from many places where
> the caller does not know/care how many active references remain, then that
> might be an issue.


If the code is written well, this won't be a problem. Even better could
I write a macro:

SafeStringRelease(s) if (s != NULL) { StringRelease(s); } s = NULL

and use that.

 
Reply With Quote
 
Shao Miller
Guest
Posts: n/a
 
      06-05-2011
On 6/5/2011 5:52 AM, daknok wrote:
> Hi,
>
> If I want to do simple reference counting for different structures I
> would go like this:
>
> struct String {
> unsigned references;
> char *cString;
> size_t length;
> };
>
> void StringRelease(struct String *str) {
> str->references--;
> if (str->references == 0) {
> free(str->cString);
> free(str);
> }
> }
>
> struct String *StringRetain(struct String *str) {
> str->references++;
> return str;
> }
>
> Though if I have about ten structs, I have ten different functions to
> increase and decrease the reference count.


Your 'struct String' contains a 'cString' pointer, which implies that
someone has to set that member somehow. If you offer an allocator which
allocates both a 'struct String' as well as the data that 'cString' will
point to, a reference-counting de-allocator that has knowledge of the
resource pointed-to by 'cString' seems nicely symmetrical.

Does one 'struct String' "own" the string that its 'cString' member
points to? Or are users allowed to modify the 'cString' member
themselves and point to, let's say, a string literal? You wouldn't want
them to free a string literal, most likely.

If the string is "owned" by the associated 'struct String', then of
course, a nice thing about having an array of some element type is that
you can allocate 'struct String' and the 'char[]' together.

typedef struct String_ String;
struct string_ {
unsigned int references;
size_t current_length;
size_t maximum_length;
char * cString;
char data_[1];
};

Now you can have an allocator that does something like:

String * new_string(size_t maximum_length) {
String * result;
result = malloc(sizeof *result + maximum_length);
if (!result)
return result; /* pass the null pointer value on */
init_string(result, maximum_length, result->data_);
return result;
}

where 'init_string' is something like:

void init_string(String * string, size_t maximum_length, char * cString);

and sets the relevant members (and 'references' to 1, other stuff,
perhaps). Now when your reference-counting de-allocator is ready to
free the 'struct String', its call to 'free' will include deallocating
the trailing 'char[]' that was allocated by the above call to 'malloc'.
This way, the de-allocator doesn't need to free 2 ranges of memory.

> Is it, in some way, possible
> to just provide one function for increasing and one function for
> decreasing the reference count which can be used for all structs with a
> reference count?
>


I think that depends. If your structs contain references to other
objects (which might contain references to other objects, etc.), it
seems that the knowledge for "collapsing" has to go somewhere. If the
struct "owns" all of the resources associated with it, you could:
- Explicitly 'free' each resource when the struct is being de-allocated.
(Knowledge in the struct-specific function.)
- Track all resources with a linked list and walk the list, freeing
items, when the struct is being de-allocated. (Knowledge in the
resource list.)

If a struct doesn't "own" all of the resources associated with it, then
perhaps you extend your reference-counting approach to such resources,
also. But still, the knowledge for what might be referenced by your
struct needs to go somewhere. Perhaps you have a struct-specific,
reference-counting de-allocator which decrements the references for all
of the resources it is referencing. This is a nicely-collapsible chain
of events.

As already suggested by others, if your structures all begin with the
same type of member, you can have a single reference-counting release
function that takes a pointer to it. While this means not having to use
'StringRelease', 'FileRelease', 'UrlRelease', etc. all over the place,
the knowledge of any "sub-resources" still needs to be somewhere;
possibly in a struct-specific function which can be found via a function
pointer.
 
Reply With Quote
 
Eric Sosman
Guest
Posts: n/a
 
      06-05-2011
On 6/5/2011 11:01 AM, daknok wrote:
> [...]
> If the code is written well, this won't be a problem. Even better could
> I write a macro:
>
> SafeStringRelease(s) if (s != NULL) { StringRelease(s); } s = NULL
>
> and use that.


Danger, Will Robinson!

if (x == 42)
SafeStringRelease(string);

Note carefully what happens when `x' is *not* forty-two. (What
you need is known as "the `do { } while(0)' trick.")

Then, too, there's the matter of side-effects:

String *array[42];
...
int i = ...;
// Release all Strings from the i'th onward:
while (i < 42)
SafeStringRelease(array[i++]);

With SafeStringRelease as it stands you'll free only about half
of the strings; a corrected version would free only about a third
and leak another third. Both versions would be likely to do
something weird on or just after the final trip through the loop.

I'm not a big believer in the efficacy of the `s = NULL' part,
for the same reason I don't use a similar construct with free():
You can NULL out one particular pointer to a released thing, but
there's not much hope of finding and NULLing all of them. For
example, what if `s' expands to the name of a function parameter?
You can NULL out the parameter -- the function's local variable --
but you can't get at the argument the caller provided.

--
Eric Sosman
http://www.velocityreviews.com/forums/(E-Mail Removed)d
 
Reply With Quote
 
Gene
Guest
Posts: n/a
 
      06-07-2011
On Jun 5, 7:17*am, Angel <(E-Mail Removed)> wrote:
> On 2011-06-05, daknok <(E-Mail Removed)> wrote:
>
>
>
>
>
> > Hi,

>
> > If I want to do simple reference counting for different structures I
> > would go like this:

>
> > struct String {
> > * * unsigned references;
> > * * char *cString;
> > * * size_t length;
> > };

>
> > void StringRelease(struct String *str) {
> > * * str->references--;
> > * * if (str->references == 0) {
> > * * * * free(str->cString);
> > * * * * free(str);
> > * * }
> > }

>
> > struct String *StringRetain(struct String *str) {
> > * * str->references++;
> > * * return str;
> > }

>
> > Though if I have about ten structs, I have ten different functions to
> > increase and decrease the reference count. Is it, in some way, possible
> > to just provide one function for increasing and one function for
> > decreasing the reference count which can be used for all structs with a
> > reference count?

>
> There are number of ways to do this. One of the easiest (but least
> flexible) is to start all your structures with the same reference
> variable, of the same type, like this:
>
> struct a
> {
> * * * * int ref_count;
> * * * * char *data;
> * * * * char *more_data;
>
> };
>
> struct b
> {
> * * * * int ref_count;
> * * * * int number;
> * * * * int another_number;
>
> };
>
> Now you can safely read the ref_count from any of these structures, for
> example like this:
>
> struct ref_count
> {
> * * * * int ref_count;
>
> };
>
> void increase_refcount(void *data)
> {
> * * * * ((struct refcount *) data)->refcount++;
>
> }
>
> You can safely pass either pointers to struct a or struct b to this
> function, and it will work as expected. The standard guarantees that
> shared fields at the beginning of structures are compatible. In a way,
> this is a primitive C implementation of inheritance.


I asked about this here some time back. The folks who know the
Standard well denied that this is portable. The standard gives you
now way to rely on common prefixes of fields to be laid out the same
way in memory. But you _can_ rely on casts between the first field
and an enclosing struct type to work correctly. So the fully portable
way is this:

typedef enum { StringTag, URLTag, ... } TAG;
typedef unsigned REF_COUNT;

typedef struct {
TAG tag;
REF_COUNT ref_count;
} HEADER, *REF_COUNTED_OBJECT_PTR;

// every kind object needs the same initial header field.
typedef struct string_s {
HEADER hdr[1];
char *text;
unsigned length;
} STRING;

REF_COUNTED_OBJECT_PTR make_string(void)
{
STRING *s = safe_malloc(sizeof(STRING));
s->hdr->tag = StringTag;
s->hdr->ref_count = 0;
s->text = NULL;
s->length = 0;
return (REF_COUNTED_OJBECT_PTR)s;
}

REF_COUNTED_OBJECT_PTR ref (REF_COUNTED_OBJECT_PTR p)
{
p->ref_count++;
return p;
}

void deref (REF_COUNTED_OBJECT_PTR p)
{
if (--p->ref_count == 0)
switch (p->tag) {
case StringTag:
safe_free((STRING*)p);
break;
case ...
}
return p;
}

.... now for example
{
REF_COUNTED_OJBECT_PTR x, s = ref(make_string());
... use s
x = ref(s);
... use x
deref(s);
... yada yada
deref(x); // causes deallocation.
}
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Reference counting and API (const reference vs pointer oriented) mathieu C++ 8 08-31-2008 09:05 AM
counting up instead of counting down edwardfredriks Javascript 6 09-07-2005 03:30 PM
reference counting Tony Johansson C++ 4 05-23-2005 01:28 PM
Reference counting in C++ Kalle Rutanen C++ 0 05-07-2005 12:26 PM
flyweight reference counting ash C++ 1 10-24-2003 10:40 AM



Advertisments