Documentation Project 1
sack::containers::sets::genericset_tag Structure

Generic sets are good for tracking lots of tiny structures. 


They track slabs of X structures at a time. They allocate a slab of X structures with an array of X bits indicating whether a node is used or not. The structure overall has how many are used, so once full, a block can be quickly checked whether there is anything free. Then when checking a block that might have room, the availablility is checked 32 bits at a time, until a free spot is found. 

Sets of 1024 members of x,y coordinates for example are good for this sort of storage. the points are often static, once loaded they all exist until none of them do. This storage has gross deletion methods too, quickly evaporate all allocated chunks. Storing tiny chunks in a slab is more efficient because every allocation method has some sort of tracking associated with it - an overhead of having it. Plus, when operating on sets of data, a single solid slab of exatly the structures you are working with is more efficient to cache.

struct genericset_tag {
  struct genericset_tag * next;
  struct genericset_tag ** me;
  _32 nUsed;
  _32 nBias;
  _32 bUsed[1];
struct genericset_tag * next; 
wow might be nice to have some flags... first flag - bSetSet - meaning that this is a set of sets of the type specified... 
struct genericset_tag ** me; 
This is the pointer that's pointing at the pointer pointing to me. (did you get that?) See DeclareLink
_32 nBias; 
hmm if I change this here? we're hozed... so.. we'll do it anyhow :) evil - recompile please 
_32 bUsed[1]; 
after this p * unit must be computed 

This represents the basic generic set structure. Addtional data is allocated at the end of this strcture to fit the bit array that maps usage of the set, and for the set size of elements.

struct treenode_tag {
    _32 treenode_data;  // abitrary structure data
typedef struct treenode_tag TREENODE;
DeclareSet( TREENODE );

The important part of the prior code is the last two lines. 

#define MAX<your type name>SPERSET <how many> 

This defines how many of your structure are kept per set block. 

The DeclareSet( type ) declares a typedefed structure called 'struct type##set_tag', 'name##SET', and '*P##name##SET'; in the above case, it would be 'struct TREENODEset_tag', 'TREENODESET', and 'PTREENODESET'. 


Then to actually use the set...

// declare a set pointer with one of the magic names.
// get a node from the set.
TREENODE *node = GetFromSet( TREENODE, nodeset );


Notice there is no CreateSet, getting a set member will create the set as required. Many operations may expend the set, except for GetUsedSetMember which will only result with members that are definatly in the set. Accesses to the set are all prefixed by the type name the set was created with, 'TREENODE' in this example.

DeleteFromSet( TREENODE, nodeset, node );
node = GetFromSet( TREENODE, nodeset );
   int index = GetMemberIndex( TREENODE, nodeset, node );


The accessor macros take care of expanding several parameters that require sizeof structure expansion.

Copyright (c) 2010. All rights reserved.
What do you think about this topic? Send feedback!