ELinks 0.16.1.1
stack.h File Reference

The DOM stack interface. More...

#include "dom/code.h"
#include "dom/node.h"
#include "util/error.h"
#include "util/hash.h"
Include dependency graph for stack.h:
This graph shows which files directly or indirectly include this file:

Data Structures

struct  dom_stack_state
 DOM stack state. More...
struct  dom_stack_context_info
 DOM stack context info. More...
struct  dom_stack_context
 DOM stack context. More...
struct  dom_stack
 The DOM stack. More...

Macros

#define DOM_STACK_MAX_DEPTH   4096
#define dom_stack_is_empty(stack)
 Check whether stack is empty or not.
#define get_dom_stack_top(stack)
 Access the stack top.
#define add_dom_stack_tracer(stack, name)
 Get debug info from the DOM stack.
#define foreach_dom_stack_state(stack, state, pos)
 The state iterators.
#define foreachback_dom_stack_state(stack, state, pos)
 Iterate the stack from top to bottom.

Typedefs

typedef enum dom_code(* dom_stack_callback_T) (struct dom_stack *, struct dom_node *, void *)
 DOM stack callback.

Enumerations

enum  dom_stack_flag { DOM_STACK_FLAG_NONE = 0 , DOM_STACK_FLAG_FREE_NODES = 1 }
 Flags for controlling the DOM stack. More...

Functions

static struct dom_stack_stateget_dom_stack_state (struct dom_stack *stack, int top_offset)
 Access state by offset from top.
static void * get_dom_stack_state_data (struct dom_stack_context *context, struct dom_stack_state *state)
 Access context specific state data.
void init_dom_stack (struct dom_stack *stack, unsigned int flags)
 Initialise a DOM stack.
void done_dom_stack (struct dom_stack *stack)
 Release a DOM stack.
struct dom_stack_contextadd_dom_stack_context (struct dom_stack *stack, void *data, struct dom_stack_context_info *context_info)
 Add a context to the stack.
void done_dom_stack_context (struct dom_stack *stack, struct dom_stack_context *context)
 Unregister a stack context.
enum dom_code push_dom_node (struct dom_stack *stack, struct dom_node *node)
 Push a node onto the stack.
void pop_dom_node (struct dom_stack *stack)
 Pop the top stack state.
void pop_dom_nodes (struct dom_stack *stack, enum dom_node_type type, struct dom_string *string)
 Conditionally pop the stack states.
void pop_dom_state (struct dom_stack *stack, struct dom_stack_state *target)
 Pop all states until target state.
struct dom_stack_statesearch_dom_stack (struct dom_stack *stack, enum dom_node_type type, struct dom_string *string)
 Search the stack states.
void walk_dom_nodes (struct dom_stack *stack, struct dom_node *root)
 Walk all nodes reachable from a given node.

Detailed Description

The DOM stack interface.

The DOM stack interface is used by the parser when building a DOM tree and by the various DOM tree traversers. It allows for several stack contexts to be registered, each defining their own type specific node handlers or callbacks (dom_stack_callback_T) which will be called upon a node being pushed onto or popped from the stack. As an example a example, by defining DOM_STACK_TRACE it is be possible to add a DOM stack tracer (using add_dom_stack_tracer) to debug all push and pop operations.

The stack interface provides a method for automatically having objects allocated when a new node is pushed onto the stack. This object can then be used for storing private state information belonging to the individual contexts. This is done by setting the dom_stack_context_info.object_size member to a non-zero value, usually using sizeof().

States on the stack can be marked immutable meaning that they will be "locked" down so that any operations to pop them will fail. This can be used when parsing a "subdocument", e.g. output from ECMAScripts "document.write" function, where badly formatted SGML should not be allowed to change the root document.

In some situations, it may be desired to avoid building a complete DOM tree in memory when only one document traversal is required, for example when highlighting SGML code. This can be done by passing the DOM_STACK_FLAG_FREE_NODES flag to init_dom_stack. Nodes that are popped from the stack will immediately be deallocated. A pop node callback can also request that a node is deallocated and removed from the DOM tree by returning the DOM_CODE_FREE_NODE return code. An example of this can be seen in the DOM configuration module where comment nodes may be pruned from the tree.

Macro Definition Documentation

◆ add_dom_stack_tracer

#define add_dom_stack_tracer ( stack,
name )
Value:
/* Nada */

Get debug info from the DOM stack.

Define DOM_STACK_TRACE to have debug info about the nodes added printed to the log. It will define add_dom_stack_tracer() to not be a no-op.

Run as:

ELINKS_LOG=/tmp/dom-dump.txt ./elinks -no-connect URL

to have the debug dumped into a file.

◆ dom_stack_is_empty

#define dom_stack_is_empty ( stack)
Value:
(!(stack)->states || (stack)->depth == 0)

Check whether stack is empty or not.

Parameters
stackThe stack to check.
Returns
Non-zero if stack is empty.

◆ DOM_STACK_MAX_DEPTH

#define DOM_STACK_MAX_DEPTH   4096

◆ foreach_dom_stack_state

#define foreach_dom_stack_state ( stack,
state,
pos )
Value:
for ((pos) = 0; (pos) < (stack)->depth; (pos)++) \
if (((state) = &(stack)->states[(pos)]))

The state iterators.

To safely iterate through the stack state iterators. Iterate the stack from bottom to top.

