OOC:en:2.6 Another Implementation — Atom

来自 ChinaUnix Wiki

To illustrate what we can do with the constructor and destructor interface we implement atoms. An atom is a unique string object; if two atoms contain the same strings, they are identical. Atoms are very cheap to compare: differ() is true if the two argument pointers differ. Atoms are more expensive to construct and destroy: we maintain a circular list of all atoms and we count the number of times an atom is cloned:

struct String {
    const void * class;         /* must be first */
    char * text;
    struct String * next;
    unsigned count;
};
static struct String * ring;    /* of all strings */
static void * String_clone (const void * _self)
{   struct String * self = (void *) _self;
    ++ self —> count;
    return self;
}

Our circular list of all atoms is marked in ring, extends through the .next com- ponent, and is maintained by the string constructor and destructor. Before the con- structor saves a text it first looks through the list to see if the same text is already stored. The following code is inserted at the beginning of String_ctor():

if (ring)
{    struct String * p = ring;
     do
         if (strcmp(p —> text, text) == 0)
         {   ++ p —> count;
             free(self);
             return p;
         }
     while ((p = p —> next) != ring);
}
else
     ring = self;
self —> next = ring —> next, ring —> next = self;
self —> count = 1;

If we find a suitable atom, we increment its reference count, free the new string object self and return the atom p instead. Otherwise we insert the new string object into the circular list and set its reference count to 1.

The destructor prevents deletion of an atom unless its reference count is decre- mented to zero. The following code is inserted at the beginning of String_dtor():

if (—— self —> count > 0)
     return 0;
assert(ring);
if (ring == self)
     ring = self —> next;
if (ring == self)
     ring = 0;
else
{    struct String * p = ring;
     while (p —> next != self)
         p = p —> next;
     {
         assert(p != ring);
     }
     p —> next = self —> next;
}

If the decremented reference count is positive, we return a null pointer so that delete() leaves our object alone. Otherwise we clear the circular list marker if our string is the last one or we remove our string from the list.

With this implementation our application from section 2.4 notices that a cloned string is identical to the original and it prints

sizeOf(a) == 16
ok
clone?