d3x0r/README.md

## README.md

      
    Raw
  

              README.md
            
          
    Declare Link; 'single and a half'ly-linked lists

hse macros are for linking and unlininking things in a linked list.
The list is basically a singly-linked list, but also references the pointer that
is pointing at the current node.  This simplifies insert/remove operations, because
the specific list that the node is in, is not required.
List heads will always be updated correctly.
A few 'tricks' are available, such as
a) These are deemed dangerous; and uncomprehendable by anyone but the maintainer. use at your own time and expense required to explain WHY these work.
1) when declaring a root node, include another node before it, and it's    simple to make this a circularly linked list.
2) defining DeclareLink at the start of the strcture, the 'me' pointer    also happens to be 'prior', so you can step through the list in both        directions.
struct my_node {
    DeclareLink( struct my_node );
    // ...
 };

// that declares
//      struct my_node *next;  // the next node in list.
//      struct my_node **me;   // address of the pointer pointing to 'me';

declare a root of the list...
//
//  struct my_node *root; // a root of a list of my_node.  It should be initialized to NULL.
//

Allocate one of your nodes, and link to the root...
  struct my_node *newNode = (struct my_node*)malloc( sizeof( *newNode ) );
     // does not require next or me to be initiialized.
  LinkThing( root, newNode );
     // now newNode is in the list.

//
//  to remove from a list
//
  struct my_node *someNode; // this should be a pointer to some valid node.
  UnlinkThing( someNode );
//     The new node is now not in the list.
//


//  To move one node from one list to another
//
   struct my_node *rootAvail;  // available nodes
   struct my_node *rootUsed;   // nodes in use

   struct my_node *someNode; // some node in a list
   someNode = rootAvail; // get first available.
   if( !someNode ) ; // create a new one or abort
      RelinkThing( rootUsed, someNode );
//      'someNode' is removed from its existing list, and added to the 'rootUsed' list.
//


## linkedList.c

// this method can be done with macros only for inline-ability
// can of course wrap any of the macros into a function.


//---------------------- Declare Link; 'single and a half'ly-linked lists -----------------------
// Thse macros are for linking and unlininking things in a linked list.
// The list is basically a singly-linked list, but also references the pointer that
// is pointing at the current node.  This simplifies insert/remove operations, because
// the specific list that the node is in, is not required.
// List heads will always be updated correctly.
//
// A few 'tricks' are available, such as
//     0) These are deemed dangerous; and uncomprehendable by anyone but the maintainer.
//        use at your own time and expense required to explain WHY these work.
//     1) when declaring a root node, include another node before it, and it's
//        simple to make this a circularly linked list.
//     2) defining DeclareLink at the start of the strcture, the 'me' pointer
//        also happens to be 'prior', so you can step through the list in both
//        directions.
//
//
//
// struct my_node {
//    DeclareLink( struct my_node );
//    // ...
// };
//
// that declares
//      struct my_node *next;  // the next node in list.
//      struct my_node **me;   // address of the pointer pointing to 'me';
//
//
//  struct my_node *root; // a root of a list of my_node.  It should be initialized to NULL.
//
//  struct my_node *newNode = (struct my_node*)malloc( sizeof( *newNode ) );
//     // does not require next or me to be initiialized.
//  LinkThing( root, newNode );
//     // now newNode is in the list.
//
//  to remove from a list
//
//  struct my_node *someNode; // this should be a pointer to some valid node.
//  UnlinkThing( someNode );
//     The new node is now not in the list.
//
//  To move one node from one list to another
//
//   struct my_node *rootAvail;  // available nodes
//   struct my_node *rootUsed;   // nodes in use
//
//   struct my_node *someNode; // some node in a list
//   someNode = rootAvail; // get first available.
//   if( !someNode ) ; // create a new one or abort
//   RelinkThing( rootUsed, someNode );
//      'someNode' is removed from its existing list, and added to the 'rootUsed' list.
//


// For Declaring the link structure members for lists
#define DeclareLink( type )  type *next; type **me


/* Link a new node into the list.


   Example
   struct mynode
   {
       DeclareLink( struct mynode );
   } *node;


	struct mynode *list;

   // node allocation not shown.
	LinkThing( list_root, node );
*/
#define LinkThing( root, node )     \
		((( (node)->next = (root) )?        \
	(((root)->me) = &((node)->next)):0),  \
	(((node)->me) = &(root)),             \
	((root) = (node)) )

/* Link a node to the end of a list. LinkThing() inserts the new
 node as the new head of the list.
 this has to scan the list to find the end, so it is a O(n) operation.
 All other linked list operations are O(1)
 */
#define LinkLast( root, type, node ) if( node ) do { if( !root ) \
	{ root = node; (node)->me=&root; } \
	else { type tmp; \
	for( tmp = root; tmp->next; tmp = tmp->next ); \
	tmp->next = (node); \
	(node)->me = &tmp->next; \
	} } while (0)


