;+ ; $Id: chain_link_utilities.pro,v 1.2 2010/01/08 15:37:00 nathan Exp $ ; ; Collection of utilities for dealing with a chain (linked list). ; The user should only ever need the "add" and "delete" functions. ; The "add" function will also create a new chain. ; The "delete" function runs depointer.pro ; All functions accept a pointer to any link in the chain. ; ; Each link in the chain has 3 elements as tags in a struture: ; prev, points to previous link, null if beginning of chain. ; next, points to the next link, null if end of chain. ; data, points to whatever. ; ; written by jeffrey.r.hall@jpl.nasa.gov ; ; "Copyright 2009, by the California Institute of Technology. ; ALL RIGHTS RESERVED. United States Government Sponsorship ; acknowledged. Any commercial use must be negotiated with the ; Office of Technology Transfer at the California Institute of ; Technology. ; ; This software may be subject to U.S. export control laws. ; By accepting this software, the user agrees to comply with ; all applicable U.S. export laws and regulations. User has ; the responsibility to obtain export licenses, or other ; export authority as may be required before exporting such ; information to foreign countries or providing access to ; foreign persons." ; ; $Log: chain_link_utilities.pro,v $ ; Revision 1.2 2010/01/08 15:37:00 nathan ; committed sunloop_20091117 ; ;- @depointer.pro function chain_start_finder, chainlinkptr ; Find 1st link in chain. if ptr_valid( chainlinkptr ) then $ while ptr_valid( (*chainlinkptr).prev ) do $ chainlinkptr = (*chainlinkptr).prev return, chainlinkptr end function chain_end_finder, chainlinkptr ; Find last link in chain. while ptr_valid( (*chainlinkptr).next ) do chainlinkptr = (*chainlinkptr).next return, chainlinkptr end function chain_integrety, chainlinkptr ; Check to make sure the next link's prev points to current. integrety = 1 currentlink = chain_start_finder( chainlinkptr ) while ptr_valid( (*currentlink).next ) do begin nextlink = (*currentlink).next if (*nextlink).prev ne currentlink then integrety = 0 currentlink = nextlink endwhile return, integrety end function chain_link_counter, chainlinkptr ; Count all links in chain. count = 0 ; If no valid links found, return 0. if ptr_valid( chainlinkptr ) then begin count = 1 ; At least 1 link exists. current = chain_start_finder( chainlinkptr ) while ptr_valid( (*current).next ) do begin current = (*current).next ; Next link ok, increment count. count = count + 1 endwhile endif return, count end function chain_death, chainlinkptr ; Run depointer.pro on every link in the entire chain. Kill the whole thing. endlink = chain_end_finder( chainlinkptr ) while ptr_valid( endlink ) do begin prevlink = (*endlink).prev (*endlink).prev = ptr_new() ; Prevent depointer from going into an endless loop. result = depointer( endlink ) endlink = prevlink endwhile return, result end function chain_link_delete, chainlinkptr, VERBOSE=verbose ; Remove a link from anywhere in the chain and repair chain where removal occured. IF SIZE(verbose,/TYPE) GT 0 THEN verbose=verbose ELSE verbose=0 if ptr_valid( (*chainlinkptr).prev ) then begin if ptr_valid( (*chainlinkptr).next ) then begin ; Rejoin the chain eliminating the link to be deleted. prev = (*chainlinkptr).prev next = (*chainlinkptr).next (*prev).next = next (*next).prev = prev ; Depointer the link to be deleted. (*chainlinkptr).next = ptr_new() (*chainlinkptr).prev = ptr_new() result = depointer( chainlinkptr ) IF VERBOSE THEN print, 'deleted link in middle of chain' chainlinkptr = chain_start_finder( next ) endif else begin ; Terminate the new end of the chain. prev = (*chainlinkptr).prev (*prev).next = ptr_new() ; Depointer the link to be deleted. (*chainlinkptr).prev = ptr_new() result = depointer( chainlinkptr ) IF VERBOSE THEN print, 'deleted link at end of multilink chain' chainlinkptr = chain_start_finder( prev ) endelse endif else begin if ptr_valid( (*chainlinkptr).next ) then begin ; Terminate the new beginning of the chain. next = (*chainlinkptr).next (*next).prev = ptr_new() ; Depointer the link to be deleted. (*chainlinkptr).next = ptr_new() result = depointer( chainlinkptr ) IF VERBOSE THEN print, 'deleted link at beginning of multilink chain' chainlinkptr = chain_start_finder( next ) endif else begin ; Depointer the link to be deleted. result = depointer( chainlinkptr ) IF VERBOSE THEN print, 'deleted the only link in the chain' chainlinkptr = PTR_NEW() endelse endelse return, chainlinkptr end function chain_link_add, chainlinkptr, data, VERBOSE=verbose ; chainlinkptr can be any link in the chain. IF SIZE(verbose,/TYPE) GT 0 THEN verbose=verbose ELSE verbose=0 if chain_link_counter( chainlinkptr ) eq 0 then begin ; Start new chain. IF VERBOSE THEN print,'start new chain' newlink = { $ prev : ptr_new(), $ next : ptr_new(), $ data : ptr_new() } newend = ptr_new( newlink ) ; , /NO_COPY ) (*newend).data = ptr_new( data ) ; , /NO_COPY ) endif else begin ; Create new link and append to end of existing chain. newlink = { $ prev : ptr_new(), $ next : ptr_new(), $ data : ptr_new() } newend = ptr_new( newlink ) ; , /NO_COPY ) oldend = chain_end_finder( chainlinkptr ) (*oldend).next = newend (*newend).prev = oldend ; Set newlink data tag to data. (*newend).data = ptr_new( data ) ; , /NO_COPY ) endelse return, newend end