Go to most recent revision | Details | Last modification | View Log | RSS feed
| Rev | Author | Line No. | Line |
|---|---|---|---|
| 3584 | sourcerer | 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 |
||
| 6 | * Copyright 2009 Bo Yang |
||
| 7 | */ |
||
| 8 | |||
| 9 | |||
| 10 | #include |
||
| 11 | #include |
||
| 12 | #include |
||
| 13 | |||
| 14 | #include |
||
| 15 | #include |
||
| 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 |