📄 hilbert.c
字号:
//
// History: John Skilling 9 Mar 1996, 20 Apr 2001
//-----------------------------------------------------------------------------
//
int FreeLink( // O 0 (or -ve debug code)
Node* psLink) // I O Linked list
{
if( psLink )
{
if( psLink->atom ) FREE( psLink->atom->Label )
FREE( psLink->atom )
FREE( psLink->parent )
psLink->parent = NULL;
psLink->atom = NULL;
psLink->depth = 0;
}
return 0;
}
//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
// Function: ResetLink
//
// Purpose: Rellocate memory, if initial guess in SetLink was inadequate
//
// History: John Skilling 9 Mar 1996, 6 Feb 1998, 12 Apr 2001
//-----------------------------------------------------------------------------
//
static int ResetLink( // O 0, or -ve error code
pNode psLink) // I O Linked list
{
int NMAX = psLink->depth; // Initial # allowed atoms
pAtom List = psLink->atom; // Old list of atoms
pNode Nodes = psLink->parent; // Old nodes of tree
int Ndim = psLink->number; // # words per label
int MORE = NMAX + NMAX/2; // Extended # allowed atoms
pAtom ListX = NULL; // Replacement list of atoms
pNode NodesX = NULL; // Replacement nodes of tree
int i; // Local counter
int j; // Counter
int CALLvalue = 0;
// Allocate new tree
CALLOC( NodesX, MORE+MORE+1, Node )
CALLOC( ListX, MORE+1, Atom )
CALLOC( ListX->Label, Ndim * (MORE+1), coord_t )
for( i = 1; i <= MORE; ++i )
ListX[i].Label = ListX[i-1].Label + Ndim;
// Copy across
for( i = 0; i <= NMAX + NMAX; ++i )
NodesX[i] = Nodes[i];
for( j = 0; j < Ndim; j++ )
ListX[0].Label[j] = List[0].Label[j];
for( i = 1; i <= NMAX; ++i )
for( j = 0; j < Ndim; j++ )
ListX[i].Label[j] = List[i].Label[j];
// Correct all internal pointers
for( i = 0; i <= NMAX; ++i )
{
ListX[i].Base = NodesX + (List[i].Base - Nodes);
ListX[i].Free = NodesX + (List[i].Free - Nodes);
}
for( i = NMAX + 1; i <= MORE; ++i )
{
ListX[i].Base = &NodesX[i+i-1];
ListX[i].Free = &NodesX[i+i];
}
for( i = 0; i <= NMAX + NMAX; ++i )
{
if( NodesX[i].parent )
NodesX[i].parent = NodesX + (Nodes[i].parent - Nodes);
if( NodesX[i].lo )
NodesX[i].lo = NodesX + (Nodes[i].lo - Nodes);
if( NodesX[i].hi )
NodesX[i].hi = NodesX + (Nodes[i].hi - Nodes);
NodesX[i].atom = ListX + (Nodes[i].atom - List);
}
psLink->atom = ListX;
psLink->parent = NodesX;
psLink->depth = MORE;
// Free old tree
FREE( List->Label )
FREE( List )
FREE( Nodes )
return 0;
Exit:
FREE( ListX->Label )
FREE( ListX )
FREE( NodesX )
return CALLvalue;
}
//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
// Function: InsAtom
//
// Purpose: Update list to insert new atom, if new label is distinct.
// Split node to left, forking to new and previous nodes,
// then re-balance the tree.
//
// Notes: After InsAtom, the serial number of the inserted atom is Natoms-1
//
// History: John Skilling 6 Mar 1996, 7 Oct 1996, 15 Dec 1997, 21 Jan 1998
// 6 Feb 1998, 12 Apr 2001, 10 Sep 2001, 22 Jan 2003
//=============================================================================
// Original configuration Final configuration before balancing
//
// \ /: /: \ /: /:
// ____ ____ ____ ____ ____ ____
// ___|Node|___|Node|___|Node|___ ___|Node| |Node| |Node|___
// |____| |____| |____| |____| |____| |____|
// : : \ /: \ / :
// : : \ /: \ / :
// ____ ____ ____ ____ :
// |Atom| |Atom| |New2|___|New1| :
// | x- | | x+ | |____| |____| :
// |____| |____| : : :
// : : :
// ____ ____ ____ ____
// | | |Atom| | | |Atom|
// InsAtom | x | > x- | x- | | x | | x+ |
// |____| |____| |____| |____|
//
//-----------------------------------------------------------------------------
//
int InsAtom( // O 1 = accept,
// 0 = reject because same label,
// -ve = error
pAtom insertion, // I New atom to be inserted into list
pNode psLink) // I O Linked list
{
int Natoms; // # inserted atoms
pAtom patom; // Copy insertion atom into list
pAtom List; // List of atoms
pNode node; // Node of tree
pNode New1; // Available node for inclusion in tree
pNode New2; // Available node for inclusion in tree
int Ndim; // # words per label
int j; // Counter
int CALLvalue = 0;
if( psLink->number <= 0 )
return CALLvalue;
// Ensure memory is available
if( psLink->depth < 2 )
return E_TREEDATA;
if( NumAtoms(psLink) >= psLink->depth )
CALL( ResetLink(psLink) )
// Goto base node at or just left of insertion
List = psLink->atom;
node = List->Free;
Ndim = psLink->number;
// log(N) loop
while( node->depth )
node = (CmpLabel(insertion->Label, node->hi->atom->Label, Ndim) < 0)
? node->lo : node->hi;
if( CmpLabel(insertion->Label, node->atom->Label, Ndim) == 0 )
{
if( CmpLabel(insertion->Label, psLink->atom->Label, Ndim) > 0 )
return 0; // Avoid overlapping existing user atom
if( node->lo ) // but allow one user atom at Label=0
return 0;
}
Natoms = NumAtoms(psLink) + 1;
// Copy atom to vacancy at top of list
patom = List + Natoms;
New1 = patom->Free;
New2 = patom->Base;
for( j = 0; j < psLink->number; j++ )
patom->Label[j] = insertion->Label[j];
// Reconnect base with additional node and twig
patom->Free = NULL;
patom->Base = New1;
New1->atom = patom;
New1->parent = node;
New1->hi = node->hi;
if( New1->hi )
New1->hi->lo = New1;
New1->lo = New2;
New1->depth = 0;
New1->number = 1;
node->hi = New1;
node->atom->Base = New2;
New2->atom = node->atom;
New2->parent = node;
New2->hi = New1;
New2->lo = node->lo;
if( New2->lo )
New2->lo->hi = New2;
New2->depth = 0;
New2->number = 1;
node->lo = New2;
// Update depth information back up tree, and equilibrate accordingly
Balance(New1);
return 1; // accepted
Exit:
return CALLvalue;
}
//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
// Function: DelAtom
//
// Purpose: Update list to delete an atom.
// Cut out specified node and its parent, then re-balance the tree.
//
// History: John Skilling 6 Mar 1996, 6 Feb 1998, 22 Jan 2003, 2 Dec 2003
//=============================================================================
// Original configuration Final configuration before balancing
// (sibling can be to left or right) (sibling can be same as lo or hi)
//
// / \.
// ____ \.
// | del| \.
// |____| \.
// / \. \.
// / \. \.
// ____ \. ____
// |sibl| \. |sibl|
// |____| \. |____|
// / \ \. / \.
// \.
// \ \. \ /
// ____ ____ ____ ____ ____
// ___| lo |___|kill|___| hi |___ ___| lo |___| hi |___
// |____| |____| |____| |____| |____|
// : : : : :
// : : : : :
// ____ ____ ____ ____ ____
// |Atom| | | |Atom| |Atom| |Atom|
// | x- | | x | | x+ | | x- | | x+ |
// |____| |____| |____| |____| |____|
// deletion
//-----------------------------------------------------------------------------
//
int DelAtom( // O 0 (or -ve error code)
pAtom deletion, // I New atom to be deleted from list
pNode psLink) // I O Linked list
{
pAtom xatom; // Interacting atom
pAtom List; // List of atoms
pAtom Top; // Top of list of atoms
pNode node; // Current node
pNode kill; // Node on tree base, to be killed
pNode del; // kill->parent, also to be killed
pNode sibling; // del->otherchild
int Natoms; // Decremented # atoms
int j; // Counter
if( psLink->number <= 0 )
return 0;
Natoms = NumAtoms(psLink);
// Ensure deletion is from list
List = psLink->atom;
Top = List + Natoms;
if( deletion <= List || deletion > Top )
return E_TREEDATA;
// Cut node out of base of tree
kill = deletion->Base;
if( kill->hi )
kill->hi->lo = kill->lo;
kill->lo->hi = kill->hi;
// Cut kill and del out of the tree
del = kill->parent;
sibling = ( del->hi == kill ) ? del->lo : del->hi;
xatom = sibling->atom;
sibling->parent = del->parent;
if( del->parent )
{
if( del->parent->hi == del )
del->parent->hi = sibling;
else
del->parent->lo = sibling;
// Replace all references to killed atom with refs to its sibling
for( node = del; node->atom == deletion; node = node->parent )
node->atom = xatom;
}
else
{
List->Free = sibling;
}
// Copy atom at top of list into freed slot to keep list storage consecutive
if( deletion < Top )
{
xatom = List + Natoms;
for( node = xatom->Base; node->atom == xatom; node = node->parent )
node->atom = deletion;
deletion->Base = xatom->Base;
deletion->Free = xatom->Free;
for( j = 0; j < psLink->number; ++j )
deletion->Label[j] = xatom->Label[j];
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -