src/document/dom/stack.c

   1 /* The DOM tree navigation interface */
   2
   3 #ifdef HAVE_CONFIG_H
   4 #include "config.h"
   5 #endif
   6
   7 #include <stdlib.h>
   8 #include <string.h>
   9
  10 #include "elinks.h"
  11
  12 #include "document/dom/node.h"
  13 #include "document/dom/stack.h"
  14 #include "util/memory.h"
  15 #include "util/string.h"
  16
  17
  18 /* Navigator states */
  19
  20 #define DOM_STACK_STATE_GRANULARITY     0x7
  21 #define DOM_STACK_CALLBACKS_SIZE        (sizeof(dom_stack_callback_T) * DOM_NODES)
  22
  23 static inline struct dom_stack_state *
  24 realloc_dom_stack_states(struct dom_stack_state **states, size_t size)
  25 {
  26         return mem_align_alloc(states, size, size + 1,
  27                                struct dom_stack_state,
  28                                DOM_STACK_STATE_GRANULARITY);
  29 }
  30
  31 static inline unsigned char *
  32 realloc_dom_stack_state_objects(struct dom_stack *stack)
  33 {
  34 #ifdef DEBUG_MEMLEAK
  35         return mem_align_alloc__(__FILE__, __LINE__, (void **) &stack->state_objects,
  36                                stack->depth, stack->depth + 1,
  37                                stack->object_size,
  38                                DOM_STACK_STATE_GRANULARITY);
  39 #else
  40         return mem_align_alloc__((void **) &stack->state_objects,
  41                                stack->depth, stack->depth + 1,
  42                                stack->object_size,
  43                                DOM_STACK_STATE_GRANULARITY);
  44 #endif
  45 }
  46
  47 void
  48 init_dom_stack(struct dom_stack *stack, void *parser, void *renderer,
  49                dom_stack_callback_T callbacks[DOM_NODES],
  50                size_t object_size)
  51 {
  52         assert(stack);
  53
  54         memset(stack, 0, sizeof(*stack));
  55
  56         stack->parser      = parser;
  57         stack->renderer    = renderer;
  58         stack->object_size = object_size;
  59
  60         if (callbacks)
  61                 memcpy(stack->callbacks, callbacks, DOM_STACK_CALLBACKS_SIZE);
  62 }
  63
  64 void
  65 done_dom_stack(struct dom_stack *stack)
  66 {
  67         assert(stack);
  68
  69         mem_free_if(stack->states);
  70         mem_free_if(stack->state_objects);
  71
  72         memset(stack, 0, sizeof(*stack));
  73 }
  74
  75 struct dom_node *
  76 push_dom_node(struct dom_stack *stack, struct dom_node *node)
  77 {
  78         dom_stack_callback_T callback;
  79         struct dom_stack_state *state;
  80
  81         assert(stack && node);
  82         assert(0 < node->type && node->type < DOM_NODES);
  83
  84         if (stack->depth > DOM_STACK_MAX_DEPTH) {
  85                 return NULL;
  86         }
  87
  88         state = realloc_dom_stack_states(&stack->states, stack->depth);
  89         if (!state) {
  90                 done_dom_node(node);
  91                 return NULL;
  92         }
  93
  94         state += stack->depth;
  95
  96         if (stack->object_size) {
  97                 unsigned char *state_objects;
  98
  99                 state_objects = realloc_dom_stack_state_objects(stack);
 100                 if (!state_objects) {
 101                         done_dom_node(node);
 102                         return NULL;
 103                 }
 104
 105                 state->depth = stack->depth;
 106         }
 107
 108         state->node = node;
 109
 110         /* Grow the state array to the new depth so the state accessors work
 111          * in the callbacks */
 112         stack->depth++;
 113
 114         callback = stack->callbacks[node->type];
 115         if (callback) {
 116                 void *state_data = get_dom_stack_state_data(stack, state);
 117
 118                 node = callback(stack, node, state_data);
 119
 120                 /* If the callback returned NULL pop the state immediately */
 121                 if (!node) {
 122                         memset(state, 0, sizeof(*state));
 123                         stack->depth--;
 124                         assert(stack->depth >= 0);
 125                 }
 126         }
 127
 128         return node;
 129 }
 130
 131 static int
 132 do_pop_dom_node(struct dom_stack *stack, struct dom_stack_state *parent)
 133 {
 134         struct dom_stack_state *state;
 135
 136         assert(stack);
 137         if (!dom_stack_has_parents(stack)) return 0;
 138
 139         state = get_dom_stack_top(stack);
 140         if (state->callback) {
 141                 void *state_data = get_dom_stack_state_data(stack, state);
 142
 143                 /* Pass the node we are popping to and _not_ the state->node */
 144                 state->callback(stack, parent->node, state_data);
 145         }
 146
 147         stack->depth--;
 148         assert(stack->depth >= 0);
 149
 150         if (stack->object_size) {
 151                 void *state_data = get_dom_stack_state_data(stack, state);
 152
 153                 memset(state_data, 0, stack->object_size);
 154         }
 155
 156         memset(state, 0, sizeof(*state));
 157
 158         return state == parent;
 159 }
 160
 161 void
 162 pop_dom_node(struct dom_stack *stack)
 163 {
 164         assert(stack);
 165         if (!dom_stack_has_parents(stack)) return;
 166
 167         do_pop_dom_node(stack, get_dom_stack_parent(stack));
 168 }
 169
 170 void
 171 pop_dom_nodes(struct dom_stack *stack, enum dom_node_type type,
 172               unsigned char *string, uint16_t length)
 173 {
 174         struct dom_stack_state *state, *parent;
 175         unsigned int pos;
 176
 177         if (!dom_stack_has_parents(stack)) return;
 178
 179         parent = search_dom_stack(stack, type, string, length);
 180         if (!parent) return;
 181
 182         foreachback_dom_state (stack, state, pos) {
 183                 if (do_pop_dom_node(stack, parent))
 184                         break;;
 185         }
 186 }
 187
 188 void
 189 walk_dom_nodes(struct dom_stack *stack, struct dom_node *root)
 190 {
 191         assert(root && stack);
 192
 193         push_dom_node(stack, root);
 194
 195         while (dom_stack_has_parents(stack)) {
 196                 struct dom_stack_state *state = get_dom_stack_top(stack);
 197                 struct dom_node_list *list = state->list;
 198                 struct dom_node *node = state->node;
 199
 200                 switch (node->type) {
 201                 case DOM_NODE_DOCUMENT:
 202                         if (!list) list = node->data.document.children;
 203                         break;
 204
 205                 case DOM_NODE_ELEMENT:
 206                         if (!list) list = node->data.element.map;
 207
 208                         if (list == node->data.element.children) break;
 209                         if (is_dom_node_list_member(list, state->index)
 210                             && list == node->data.element.map)
 211                                 break;
 212
 213                         list = node->data.element.children;
 214                         break;
 215
 216                 case DOM_NODE_PROCESSING_INSTRUCTION:
 217                         if (!list) list = node->data.proc_instruction.map;
 218                         break;
 219
 220                 case DOM_NODE_DOCUMENT_TYPE:
 221                         if (!list) list = node->data.document_type.entities;
 222
 223                         if (list == node->data.document_type.notations) break;
 224                         if (is_dom_node_list_member(list, state->index)
 225                             && list == node->data.document_type.entities)
 226                                 break;
 227
 228                         list = node->data.document_type.notations;
 229                         break;
 230
 231                 case DOM_NODE_ATTRIBUTE:
 232                 case DOM_NODE_TEXT:
 233                 case DOM_NODE_CDATA_SECTION:
 234                 case DOM_NODE_COMMENT:
 235                 case DOM_NODE_NOTATION:
 236                 case DOM_NODE_DOCUMENT_FRAGMENT:
 237                 case DOM_NODE_ENTITY_REFERENCE:
 238                 case DOM_NODE_ENTITY:
 239                 default:
 240                         break;
 241                 }
 242
 243                 /* Reset list state if it is a new list */
 244                 if (list != state->list) {
 245                         state->list  = list;
 246                         state->index = 0;
 247                 }
 248
 249                 /* If we have next child node */
 250                 if (is_dom_node_list_member(list, state->index)) {
 251                         struct dom_node *child = list->entries[state->index++];
 252
 253                         if (push_dom_node(stack, child))
 254                                 continue;
 255                 }
 256
 257                 pop_dom_node(stack);
 258         }
 259 }