Subversion Repositories Kolibri OS

Rev

Go to most recent revision | Blame | Last modification | View Log | Download | RSS feed

  1. /*
  2.  * This file is part of libdom test suite.
  3.  * Licensed under the MIT License,
  4.  *                              http://www.opensource.org/licenses/mit-license.php
  5.  * Copyright 2007 James Shaw <jshaw@netsurf-browser.org>
  6.  * Copyright 2009 Bo Yang <struggeleyb.nku@gmail.com>
  7.  */
  8.  
  9.  
  10. #include <stdbool.h>
  11. #include <stdio.h>
  12. #include <stdlib.h>
  13.  
  14. #include <dom/core/string.h>
  15. #include <dom/core/node.h>
  16.  
  17. #include "comparators.h"
  18. #include "list.h"
  19. #include "domtsasserts.h"
  20.  
  21. /**
  22.  * Private helper function.
  23.  * Create a new list_elt and initialise it.
  24.  */
  25. struct list_elt* list_new_elt(void* data);
  26.  
  27. struct list_elt* list_new_elt(void* data) {
  28.         struct list_elt* elt = malloc(sizeof(struct list_elt));
  29.         assert(elt != NULL);
  30.         elt->data = data;
  31.         elt->next = NULL;
  32.         return elt;
  33. }
  34.  
  35. struct list* list_new(TYPE type)
  36. {
  37.         struct list* list = malloc(sizeof(struct list));
  38.         assert(list != NULL);
  39.         list->size = 0;
  40.         list->type = type;
  41.         list->head = NULL;
  42.         list->tail = NULL;
  43.         return list;
  44. }
  45.  
  46. void list_destroy(struct list* list)
  47. {
  48.         struct list_elt* elt = list->head;
  49.         while (elt != NULL) {
  50.                 if (list->type == DOM_STRING)
  51.                         dom_string_unref((dom_string *) elt->data);
  52.                 if (list->type == NODE)
  53.                         dom_node_unref(elt->data);
  54.                 struct list_elt* nextElt = elt->next;
  55.                 free(elt);
  56.                 elt = nextElt;
  57.         }
  58.         free(list);
  59. }
  60.  
  61. void list_add(struct list* list, void* data)
  62. {
  63.         struct list_elt* elt = list_new_elt(data);
  64.         struct list_elt* tail = list->tail;
  65.  
  66.         /* if tail was set, make its 'next' ptr point to elt */
  67.         if (tail != NULL) {
  68.                 tail->next = elt;
  69.         }
  70.  
  71.         /* make elt the new tail */
  72.         list->tail = elt;
  73.  
  74.         if (list->head == NULL) {
  75.                 list->head = elt;
  76.         }
  77.  
  78.         /* inc the size of the list */
  79.         list->size++;
  80.         if (list->type == DOM_STRING)
  81.                 dom_string_ref((dom_string *) data);
  82.         if (list->type == NODE)
  83.                 dom_node_ref(data);
  84. }
  85.  
  86. bool list_remove(struct list* list, void* data)
  87. {      
  88.         struct list_elt* prevElt = NULL;
  89.         struct list_elt* elt = list->head;
  90.        
  91.         bool found = false;
  92.        
  93.         while (elt != NULL) {
  94.                 struct list_elt* nextElt = elt->next;
  95.                
  96.                 /* if data is identical, fix up pointers, and free the element */
  97.                 if (data == elt->data) {
  98.                         if (prevElt == NULL) {
  99.                                 list->head = nextElt;
  100.                         } else {
  101.                                 prevElt->next = nextElt;
  102.                         }
  103.                         free(elt);
  104.                         list->size--;
  105.                         found = true;
  106.                         break;
  107.                 }
  108.                
  109.                 prevElt = elt;
  110.                 elt = nextElt;
  111.         }
  112.        
  113.         return found;
  114. }
  115.  
  116. struct list* list_clone(struct list* list)
  117. {
  118.         struct list* newList = list_new(list->type);
  119.         struct list_elt* elt = list->head;
  120.        
  121.         while (elt != NULL) {
  122.                 list_add(newList, elt->data);
  123.                 elt = elt->next;
  124.         }
  125.        
  126.         return newList;
  127. }
  128.  
  129. bool list_contains(struct list* list, void* data, comparator comparator)
  130. {
  131.         struct list_elt* elt = list->head;
  132.         while (elt != NULL) {
  133.                 if (comparator(elt->data, data) == 0) {
  134.                         return true;
  135.                 }
  136.                 elt = elt->next;
  137.         }
  138.         return false;
  139. }
  140.  
  141. bool list_contains_all(struct list* superList, struct list* subList,
  142.                 comparator comparator)
  143. {
  144.         struct list_elt* subElt = subList->head;
  145.         struct list* superListClone = list_clone(superList);
  146.        
  147.         bool found = true;
  148.        
  149.         while (subElt != NULL) {
  150.                 struct list_elt* superElt = superListClone->head;
  151.  
  152.                 found = false;
  153.                 while (superElt != NULL && found == false) {
  154.                         if (comparator(superElt->data, subElt->data) == 0) {
  155.                                 found = true;
  156.                                 list_remove(superListClone, superElt->data);
  157.                                 break;
  158.                         }
  159.                         superElt = superElt->next;
  160.                 }
  161.                
  162.                 if (found == false)
  163.                         break;
  164.                 subElt = subElt->next;
  165.         }
  166.  
  167.         free(superListClone);
  168.        
  169.         return found;
  170. }
  171.  
  172.