// put 'Thing' after 'node'
// inserts 'node' after Thing

#define LinkThingAfter( node, thing ) \
	( ( (thing)&&(node))   \
	?(((((thing)->next = (node)->next))?((node)->next->me = &(thing)->next):0) \
	 ,((thing)->me = &(node)->next), ((node)->next = thing))  \
	:((node)=(thing)) )

//
// put 'Thing' before 'node'... so (*node->me) = thing
// similar to LinkThingAfter but puts the new 'thing'
// before the 'node' specified.
#define LinkThingBefore( node, thing ) \
	{  \
thing->next = (*node->me);\
	(*node->me) = thing;    \
thing->me = node->me;       \
node->me = &thing->next;     \
}

// move a list from one list to another.
// unlinks node from where it was, inserts at the head of another.
// this can also be use to reproiritize within the same list.
#define RelinkThing( root, node )   \
	((( node->me && ( (*node->me)=node->next ) )?  \
	node->next->me = node->me:0),(node->next = NULL),(node->me = NULL),node), \
	((( node->next = root )?        \
	(root->me = &node->next):0),  \
	(node->me = &root),             \
	(root = node) )


/* Remove a node from a list. Requires only the node. */
#define UnlinkThing( node )                      \
	((( (node) && (node)->me && ( (*(node)->me)=(node)->next ) )?  \
	(node)->next->me = (node)->me:0),((node)->next = NULL),((node)->me = NULL),(node))

// this has two expressions duplicated...
// but in being so safe in this expression,
// the self-circular link needs to be duplicated.
// GrabThing is used for nodes which are circularly bound
#define GrabThing( node )    \
	((node)?(((node)->me)?(((*(node)->me)=(node)->next)? \
	((node)->next->me=(node)->me),((node)->me=&(node)->next):NULL):((node)->me=&(node)->next)):NULL)

/* Go to the next node with links declared by DeclareLink
 safe iterator macro that tests if node is valid, which returns
 the next item in the list, else returns NULL
 */
#define NextLink(node) ((node)?(node)->next:NULL)

// everything else is called a thing... should probably migrate to using this...
#define NextThing(node) ((node)?(node)->next:NULL)


struct userNode {
	declareLink( struct userNode );
	int userNodeData;
};

struct userNode* CreateNode( void ) {
	struct userNode* node = malloc( sizeof( *node ) );
	node->next = 0;
	node->me = &node->next; // probably overwritten later.

	/* other user node initiaialization */

	return node;
}


## linkedList.js
// o refers to the user object.


// create a node containing user object.
function Node( o ) {
	if( this instanceof Node ) throw new Error( "please do not call this with new" );
	return {
		next : null,
		me : null,
		o:o,
	}
}

function linkNode( root, rootField, node ) {
	if( node.next = root[rootField] ) {
		node.next.me.ref = node;
	}
	node.me = { ref: root, field:rootField };

}

// the magic unlink function.  So easy.
function unlinkNode( node ) {
	node.me.ref[node.me.field] = node.next;
}

