src/dom/node.c

   1 /* The DOM node handling */
   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 "dom/node.h"
  13 #include "dom/string.h"
  14 #include "util/hash.h"
  15 #include "util/memory.h"
  16
  17
  18 static void done_dom_node_data(struct dom_node *node);
  19
  20 /* Node lists */
  21
  22 #define DOM_NODE_LIST_GRANULARITY 0x7
  23
  24 #define DOM_NODE_LIST_BLOCK_SIZE \
  25         (ALIGN_MEMORY_SIZE(1, DOM_NODE_LIST_GRANULARITY) * sizeof(struct dom_node *))
  26
  27 /* The node list struct has one node pointer */
  28 #define DOM_NODE_LIST_SIZE(size) \
  29         ((size - 1) * sizeof(struct dom_node *) + sizeof(struct dom_node_list))
  30
  31 static inline struct dom_node_list *
  32 realloc_dom_node_list(struct dom_node_list **oldlist)
  33 {
  34         struct dom_node_list *list = *oldlist;
  35         size_t size = list ? list->size : 0;
  36         size_t oldsize = ALIGN_MEMORY_SIZE(size, DOM_NODE_LIST_GRANULARITY);
  37         size_t newsize = ALIGN_MEMORY_SIZE(size + 1, DOM_NODE_LIST_GRANULARITY);
  38
  39         if (newsize <= oldsize) return list;
  40
  41         list = mem_realloc(list, DOM_NODE_LIST_SIZE(newsize));
  42         if (!list) return NULL;
  43
  44         /* If this is the first reallocation clear the size */
  45         if (!size) list->size = 0;
  46
  47         /* Clear the new block of entries */
  48         memset(&list->entries[oldsize], 0, DOM_NODE_LIST_BLOCK_SIZE);
  49
  50         *oldlist = list;
  51
  52         return list;
  53 }
  54
  55 struct dom_node_list *
  56 add_to_dom_node_list(struct dom_node_list **list_ptr,
  57                      struct dom_node *node, int position)
  58 {
  59         struct dom_node_list *list;
  60
  61         assert(list_ptr && node);
  62
  63         list = realloc_dom_node_list(list_ptr);
  64         if (!list) return NULL;
  65
  66         assertm(position < 0 || position <= list->size,
  67                 "position out of bound %d > %zu", position, list->size);
  68
  69         if (position < 0) {
  70                 position = list->size;
  71
  72         } else if (position < list->size) {
  73                 /* Make room if we have to add the node in the middle of the list */
  74                 struct dom_node **offset = &list->entries[position];
  75                 size_t size = (list->size - position) * sizeof(*offset);
  76
  77                 memmove(offset + 1, offset, size);
  78         }
  79
  80         list->size++;
  81         list->entries[position] = node;
  82
  83         return list;
  84 }
  85
  86 static void
  87 del_from_dom_node_list(struct dom_node_list *list, struct dom_node *node)
  88 {
  89         struct dom_node *entry;
  90         size_t i;
  91
  92         if (!list) return;
  93
  94         foreach_dom_node (list, entry, i) {
  95                 size_t successors;
  96
  97                 if (entry != node) continue;
  98
  99                 successors = list->size - (i + 1);
 100                 if (successors)
 101                         memmove(&list->entries[i], &list->entries[i+1],
 102                                 sizeof(*list->entries) * successors);
 103                 list->size--;
 104         }
 105 }
 106
 107 void
 108 done_dom_node_list(struct dom_node_list *list)
 109 {
 110         struct dom_node *node;
 111         int i;
 112
 113         assert(list);
 114
 115         foreach_dom_node (list, node, i) {
 116                 /* Avoid that the node start messing with the node list. */
 117                 done_dom_node_data(node);
 118         }
 119
 120         mem_free(list);
 121 }
 122
 123
 124 /* Node map */
 125
 126 struct dom_node_search {
 127         struct dom_node *key;
 128         unsigned int from, pos, to;
 129 };
 130
 131 #define INIT_DOM_NODE_SEARCH(key, list) \
 132         { (key), -1, 0, (list)->size, }
 133
 134 int
 135 dom_node_casecmp(struct dom_node *node1, struct dom_node *node2)
 136 {
 137         if (node1->type == node2->type) {
 138                 switch (node1->type) {
 139                 case DOM_NODE_ELEMENT:
 140                         if (node1->data.element.type && node2->data.element.type)
 141                                 return node1->data.element.type - node2->data.element.type;
 142                         break;
 143
 144                 case DOM_NODE_ATTRIBUTE:
 145                         if (node1->data.attribute.type && node2->data.attribute.type)
 146                                 return node1->data.attribute.type - node2->data.attribute.type;
 147                         break;
 148
 149                 default:
 150                         break;
 151                 }
 152         }
 153
 154         return dom_string_casecmp(&node1->string, &node2->string);
 155 }
 156
 157 static inline int
 158 get_bsearch_position(struct dom_node_list *list, int from, int to)
 159 {
 160         int pos = from + ((to - from) / 2);
 161
 162         assertm(0 <= pos && pos < list->size, "pos %d", pos);
 163         return pos;
 164 }
 165
 166 #define has_bsearch_node(from, to)      ((from) + 1 < (to))
 167
 168 static inline struct dom_node *
 169 dom_node_list_bsearch(struct dom_node_search *search, struct dom_node_list *list)
 170 {
 171         assert(has_bsearch_node(search->from, search->to));
 172
 173         do {
 174                 int pos = get_bsearch_position(list, search->from, search->to);
 175                 struct dom_node *node = list->entries[pos];
 176                 int difference = dom_node_casecmp(search->key, node);
 177
 178                 search->pos = pos;
 179
 180                 if (!difference) return node;
 181
 182                 if (difference < 0) {
 183                         search->to   = search->pos;
 184                 } else {
 185                         search->from = search->pos;
 186                 }
 187
 188         } while (has_bsearch_node(search->from, search->to));
 189
 190         return NULL;
 191 }
 192
 193 int
 194 get_dom_node_map_index(struct dom_node_list *list, struct dom_node *node)
 195 {
 196         struct dom_node_search search = INIT_DOM_NODE_SEARCH(node, list);
 197         struct dom_node *match = dom_node_list_bsearch(&search, list);
 198
 199         return match ? search.pos : search.to;
 200 }
 201
 202 struct dom_node *
 203 get_dom_node_map_entry(struct dom_node_list *list, enum dom_node_type type,
 204                        uint16_t subtype, struct dom_string *name)
 205 {
 206         struct dom_node node = { type, 0, INIT_DOM_STRING(name->string, name->length) };
 207         struct dom_node_search search = INIT_DOM_NODE_SEARCH(&node, list);
 208
 209         if (subtype) {
 210                 /* Set the subtype */
 211                 switch (type) {
 212                 case DOM_NODE_ELEMENT:
 213                         node.data.element.type = subtype;
 214                         break;
 215                 case DOM_NODE_ATTRIBUTE:
 216                         node.data.attribute.type = subtype;
 217                         break;
 218                 case DOM_NODE_PROCESSING_INSTRUCTION:
 219                         node.data.proc_instruction.type = subtype;
 220                         break;
 221                 default:
 222                         break;
 223                 }
 224         }
 225
 226         return dom_node_list_bsearch(&search, list);
 227 }
 228
 229 static int
 230 get_dom_node_list_pos(struct dom_node_list *list, struct dom_node *node)
 231 {
 232         struct dom_node *entry;
 233         int i;
 234
 235         assert(list);
 236         if_assert_failed return -1;
 237
 238         foreach_dom_node (list, entry, i) {
 239                 if (entry == node)
 240                         return i;
 241         }
 242
 243         return -1;
 244 }
 245
 246 int
 247 get_dom_node_list_index(struct dom_node *parent, struct dom_node *node)
 248 {
 249         struct dom_node_list **list = get_dom_node_list(parent, node);
 250
 251         return (list && *list) ? get_dom_node_list_pos(*list, node) : -1;
 252 }
 253
 254 struct dom_node *
 255 get_dom_node_prev(struct dom_node *node)
 256 {
 257         struct dom_node_list **list;
 258         int index;
 259
 260         assert(node->parent);
 261         if_assert_failed return NULL;
 262
 263         list = get_dom_node_list(node->parent, node);
 264         /* node->parent != NULL, so the node must be in the
 265          * appropriate list of the parent; the list thus cannot be
 266          * empty.  */
 267         if (!list) return NULL;
 268         assert(*list);
 269         if_assert_failed return NULL;
 270
 271         index = get_dom_node_list_pos(*list, node);
 272         assert(index >= 0); /* in particular, not -1 */
 273         if_assert_failed return NULL;
 274
 275         if (index > 0)
 276                 return (*list)->entries[index - 1];
 277
 278         return NULL;
 279 }
 280
 281 struct dom_node *
 282 get_dom_node_next(struct dom_node *node)
 283 {
 284         struct dom_node_list **list;
 285         int index;
 286
 287         assert(node->parent);
 288         if_assert_failed return NULL;
 289
 290         list = get_dom_node_list(node->parent, node);
 291         /* node->parent != NULL, so the node must be in the
 292          * appropriate list of the parent; the list thus cannot be
 293          * empty.  */
 294         if (!list) return NULL;
 295         assert(*list);
 296         if_assert_failed return NULL;
 297
 298         index = get_dom_node_list_pos(*list, node);
 299         assert(index >= 0); /* in particular, not -1 */
 300         if_assert_failed return NULL;
 301
 302         if (index + 1 < (*list)->size)
 303                 return (*list)->entries[index + 1];
 304
 305         return NULL;
 306 }
 307
 308 struct dom_node *
 309 get_dom_node_child(struct dom_node *parent, enum dom_node_type type,
 310                    int16_t subtype)
 311 {
 312         struct dom_node_list **list;
 313         struct dom_node *node;
 314         int index;
 315
 316         list = get_dom_node_list_by_type(parent, type);
 317         if (!list) return NULL; /* parent doesn't support this type */
 318         if (!*list) return NULL; /* list is empty and not yet allocated */
 319
 320         foreach_dom_node (*list, node, index) {
 321                 if (node->type != type)
 322                         continue;
 323
 324                 if (!subtype) return node;
 325
 326                 switch (type) {
 327                 case DOM_NODE_ELEMENT:
 328                         if (node->data.element.type == subtype)
 329                                 return node;
 330                         break;
 331
 332                 case DOM_NODE_ATTRIBUTE:
 333                         if (node->data.attribute.type == subtype)
 334                                 return node;
 335                         break;
 336
 337                 case DOM_NODE_PROCESSING_INSTRUCTION:
 338                         if (node->data.attribute.type == subtype)
 339                                 return node;
 340                         break;
 341
 342                 default:
 343                         return node;
 344                 }
 345         }
 346
 347         return NULL;
 348 }
 349
 350
 351 /* Nodes */
 352
 353 struct dom_node *
 354 init_dom_node_at(
 355 #ifdef DEBUG_MEMLEAK
 356                 unsigned char *file, int line,
 357 #endif
 358                 struct dom_node *parent, enum dom_node_type type,
 359                 struct dom_string *string, int allocated)
 360 {
 361 #ifdef DEBUG_MEMLEAK
 362         struct dom_node *node = debug_mem_calloc(file, line, 1, sizeof(*node));
 363 #else
 364         struct dom_node *node = mem_calloc(1, sizeof(*node));
 365 #endif
 366
 367         if (!node) return NULL;
 368
 369         node->type   = type;
 370         node->parent = parent;
 371
 372         /* Make it possible to add a node to a parent without allocating the
 373          * strings. */
 374         if (allocated >= 0) {
 375                 node->allocated = !!allocated;
 376         } else if (parent) {
 377                 node->allocated = parent->allocated;
 378         }
 379
 380         if (node->allocated) {
 381                 if (!init_dom_string(&node->string, string->string, string->length)) {
 382                         done_dom_node(node);
 383                         return NULL;
 384                 }
 385         } else {
 386                 copy_dom_string(&node->string, string);
 387         }
 388
 389         if (parent) {
 390                 struct dom_node_list **list = get_dom_node_list(parent, node);
 391                 int sort = (type == DOM_NODE_ATTRIBUTE);
 392                 int index;
 393
 394                 assertm(list != NULL, "Adding node %d to bad parent %d",
 395                         node->type, parent->type);
 396
 397                 index = *list && (*list)->size > 0 && sort
 398                       ? get_dom_node_map_index(*list, node) : -1;
 399
 400                 if (!add_to_dom_node_list(list, node, index)) {
 401                         done_dom_node(node);
 402                         return NULL;
 403                 }
 404         }
 405
 406         return node;
 407 }
 408
 409 void
 410 done_dom_node_data(struct dom_node *node)
 411 {
 412         union dom_node_data *data;
 413
 414         assert(node);
 415         assert(node->type < DOM_NODES); /* unsigned comparison */
 416
 417         data = &node->data;
 418
 419         switch (node->type) {
 420         case DOM_NODE_ATTRIBUTE:
 421                 if (node->allocated)
 422                         done_dom_string(&data->attribute.value);
 423                 break;
 424
 425         case DOM_NODE_DOCUMENT:
 426                 if (data->document.children)
 427                         done_dom_node_list(data->document.children);
 428                 break;
 429
 430         case DOM_NODE_ELEMENT:
 431                 if (data->element.children)
 432                         done_dom_node_list(data->element.children);
 433
 434                 if (data->element.map)
 435                         done_dom_node_list(data->element.map);
 436                 break;
 437
 438         case DOM_NODE_PROCESSING_INSTRUCTION:
 439                 if (data->proc_instruction.map)
 440                         done_dom_node_list(data->proc_instruction.map);
 441                 if (node->allocated)
 442                         done_dom_string(&data->proc_instruction.instruction);
 443                 break;
 444
 445         default:
 446                 break;
 447         }
 448
 449         if (node->allocated)
 450                 done_dom_string(&node->string);
 451
 452         /* call_dom_stack_callbacks() asserts that the node type is
 453          * within range.  If assertions are enabled, store an
 454          * out-of-range value there to make the assertion more likely
 455          * to fail if a callback has freed the node prematurely.
 456          * This is not entirely reliable though, because the memory
 457          * is freed below and may be allocated for some other purpose
 458          * before the assertion.  */
 459 #ifndef CONFIG_FASTMEM
 460         node->type = -1;
 461 #endif
 462
 463         mem_free(node);
 464 }
 465
 466 void
 467 done_dom_node(struct dom_node *node)
 468 {
 469         assert(node);
 470
 471         if (node->parent) {
 472                 struct dom_node *parent = node->parent;
 473                 union dom_node_data *data = &parent->data;
 474
 475                 switch (parent->type) {
 476                 case DOM_NODE_DOCUMENT:
 477                         del_from_dom_node_list(data->document.children, node);
 478                         break;
 479
 480                 case DOM_NODE_ELEMENT:
 481                         del_from_dom_node_list(data->element.children, node);
 482                         del_from_dom_node_list(data->element.map, node);
 483                         break;
 484
 485                 case DOM_NODE_PROCESSING_INSTRUCTION:
 486                         del_from_dom_node_list(data->proc_instruction.map, node);
 487                         break;
 488
 489                 default:
 490                         break;
 491                 }
 492         }
 493
 494         done_dom_node_data(node);
 495 }
 496
 497 #define set_node_name(name, namelen, str)       \
 498         do { (name) = (str); (namelen) = sizeof(str) - 1; } while (0)
 499
 500 struct dom_string *
 501 get_dom_node_name(struct dom_node *node)
 502 {
 503         static struct dom_string cdata_section_str = STATIC_DOM_STRING("#cdata-section");
 504         static struct dom_string comment_str = STATIC_DOM_STRING("#comment");
 505         static struct dom_string document_str = STATIC_DOM_STRING("#document");
 506         static struct dom_string document_fragment_str = STATIC_DOM_STRING("#document-fragment");
 507         static struct dom_string text_str = STATIC_DOM_STRING("#text");
 508
 509         assert(node);
 510
 511         switch (node->type) {
 512         case DOM_NODE_CDATA_SECTION:
 513                 return &cdata_section_str;
 514
 515         case DOM_NODE_COMMENT:
 516                 return &comment_str;
 517
 518         case DOM_NODE_DOCUMENT:
 519                 return &document_str;
 520
 521         case DOM_NODE_DOCUMENT_FRAGMENT:
 522                 return &document_fragment_str;
 523
 524         case DOM_NODE_TEXT:
 525                 return &text_str;
 526
 527         case DOM_NODE_ATTRIBUTE:
 528         case DOM_NODE_DOCUMENT_TYPE:
 529         case DOM_NODE_ELEMENT:
 530         case DOM_NODE_ENTITY:
 531         case DOM_NODE_ENTITY_REFERENCE:
 532         case DOM_NODE_NOTATION:
 533         case DOM_NODE_PROCESSING_INSTRUCTION:
 534         default:
 535                 return &node->string;
 536         }
 537 }
 538
 539 struct dom_string *
 540 get_dom_node_value(struct dom_node *node)
 541 {
 542         assert(node);
 543
 544         switch (node->type) {
 545         case DOM_NODE_ATTRIBUTE:
 546                 return &node->data.attribute.value;
 547
 548         case DOM_NODE_PROCESSING_INSTRUCTION:
 549                 return &node->data.proc_instruction.instruction;
 550
 551         case DOM_NODE_CDATA_SECTION:
 552         case DOM_NODE_COMMENT:
 553         case DOM_NODE_TEXT:
 554                 return &node->string;
 555
 556         case DOM_NODE_ENTITY_REFERENCE:
 557         case DOM_NODE_NOTATION:
 558         case DOM_NODE_DOCUMENT:
 559         case DOM_NODE_DOCUMENT_FRAGMENT:
 560         case DOM_NODE_DOCUMENT_TYPE:
 561         case DOM_NODE_ELEMENT:
 562         case DOM_NODE_ENTITY:
 563         default:
 564                 return NULL;
 565         }
 566 }
 567
 568 struct dom_string *
 569 get_dom_node_type_name(enum dom_node_type type)
 570 {
 571         static struct dom_string dom_node_type_names[DOM_NODES] = {
 572                 INIT_DOM_STRING(NULL, 0),
 573                 /* DOM_NODE_ELEMENT */                  STATIC_DOM_STRING("element"),
 574                 /* DOM_NODE_ATTRIBUTE */                STATIC_DOM_STRING("attribute"),
 575                 /* DOM_NODE_TEXT */                     STATIC_DOM_STRING("text"),
 576                 /* DOM_NODE_CDATA_SECTION */            STATIC_DOM_STRING("cdata-section"),
 577                 /* DOM_NODE_ENTITY_REFERENCE */         STATIC_DOM_STRING("entity-reference"),
 578                 /* DOM_NODE_ENTITY */                   STATIC_DOM_STRING("entity"),
 579                 /* DOM_NODE_PROCESSING_INSTRUCTION */   STATIC_DOM_STRING("proc-instruction"),
 580                 /* DOM_NODE_COMMENT */                  STATIC_DOM_STRING("comment"),
 581                 /* DOM_NODE_DOCUMENT */                 STATIC_DOM_STRING("document"),
 582                 /* DOM_NODE_DOCUMENT_TYPE */            STATIC_DOM_STRING("document-type"),
 583                 /* DOM_NODE_DOCUMENT_FRAGMENT */        STATIC_DOM_STRING("document-fragment"),
 584                 /* DOM_NODE_NOTATION */                 STATIC_DOM_STRING("notation"),
 585         };
 586
 587         assert(type < DOM_NODES);
 588
 589         return &dom_node_type_names[type];
 590 }