Verstable vs. CC map

[duke13137]

Hi - CC documentation has a phase:

• Duplicating a container handle via assignment and then operating on the duplicate will invalidate the original.Hence, only create a duplicate via assignment (including through function parameters and return values) if you have finished with the original.

My understanding, in summary, is that CC container handles move unique ownership w.r.t assignment and parameter passing.

I'm aware that Verstable and CC hashmap have a similar design underneath. However, I don't observe Verstable has the same semantic, rather its struct values (ie. map_int_str m2 = m) behaves more or less like shared ownership (however no RC w.r.t cleanup call).

Is above understanding accurate?

Thanks!

[JacksonAllan]

Hello!

The semantics of copying containers and container handles are actually much the same with both libraries. In both cases, a container should be treated as a struct containing pointers to memory that it is responsible for allocating and freeing. That’s because in Verstable, the handle actually is a struct, and in CC, the handle is a pointer that the library effectively treats like a struct with one (pointer) member.

What this means is that if you duplicate a container handle through assignment, you create two handles, each containing its own pointer to the same data buffer. This will work okay until you mutate the container through one of the handles (e.g. by inserting data). At that point, if the container reallocates its internal memory or (in the case of Verstable) changes metadata like the key count, only one handle’s pointer and/or metadata will get updated, and trying to access the container through the other handle will fail in all kinds of unpredictable ways. These semantics are, by the way, the same as those of any generic container library in which a container is a struct (e.g. typedef struct { size_t size; size_t capacity; int *data_buffer; } int_vector;), if that helps…

Hence, with either library, it usually doesn’t make sense to copy container handles. If we want to create an actual copy of a container and its data, we should use cc_init_clone/vt_init_clone, which creates a copy of the container including a shallow copy of its data (I leave the deep copying of the data, if necessary, up to the user). If, on the other hand, we want to create a second reference to an existing container, then we need to create a pointer to the original handle rather than duplicating the handle.

But there are two cases in which it does make sense to copy a container handle:

• We’re creating a container inside a function and then returning it from the function via the return value. In this case, the original handle obviously goes out of scope when the function exists. Here is what that might look like with Verstable (Godbolt):

  #include <stdlib.h>
  
  #define NAME int_set
  #define KEY_TY int
  #include "verstable.h"
  
  int_set make_set_0_to_9( void )
  {
    int_set our_set;
    vt_init( &our_set );
  
    for( int i = 0; i < 10; ++i )
      if( vt_is_end( vt_insert( &our_set, i ) ) )
      {
        // Out of memory, so just abort.
        vt_cleanup( &our_set );
        exit( 1 );
      }
  
    return our_set;
  }
  
  int main( void )
  {
    int_set our_set = make_set_0_to_9();
  
    // Do things with our_set...
  
    vt_cleanup( &our_set );
  }

• We’re inserting a container into another container that will call a destructor we defined. In this case, if the insertion succeeds, then the latter container effectively takes ownership of the former and will clean it up (i.e. free it via the destructor) when necessary, and the original handle should not be used again. Here is what that might look like with Verstable (Godbolt):

  #include <assert.h>
  #include <stdlib.h>
  
  #define NAME int_set
  #define KEY_TY int
  #include "verstable.h"
  
  void int_set_dtor( int_set val )
  {
    vt_cleanup( &val );
  }
  
  #define NAME int_to_int_set_map
  #define KEY_TY int
  #define VAL_TY int_set
  #define VAL_DTOR int_set_dtor
  #include "verstable.h"
  
  int main( void )
  {
    int_set our_set;
    vt_init( &our_set );
    if( vt_is_end( vt_insert( &our_set, 123 ) ) )
    {
      // Out of memory, so just abort.
      vt_cleanup( &our_set );
      exit( 1 );
    }
  
    int_to_int_set_map our_map;
    vt_init( &our_map );
    if( vt_is_end( vt_insert( &our_map, 456, our_set ) ) )
    {
      // Out of memory, so just abort.
      vt_cleanup( &our_set );
      vt_cleanup( &our_map );
      exit( 1 );
    }
  
    // At this point, our_map has taken ownership of our_set and will clean it up when necessary by
    // calling the destructor we specified via VAL_DTOR when creating the int_to_int_set_map type.
    // We should NOT use the our_set handle again.
    // Rather, we should access the set via the iterator we get by calling vt_get on the map:
    int_to_int_set_map_itr our_itr = vt_get( &our_map, 456 );
    if( vt_is_end( vt_insert( &our_itr.data->val, 789 ) ) )
    {
      // Out of memory, so just abort.
      vt_cleanup( &our_map );
      exit( 1 );
    }
    // Just beware that mutating our_map (e.g. by inserting new key-value pairs) will invalidate
    // existing iterators.
  
    // This line just proves how the our_set handle has become invalid and unusable because its
    // metadata (and potentially its internal pointer) is now out of sync.
    assert( vt_size( &our_set ) == 1 && vt_size( &our_itr.data->val ) == 2 );
  
    vt_cleanup( &our_map );
  }

  Both libraries behave basically the same here, although there are some API differences (e.g. in CC, rather than specifying a destructor for int_to_int_set_map's value type, we would specify a destructor for the int_set type and then any container using it as its key or value ("element", in CC's terminology) type would deduce and call the destructor automagically.

So, in summary, neither CC nor Verstable has any concept of shared handles to the same container. In either library, once a handle (a struct in the case of Verstable and a pointer-treated-like-a-struct in the case of CC) has been copied one way or another, the original becomes invalid and must be discarded. If we need additional references to a container whose handle exists somewhere on the stack or heap, we can create pointers to the handle. If the handle exists as a key or value of another container, then we can create iterators, which are themselves subject to iterator invalidation rules (for Verstable, for example, we wouldn't want to store an iterator to a key-value pair; rather, we would store the key and perform a lookup whenever we need to access the value).

Does all that help clarify the situation?