◆ foreachback_dom_stack_state

#define foreachback_dom_stack_state ( stack,
state,
pos )
Value:
for ((pos) = (stack)->depth - 1; (pos) >= 0; (pos)--) \
if (((state) = &(stack)->states[(pos)]))

Iterate the stack from top to bottom.

◆ get_dom_stack_top

#define get_dom_stack_top ( stack)
Value:
static struct dom_stack_state * get_dom_stack_state(struct dom_stack *stack, int top_offset)
Access state by offset from top.
Definition stack.h:169

Access the stack top.

Parameters
stackThe stack to get the top state from.
Returns
The top state.

Typedef Documentation

◆ dom_stack_callback_T

typedef enum dom_code(* dom_stack_callback_T) (struct dom_stack *, struct dom_node *, void *)

DOM stack callback.

Used by contexts, for 'hooking' into the node traversing.

This callback must not call done_dom_node() to free the node it gets as a parameter, because call_dom_node_callbacks() may be intending to call more callbacks for the same node. Instead, the callback can return DOM_CODE_FREE_NODE, and the node will then be freed after the callbacks of all contexts have been called.

Enumeration Type Documentation

◆ dom_stack_flag

Flags for controlling the DOM stack.

Enumerator
DOM_STACK_FLAG_NONE 

No flag needed.

DOM_STACK_FLAG_FREE_NODES 

Free nodes when popping by calling done_dom_node().

Function Documentation

◆ add_dom_stack_context()

struct dom_stack_context * add_dom_stack_context ( struct dom_stack * stack,
void * data,
struct dom_stack_context_info * context_info )

Add a context to the stack.

This is needed if either you want to have the stack allocated objects for created states and/or if you want to install callbacks for pushing or popping.

Parameters
stackThe stack where the context should be created.
dataPrivate data to be stored in ref:[dom_stack_context.data].
context_infoInformation about state objects and node callbacks.
Returns
A pointer to the newly created context or NULL.

◆ done_dom_stack()

void done_dom_stack ( struct dom_stack * stack)

Release a DOM stack.

Free all resources collected by the stack.

Parameters
stackThe stack to release.

◆ done_dom_stack_context()

void done_dom_stack_context ( struct dom_stack * stack,
struct dom_stack_context * context )

Unregister a stack context.

This should be done especially for temporary stack contexts (without any callbacks) so that they do not increasing the memory usage.

◆ get_dom_stack_state()

struct dom_stack_state * get_dom_stack_state ( struct dom_stack * stack,
int top_offset )
inlinestatic

Access state by offset from top.

Parameters
stackThe stack to fetch the state from.
top_offsetThe offset from the stack top, zero is the top.
Returns
The requested state.

◆ get_dom_stack_state_data()

void * get_dom_stack_state_data ( struct dom_stack_context * context,
struct dom_stack_state * state )
inlinestatic

Access context specific state data.

Similar to ref:[get_dom_stack_state], this will fetch the data associated with the state for the given context.

Parameters
contextThe context to get data from.
stateThe stack state to get data from.
Returns
The state data or NULL if dom_stack_context_info.object_size was zero.

◆ init_dom_stack()

void init_dom_stack ( struct dom_stack * stack,
unsigned int flags )

Initialise a DOM stack.

Parameters
stackPointer to a (preallocated) stack.
flagsAny flags needed for controlling the behaviour of the stack.

◆ pop_dom_node()

void pop_dom_node ( struct dom_stack * stack)

Pop the top stack state.

Parameters
stackThe stack to pop from.

◆ pop_dom_nodes()

void pop_dom_nodes ( struct dom_stack * stack,
enum dom_node_type type,
struct dom_string * string )

Conditionally pop the stack states.

Searches the stack (using ref:[search_dom_stack]) for a specific node and pops all states until that particular state is met.

Note
The popping is stopped if an immutable state is encountered.

◆ pop_dom_state()

void pop_dom_state ( struct dom_stack * stack,
struct dom_stack_state * target )

Pop all states until target state.

Pop all stack states until a specific state is reached. The target state is also popped.

Parameters
stackThe stack to pop from.
targetThe state to pop until and including.

◆ push_dom_node()

enum dom_code push_dom_node ( struct dom_stack * stack,
struct dom_node * node )

Push a node onto the stack.

Makes the pushed node the new top of the stack.

Parameters
stackThe stack to push onto.
nodeThe node to push onto the stack.
Returns
If an error occurs the node is released with done_dom_node and NULL is returned. Else the pushed node is returned.

◆ search_dom_stack()

struct dom_stack_state * search_dom_stack ( struct dom_stack * stack,
enum dom_node_type type,
struct dom_string * string )

Search the stack states.

The string comparison is done against the ref:[dom_node.string] member of the of the state nodes.

Parameters
stackThe stack to search in.
typeThe type of node to match against.
stringThe string to match against.
Returns
A state that matched the type and string or NULL.

◆ walk_dom_nodes()

void walk_dom_nodes ( struct dom_stack * stack,
struct dom_node * root )

Walk all nodes reachable from a given node.

Visits each node in the DOM tree rooted at a given node, pre-order style.

Parameters
stackThe stack to use for walking the nodes.
rootThe root node to start from.

It is assummed that the given stack has been initialised with init_dom_stack and that the caller already added one or more context to the stack.