function testList( ) {
  var localObject = {
    rootNode : null
  };

  linkNode( localObject, "rootNode, node );
  var rootNode = null;
}

	// this method can be done with macros only for inline-ability
	// can of course wrap any of the macros into a function.



	//---------------------- Declare Link; 'single and a half'ly-linked lists -----------------------
	// Thse macros are for linking and unlininking things in a linked list.
	// The list is basically a singly-linked list, but also references the pointer that
	// is pointing at the current node. This simplifies insert/remove operations, because
	// the specific list that the node is in, is not required.
	// List heads will always be updated correctly.
	//
	// A few 'tricks' are available, such as
	// 0) These are deemed dangerous; and uncomprehendable by anyone but the maintainer.
	// use at your own time and expense required to explain WHY these work.
	// 1) when declaring a root node, include another node before it, and it's
	// simple to make this a circularly linked list.
	// 2) defining DeclareLink at the start of the strcture, the 'me' pointer
	// also happens to be 'prior', so you can step through the list in both
	// directions.
	//
	//
	//
	// struct my_node {
	// DeclareLink( struct my_node );
	// // ...
	// };
	//
	// that declares
	// struct my_node *next; // the next node in list.
	// struct my_node **me; // address of the pointer pointing to 'me';
	//
	//
	// struct my_node *root; // a root of a list of my_node. It should be initialized to NULL.
	//
	// struct my_node newNode = (struct my_node)malloc( sizeof( *newNode ) );
	// // does not require next or me to be initiialized.
	// LinkThing( root, newNode );
	// // now newNode is in the list.
	//
	// to remove from a list
	//
	// struct my_node *someNode; // this should be a pointer to some valid node.
	// UnlinkThing( someNode );
	// The new node is now not in the list.
	//
	// To move one node from one list to another
	//
	// struct my_node *rootAvail; // available nodes
	// struct my_node *rootUsed; // nodes in use
	//
	// struct my_node *someNode; // some node in a list
	// someNode = rootAvail; // get first available.
	// if( !someNode ) ; // create a new one or abort
	// RelinkThing( rootUsed, someNode );
	// 'someNode' is removed from its existing list, and added to the 'rootUsed' list.
	//


	// For Declaring the link structure members for lists
	#define DeclareLink( type ) type next; type *me


	/* Link a new node into the list.


	Example
	struct mynode
	{
	DeclareLink( struct mynode );
	} *node;


	struct mynode *list;

	// node allocation not shown.
	LinkThing( list_root, node );
	*/
	#define LinkThing( root, node ) \
	((( (node)->next = (root) )? \
	(((root)->me) = &((node)->next)):0), \
	(((node)->me) = &(root)), \
	((root) = (node)) )

	/* Link a node to the end of a list. LinkThing() inserts the new
	node as the new head of the list.
	this has to scan the list to find the end, so it is a O(n) operation.
	All other linked list operations are O(1)
	*/
	#define LinkLast( root, type, node ) if( node ) do { if( !root ) \
	{ root = node; (node)->me=&root; } \
	else { type tmp; \
	for( tmp = root; tmp->next; tmp = tmp->next ); \
	tmp->next = (node); \
	(node)->me = &tmp->next; \
	} } while (0)


	// put 'Thing' after 'node'
	// inserts 'node' after Thing

	#define LinkThingAfter( node, thing ) \
	( ( (thing)&&(node)) \
	?(((((thing)->next = (node)->next))?((node)->next->me = &(thing)->next):0) \
	,((thing)->me = &(node)->next), ((node)->next = thing)) \
	:((node)=(thing)) )

	//
	// put 'Thing' before 'node'... so (*node->me) = thing
	// similar to LinkThingAfter but puts the new 'thing'
	// before the 'node' specified.
	#define LinkThingBefore( node, thing ) \
	{ \
	thing->next = (*node->me);\
	(*node->me) = thing; \
	thing->me = node->me; \
	node->me = &thing->next; \
	}

	// move a list from one list to another.
	// unlinks node from where it was, inserts at the head of another.
	// this can also be use to reproiritize within the same list.
	#define RelinkThing( root, node ) \
	((( node->me && ( (*node->me)=node->next ) )? \
	node->next->me = node->me:0),(node->next = NULL),(node->me = NULL),node), \
	((( node->next = root )? \
	(root->me = &node->next):0), \
	(node->me = &root), \
	(root = node) )


	/* Remove a node from a list. Requires only the node. */
	#define UnlinkThing( node ) \
	((( (node) && (node)->me && ( (*(node)->me)=(node)->next ) )? \
	(node)->next->me = (node)->me:0),((node)->next = NULL),((node)->me = NULL),(node))

	// this has two expressions duplicated...
	// but in being so safe in this expression,
	// the self-circular link needs to be duplicated.
	// GrabThing is used for nodes which are circularly bound
	#define GrabThing( node ) \
	((node)?(((node)->me)?(((*(node)->me)=(node)->next)? \
	((node)->next->me=(node)->me),((node)->me=&(node)->next):NULL):((node)->me=&(node)->next)):NULL)

	/* Go to the next node with links declared by DeclareLink
	safe iterator macro that tests if node is valid, which returns
	the next item in the list, else returns NULL
	*/
	#define NextLink(node) ((node)?(node)->next:NULL)

	// everything else is called a thing... should probably migrate to using this...
	#define NextThing(node) ((node)?(node)->next:NULL)


	struct userNode {
	declareLink( struct userNode );
	int userNodeData;
	};

	struct userNode* CreateNode( void ) {
	struct userNode* node = malloc( sizeof( *node ) );
	node->next = 0;
	node->me = &node->next; // probably overwritten later.

	/* other user node initiaialization */

	return node;
	}
	// o refers to the user object.


	// create a node containing user object.
	function Node( o ) {
	if( this instanceof Node ) throw new Error( "please do not call this with new" );
	return {
	next : null,
	me : null,
	o:o,
	}
	}

	function linkNode( root, rootField, node ) {
	if( node.next = root[rootField] ) {
	node.next.me.ref = node;
	}
	node.me = { ref: root, field:rootField };

	}

	// the magic unlink function. So easy.
	function unlinkNode( node ) {
	node.me.ref[node.me.field] = node.next;
	}

	function testList( ) {
	var localObject = {
	rootNode : null
	};

	linkNode( localObject, "rootNode, node );
	var rootNode = null;
	}