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
 237         foreach_dom_node (list, entry, i) {
 238                 if (entry == node)
 239                         return i;
 240         }
 241
 242         return -1;
 243 }
 244
 245 int
 246 get_dom_node_list_index(struct dom_node *parent, struct dom_node *node)
 247 {
 248         struct dom_node_list **list = get_dom_node_list(parent, node);
 249
 250         return list ? get_dom_node_list_pos(*list, node) : -1;
 251 }
 252
 253 struct dom_node *
 254 get_dom_node_prev(struct dom_node *node)
 255 {
 256         struct dom_node_list **list;
 257         int index;
 258
 259         assert(node->parent);
 260
 261         list = get_dom_node_list(node->parent, node);
 262         if (!list) return NULL;
 263
 264         index = get_dom_node_list_pos(*list, node);
 265         if (index > 0)
 266                 return (*list)->entries[index - 1];
 267
 268         return NULL;
 269 }
 270
 271 struct dom_node *
 272 get_dom_node_next(struct dom_node *node)
 273 {
 274         struct dom_node_list **list;
 275         int index;
 276
 277         assert(node->parent);
 278
 279         list = get_dom_node_list(node->parent, node);
 280         if (!list) return NULL;
 281
 282         index = get_dom_node_list_pos(*list, node);
 283         if (index + 1 < (*list)->size)
 284                 return (*list)->entries[index + 1];
 285
 286         return NULL;
 287 }
 288
 289 struct dom_node *
 290 get_dom_node_child(struct dom_node *parent, enum dom_node_type type,
 291                    int16_t subtype)
 292 {
 293         struct dom_node_list **list;
 294         struct dom_node *node;
 295         int index;
 296
 297         list = get_dom_node_list_by_type(parent, type);
 298         if (!list) return NULL;
 299
 300         foreach_dom_node (*list, node, index) {
 301                 if (node->type != type)
 302                         continue;
 303
 304                 if (!subtype) return node;
 305
 306                 switch (type) {
 307                 case DOM_NODE_ELEMENT:
 308                         if (node->data.element.type == subtype)
 309                                 return node;
 310                         break;
 311
 312                 case DOM_NODE_ATTRIBUTE:
 313                         if (node->data.attribute.type == subtype)
 314                                 return node;
 315                         break;
 316
 317                 case DOM_NODE_PROCESSING_INSTRUCTION:
 318                         if (node->data.attribute.type == subtype)
 319                                 return node;
 320                         break;
 321
 322                 default:
 323                         return node;
 324                 }
 325         }
 326
 327         return NULL;
 328 }
 329
 330
 331 /* Nodes */
 332
 333 struct dom_node *
 334 init_dom_node_at(
 335 #ifdef DEBUG_MEMLEAK
 336                 unsigned char *file, int line,
 337 #endif
 338                 struct dom_node *parent, enum dom_node_type type,
 339                 struct dom_string *string, int allocated)
 340 {
 341 #ifdef DEBUG_MEMLEAK
 342         struct dom_node *node = debug_mem_calloc(file, line, 1, sizeof(*node));
 343 #else
 344         struct dom_node *node = mem_calloc(1, sizeof(*node));
 345 #endif
 346
 347         if (!node) return NULL;
 348
 349         node->type   = type;
 350         node->parent = parent;
 351
 352         /* Make it possible to add a node to a parent without allocating the
 353          * strings. */
 354         if (allocated >= 0) {
 355                 node->allocated = !!allocated;
 356         } else if (parent) {
 357                 node->allocated = parent->allocated;
 358         }
 359
 360         if (node->allocated) {
 361                 if (!init_dom_string(&node->string, string->string, string->length)) {
 362                         done_dom_node(node);
 363                         return NULL;
 364                 }
 365         } else {
 366                 copy_dom_string(&node->string, string);
 367         }
 368
 369         if (parent) {
 370                 struct dom_node_list **list = get_dom_node_list(parent, node);
 371                 int sort = (type == DOM_NODE_ATTRIBUTE);
 372                 int index;
 373
 374                 assertm(list != NULL, "Adding node %d to bad parent %d",
 375                         node->type, parent->type);
 376
 377                 index = *list && (*list)->size > 0 && sort
 378                       ? get_dom_node_map_index(*list, node) : -1;
 379
 380                 if (!add_to_dom_node_list(list, node, index)) {
 381                         done_dom_node(node);
 382                         return NULL;
 383                 }
 384         }
 385
 386         return node;
 387 }
 388
 389 void
 390 done_dom_node_data(struct dom_node *node)
 391 {
 392         union dom_node_data *data;
 393
 394         assert(node);
 395
 396         data = &node->data;
 397
 398         switch (node->type) {
 399         case DOM_NODE_ATTRIBUTE:
 400                 if (node->allocated)
 401                         done_dom_string(&data->attribute.value);
 402                 break;
 403
 404         case DOM_NODE_DOCUMENT:
 405                 if (data->document.children)
 406                         done_dom_node_list(data->document.children);
 407                 break;
 408
 409         case DOM_NODE_ELEMENT:
 410                 if (data->element.children)
 411                         done_dom_node_list(data->element.children);
 412
 413                 if (data->element.map)
 414                         done_dom_node_list(data->element.map);
 415                 break;
 416
 417         case DOM_NODE_PROCESSING_INSTRUCTION:
 418                 if (data->proc_instruction.map)
 419                         done_dom_node_list(data->proc_instruction.map);
 420                 if (node->allocated)
 421                         done_dom_string(&data->proc_instruction.instruction);
 422                 break;
 423
 424         default:
 425                 break;
 426         }
 427
 428         if (node->allocated)
 429                 done_dom_string(&node->string);
 430         mem_free(node);
 431 }
 432
 433 void
 434 done_dom_node(struct dom_node *node)
 435 {
 436         assert(node);
 437
 438         if (node->parent) {
 439                 struct dom_node *parent = node->parent;
 440                 union dom_node_data *data = &parent->data;
 441
 442                 switch (parent->type) {
 443                 case DOM_NODE_DOCUMENT:
 444                         del_from_dom_node_list(data->document.children, node);
 445                         break;
 446
 447                 case DOM_NODE_ELEMENT:
 448                         del_from_dom_node_list(data->element.children, node);
 449                         del_from_dom_node_list(data->element.map, node);
 450                         break;
 451
 452                 case DOM_NODE_PROCESSING_INSTRUCTION:
 453                         del_from_dom_node_list(data->proc_instruction.map, node);
 454                         break;
 455
 456                 default:
 457                         break;
 458                 }
 459         }
 460
 461         done_dom_node_data(node);
 462 }
 463
 464 #define set_node_name(name, namelen, str)       \
 465         do { (name) = (str); (namelen) = sizeof(str) - 1; } while (0)
 466
 467 struct dom_string *
 468 get_dom_node_name(struct dom_node *node)
 469 {
 470         static struct dom_string cdata_section_str = STATIC_DOM_STRING("#cdata-section");
 471         static struct dom_string comment_str = STATIC_DOM_STRING("#comment");
 472         static struct dom_string document_str = STATIC_DOM_STRING("#document");
 473         static struct dom_string document_fragment_str = STATIC_DOM_STRING("#document-fragment");
 474         static struct dom_string text_str = STATIC_DOM_STRING("#text");
 475
 476         assert(node);
 477
 478         switch (node->type) {
 479         case DOM_NODE_CDATA_SECTION:
 480                 return &cdata_section_str;
 481
 482         case DOM_NODE_COMMENT:
 483                 return &comment_str;
 484
 485         case DOM_NODE_DOCUMENT:
 486                 return &document_str;
 487
 488         case DOM_NODE_DOCUMENT_FRAGMENT:
 489                 return &document_fragment_str;
 490
 491         case DOM_NODE_TEXT:
 492                 return &text_str;
 493
 494         case DOM_NODE_ATTRIBUTE:
 495         case DOM_NODE_DOCUMENT_TYPE:
 496         case DOM_NODE_ELEMENT:
 497         case DOM_NODE_ENTITY:
 498         case DOM_NODE_ENTITY_REFERENCE:
 499         case DOM_NODE_NOTATION:
 500         case DOM_NODE_PROCESSING_INSTRUCTION:
 501         default:
 502                 return &node->string;
 503         }
 504 }
 505
 506 struct dom_string *
 507 get_dom_node_value(struct dom_node *node)
 508 {
 509         assert(node);
 510
 511         switch (node->type) {
 512         case DOM_NODE_ATTRIBUTE:
 513                 return &node->data.attribute.value;
 514
 515         case DOM_NODE_PROCESSING_INSTRUCTION:
 516                 return &node->data.proc_instruction.instruction;
 517
 518         case DOM_NODE_CDATA_SECTION:
 519         case DOM_NODE_COMMENT:
 520         case DOM_NODE_TEXT:
 521                 return &node->string;
 522
 523         case DOM_NODE_ENTITY_REFERENCE:
 524         case DOM_NODE_NOTATION:
 525         case DOM_NODE_DOCUMENT:
 526         case DOM_NODE_DOCUMENT_FRAGMENT:
 527         case DOM_NODE_DOCUMENT_TYPE:
 528         case DOM_NODE_ELEMENT:
 529         case DOM_NODE_ENTITY:
 530         default:
 531                 return NULL;
 532         }
 533 }
 534
 535 struct dom_string *
 536 get_dom_node_type_name(enum dom_node_type type)
 537 {
 538         static struct dom_string dom_node_type_names[DOM_NODES] = {
 539                 INIT_DOM_STRING(NULL, 0),
 540                 /* DOM_NODE_ELEMENT */                  STATIC_DOM_STRING("element"),
 541                 /* DOM_NODE_ATTRIBUTE */                STATIC_DOM_STRING("attribute"),
 542                 /* DOM_NODE_TEXT */                     STATIC_DOM_STRING("text"),
 543                 /* DOM_NODE_CDATA_SECTION */            STATIC_DOM_STRING("cdata-section"),
 544                 /* DOM_NODE_ENTITY_REFERENCE */         STATIC_DOM_STRING("entity-reference"),
 545                 /* DOM_NODE_ENTITY */                   STATIC_DOM_STRING("entity"),
 546                 /* DOM_NODE_PROCESSING_INSTRUCTION */   STATIC_DOM_STRING("proc-instruction"),
 547                 /* DOM_NODE_COMMENT */                  STATIC_DOM_STRING("comment"),
 548                 /* DOM_NODE_DOCUMENT */                 STATIC_DOM_STRING("document"),
 549                 /* DOM_NODE_DOCUMENT_TYPE */            STATIC_DOM_STRING("document-type"),
 550                 /* DOM_NODE_DOCUMENT_FRAGMENT */        STATIC_DOM_STRING("document-fragment"),
 551                 /* DOM_NODE_NOTATION */                 STATIC_DOM_STRING("notation"),
 552         };
 553
 554         assert(type < DOM_NODES);
 555
 556         return &dom_node_type_names[type];
 557 }