User Manual: Code: data.c
From FLUX
(Return to Code or the User Manual)
data.c contains low-level interface routines for the basic structures in FLUX. Here the components of the package are separated by major function.
The data structures are described in more detail on their own page.
Contents |
constructors/destructors
Although FLUX is written in C rather than some object-oriented language, it does manipulate structured data that require initialization, and therefore has constructors and destructors for each data type. Use the appropriate constructor to generate new dynamic data structures, and the appropriate destructor (rather than just free()) to get rid of it.
new_fluxon
FLUXON *new_fluxon(NUM flux, FLUX_CONCENTRATION *c1, FLUX_CONCENTRATION *c2, long label, char plasmoid)
Creates a new fluxon linking concentration c1 (source) to c2 (sink), with flux units of magnetic flux. The new fluxon contains no vertices. The label should be unique. If the fluxon is a plasmoid, c1 and c2 should be the plasmoid placeholder concentrations in the WORLD (though that is for bookkeeping only: the code will work if they are not), and the plasmoid flag should be set.
Currently, the plasmoid flag and the flux parameter are ignored -- the flux parameter is entered into the fluxon data structure, but ignored by the force law routines; and the plasmoid flag is simply ignored.
delete_fluxon
void delete_fluxon (FLUXON *f)
Deletes a fluxon completely, by first deleting all of its vertices with delete_vertex and then unlinking the fluxon from the trees of which it is a member. At the end the fluxon is deallocated and should no longer be used.
new_vertex
VERTEX *new_vertex(long label, NUM x, NUM y, NUM z, FLUXON *fluxon)
Creates a new vertex at the given x,y,z location, and associates it with a particular fluxon. (You can create an unassociated vertex by passing NULL into fluxon.) The vertex is initialized in the sense that its various pointers are NULL and not pointing into hyperspace, and it is linked into the worldwide vertex tree -- but it is not linked into the fluxon's vertex list -- for that you must use one of the add_vertex routines on your shiny new vertex.
If you feed in a nonzero label, then new_vertex will create a VERTEX structure with that label. If label is zero, then new_vertex will create a (simulation-wide) unique label for the new vertex. In FLUX versions through 2.2, the labels were created in numeric order; however, this caused problems with reading and manipulating very large simulations, because numeric order addition of new labels is pessimal for tree maintenance. As of Spring 2009, new vertices are created with random id numbers, which simplifies tree maintenance.
delete_vertex
void delete_vertex(VERTEX *v)
This cleanly unlinks a vertex from the world structure (by calling unlink_vertex, below), and deallocates it. There are some nuances in how unlink_vertex works, so if you're doing anything tricky, check unlink_vertex and examine the code in (e.g.) fluxon_auto_open, over in model.c.
new_flux_concentration
FLUX_CONCENTRATION *new_flux_concentration(WORLD *world, NUM x, NUM y, NUM z, NUM flux, long label)
Creates a new flux concentration (a new fluxon anchorpoint) at the given x, y, z logation. The flux concentration contains flux units of magnetic flux -- positive for north poles, negative for south poles. The concentration gets linked into the world's all-concentrations tree.
new_world
WORLD *new_world()
Creates a new simulation arena. Takes no arguments.
initializers
unlink_vertex
void unlink_vertex(VERTEX *v)
This is a helper routine for delete_vertex (above), but may be useful standalone. This excises a vertex from the entire world, including extricating it from the web of neighbor relations. In particular, it follows every neighbor/nearby link and removes the given vertex from the nearby/neighbor lists of the neighbors. The surrounding vertices on the same fluxon are linked together, and the next/prev and line pointers are set to NULL. After unlink_vertex, the vertex is ready to be deallocated.
Because unlink_vertex unlinks the VERTEX from its parent FLUXON, there are some cases that are particularly tricky. If you unlink the VERTEX from the surrounding linked list first, for example, unlink_vertex will assume that it is a start or end vertex for the fluxon as a whole, and clear the start and end fields of the FLUXON itself. If you are going to do anything like that, check the plasmoid case in fluxon_auto_open, in data.c.
add_vertex_pos
int add_vertex_pos(FLUXON *f, long pos, VERTEX *v)
Adds a new, not-yet-linked vertex to the linked list in the given fluxon, at the given position. The position is found by walking along the linked list of vertices in the fluxon. Nonnegative numbers count from the very beginning of the fluxon, with 0 being anchored at the flux concentration of origin. Negative numbers count from the very end of the fluxon, with -1 being anchored at the flux concentration of demise.
Returns zero on success, or an arcane error code (use the source, Luke!) on failure.
add_vertex_after
int add_vertex_after(FLUXON *f, VERTEX *lucy, VERTEX *v)
Links a shiny new vertex v into the fluxon f, immediately after the vertex
lucy in the linked list. lucy must exist. You can add v
to the very beginning of the fluxon by passing in NULL for lucy.
The return value is zero on success, or a cryptic error code on failure.
clear_links
void clear_links(LINKS *links)
Just zeroes out (initializes) a set of tree links. Don't do this to a data structure that is already linked into a tree! Should only be called on freshly allocated LINKS structures (as in a new FLUXON, VERTEX, or what-have-you).
Label modification
The base data structures (VERTEX, FLUXON, and FLUX_CONCENTRATION) can be referenced by unique integer labels rather than memory location, and the Perl interface library uses that ability extensively. Relabeling a structure requires re-inserting it into the binary trees in which it is indexed. These routines handle that, and also check for ambiguous labeling - if you want to relabel a data structure, use them.
vertex_relabel
int vertex_relabel(VERTEX *v, long newlabel)
Changes v to have label newlabel, and relinks it appropriately. Prevents ambiguous labeling between vertices. Returns 0 on success, nonzero on failure.
fluxon_relabel
int fluxon_relabel(FLUXON *f, long newlabel)
Changes f to have label newlabel, and relinks it appropriately. Prevents ambiguous labeling between fluxons. Returns 0 on success, nonzero on failure.
concentration_relabel
<code>int concentration_relabel(FLUX_CONCENTRATION *fc, long newlabel)
Changes fc to have label newlabel, and relinks it appropriately. Prevents ambiguous labeling between flux concentrations. Returns 0 on success, nonzero on failure. Avoid relabeling concentrations with small negative labels, becuase they are generally magical (associated with particular boundary conditions such as plasmoid or open bondaries).
Tree manipulation
A lot of the structures in FLUX are accessible via trees. There is a generic tree] structure (LINKS) that is used in several places through the code. Because any given data structure within FLUX might be linked into several trees, all of the tree routines require both a generic data pointer and a link offset that gives the offset between the start of the generic data and the LINKS structure embedded within it.
Otherwise, it is a fairly standard collection of balanced-tree handlers.
Tree data structures are much faster to manipulate (in the typical case) than linked lists or other dynamic data structures. The FLUX trees sort stuff based on the long-int label that is attached to each data structure.
clear_links
<code>void clear_links(LINKS *links)
Zeroes out a links structure.
tree_top
void *tree_top(void *tree, int link_offset)
Returns the root of the tree.
tree_find
void *tree_find(void *tree, long label, int label_offset, int link_offset)
Finds a pointer to the tree node with a given long-int label. You have to supply not just the offset to the LINKS structure but also the offset to the label itself within each tree node. Returns NULL if no such node exists.
tree_walk
long tree_walk(void *tree, int label_offset, int link_offset, long ((*func)()))
Just a convenience function for tree_walker, below.
tree_walker
long tree_walker(void *tree, int label_offset, int link_offset, long ((*func)()), int depth)
This is a generic execute-something-on-the-whole-tree routine. You feed in a function pointer, and the function gets called once per node of the tree, in label order. It's called as func(void *node, int depth) on each iteration of the walker. Such functions are called "springboards" within the code. The implementation is a little awkward: if your function to be executed requires any parameters other than the node itself, then you must allocate a global variable, fill it with parameters in your main routine, and then declare a separate springboard routine that uses the global variable. A good example is world_update_neighbors, in model.c.
tree_insert
void *tree_insert(void *root, void *item, int label_offset, int link_offset)
Inserts a node into a tree, with no extras (the tree is allowed to get unbalanced).
tree_binsert
void *tree_binsert(void *root, void *item, int label_offset, int link_offset)
Inserts a node into a tree, and rebalances if it is getting out of balance.
tree_balance_check
char tree_balance_check(void *foo, int link_offset)
Figures whether a tree appears balanced or not. Allows up to 30% slop in the ratio of the left and right branches.
tree_balance
void *tree_balance(void *tree, int label_offset, int link_offset)
Er, balances a tree. Because the root of the tree might change, it returns a void * that points to the new root.
tree_unlink
void *tree_unlink(void *data, int label_offset, int link_offset)
Removes a node from the tree, clearing the associated LINKS structure. Because the root of the tree might change, it returns a void * that points to the new root.
Dumblist manipulation
Dumblists are extensible arrays. Each dumblist points to some dynamically allocated memory (an array of void *'s), and keeps track of both how many items it has and how many memory slots there are. If you use the dumblist_add routine to put new things in the list, then more memory is automagically allocated when needed. There's no straightforward to shrink a dumblist -- they just grow to the high water mark, and stay there. You need to think about that carefully when working with scratch spaces -- it's easy to suck up huge quantities of memory by making (for example) a large scratch space associated with every individual VERTEX. Scratch spaces (like the neighbor-candidate counting space) are best kept as globals -- then you can copy out shorter copies (like the actual reduced neighbor list) as needed.
The stuff in the DUMBLIST is just a collection of pointers -- implemented as void *'s -- that point off to whatever object you want. Strong typing is for people with weak minds! :-)
Dumblists are mainly used for tracking the neighbor lists of each VERTEX in the simulation.
To delete an item from a DUMBLIST you can either use one of the removal codes (dumblist_delete or dumblist_rm, or set the item to NULL and subsequently call dumblist_crunch. The latter form may be better for doing large numbers of deletions at once. Then again, it may not.
allocation, de-allocation
new_dumblist
DUMBLIST *new_dumblist()
Dynamically allocates a new DUMBLIST and initializes it. This isn't used so much -- most of the DUMBLISTs are themselves part of other data structures and hence are allocated automatically. Most new_<foo> routines use dumblist_init, below.
dumblist_init
void dumblist_init(DUMBLIST *foo)
Just sets all the counts to zero and the dynamic memory pointer to NULL. You should call this whenever you allocate a new DUMBLIST as part of another structure.
dumblist_clear
void dumblist_clear(DUMBLIST *foo)
Just sets the element count to zero, leaving everything else as-is. You should probably call this (rather than setting n=0 manually) in case DUMBLISTs ever become less, well, dumb.
free_dumblist
void free_dumblist(DUMBLIST *foo)
Frees both the stuff array and the DUMBLIST itself.
dumblist_quickadd
void dumblist_quickadd(DUMBLIST *dl, void *a)
Adds a new void * to the end of the DUMBLIST's list, without regard to whether it is already in the list (duplicates allowed).
void dumblist_add(DUMBLIST *dl, void *a)
Adds a new void * to the end of the DUMBLIST's list, with duplication checking (no duplicates allowed). Slower than quickadd because it does a linear search through the existing elements.
dumblist_delete
void dumblist_delete(DUMBLIST *dl, void *a)
Removes all copies of a particular void * from a DUMBLIST. It is not an error to ask to delete something that is not already in the DUMBLIST -- that is an expensive no-op. Works by scanning every element and calling dumblist_rm where needed.
dumblist_rm
void dumblist_rm(DUMBLIST *dl, int i)
Removes the ith element of the dumblist, crunching the remaining elements down into the remaining space. This is faster toward the end of the list and slower toward the beginning.
dumblist_grow
void dumblist_grow(DUMBLIST *dl, int size)
Grows a dumblist to be able to hold the number of elements given in size. The actual space allocated is actually 50% larger, to allow room to grow. Normally this is called by dumblist_add as needed, but you can avoid the need for multiple calls (which can get expensive) by calling it in advance of a loop that adds new material.
Sorting
dumblist_qsort
void **dumblist_qsort(void **l, int n, void **wk_start)
Implements the O(nlogn) Quicksort (recursively) on the list, calling a supplied comparator function that is placed into a global static function pointer. You should probably not call qsort yourself, but instead call dumblist_sort, below: the calling interface is, not well encapsulated.
Quicksort is indeed a very fast sort for huge numbers of items, but it's surprisingly slow for small numbers of items -- so if you have a skillion short lists of things to sort, quicksort is the Wrong choice. Quicksorting was originally implemented because the early geometric Voronoi hull algorithm required presorting the elements. It turns out that presorting is a waste of time: the slight inefficiency added to the algorithm by sorting new neighbor candidates on-the-fly is tiny compared to the cost of sorting hundreds of neighbor candidates each time.
Duplicates are preserved -- call dumblist_crunch after sorting to get rid of them.
dumblist_shellsort
void dumblist_shellsort( DUMBLIST *dl, int (*cmp)(void *a, void *b)))
Implements Shell Sort on the list, calling the supplied comparator to order the elements. Shell Sort is a O(n2) sort algorithm, but it's faster than dumblist_qsort for up to about 50 elements, and allocates no additional memory. Although the calling interface is nicely encapsulated, you should probably call dumblist_sort (below) instead.
Duplicates are preserved -- call dumblist_crunch after sorting to get rid of them.
dumblist_crunch
void dumblist_crunch(DUMBLIST *dl)
Removes NULLs and duplicates in a DUMBLIST. The DUMBLIST need not be sorted, and if there are NULLs or duplicates it will end up in a random order: dumblist_rm is used to delete the unwanted elements, and it works by moving the last element in the DUMBLIST into the unoccupied position.
Because the DUMBLIST can be unsorted, the algorithm is inefficient for large lists: each element must be checked against every other element, so the testing is O(n2). For collections of order 10-30 elements it's not too bad, but crunching a list of 15,000 items is much slower than it could be.
dumblist_sort
void dumblist_sort( DUMBLIST *dl, int ((*cmp)(void *a, void *b)))
Sorts the dumblist and removes duplicates with one of the sorting helpers above and dumblist_crunch. The whole sorting infrastructure was written to help the hull algorithm in geometry.c; but later the hull algorithm itself was updated to not require presorting of the neighbor candidates. Maybe you'll have a use for it.
ptr_cmp
int ptr_cmp(void *a, void *b)
This is a generic pointer comparison routine for the sorting routines (above). It just compares the numeric values of the pointers themselves.
Utility
dumblist_snarf
void dumblist_snarf(DUMBLIST *dest, DUMBLIST *source)
Copies all elements from one dumblist into another, without regard for duplication. Used for neighbor candidate gathering.
dumblist_dump
void dumblist_dump(DUMBLIST *foo, void (*printer)(void *a)))
Calls the passed-in function on every element of a DUMBLIST. There's a standard one defined, dd_vertex_printer, which simply prints the vertex label field if the DUMBLIST happens to contain VERTEX structures.
Memory management
FLUX has a memory management system that wraps around the standard malloc. The memory manager is intended to help find corruption errors and memory leaks. You shouldn't normally have to use direct allocation: you should use the high level constructors
(at the top of this page) instead.
flux_malloc, flux_free
char *flux_malloc(long size, int what_for)
void flux_free(void *p)
Call flux_malloc rather than normal malloc. The what_for parameter should be an index into the global flux_malloc_types array defined in data.c.
In normal compilation flux_malloc ignores the second argument and just calls malloc. There are some debugging compile-time options that allow for memory padding, typechecking, and monitoring, to help debug the dynamic data structures.
