Sergei G / LinkedList

Important changes to repositories hosted on mbed.com

Mbed hosted mercurial repositories are deprecated and are due to be permanently deleted in July 2026.

To keep a copy of this software download the repository Zip archive or clone locally using Mercurial.

It is also possible to export all your personal repositories from the account settings page.

Dependents:   JobScheduler

Fork of LinkedList by Sam Grove

LinkedList.cpp@4:59b2aa82b517, 2013-04-10 (annotated)

Committer:
sam_grove
Date:
Wed Apr 10 06:17:21 2013 +0000
Revision:
4:59b2aa82b517
Parent:
3:c14e7a918e21
Child:
5:28e11c75b433
removed setting _head->next to 0 in the constructor. Was writing to uninitialized (unallocated) memory location

Who changed what in which revision?

UserRevisionLine numberNew contents of line
sam_grove 0:3f64a15357ac 1 /**
sam_grove 0:3f64a15357ac 2 * @file LinkedList.cpp
sam_grove 0:3f64a15357ac 3 * @brief Core Utility - Templated Linked List class
sam_grove 0:3f64a15357ac 4 * @author sam grove
sam_grove 0:3f64a15357ac 5 * @version 1.0
sam_grove 0:3f64a15357ac 6 * @see
sam_grove 0:3f64a15357ac 7 *
sam_grove 0:3f64a15357ac 8 * Copyright (c) 2013
sam_grove 0:3f64a15357ac 9 *
sam_grove 0:3f64a15357ac 10 * Licensed under the Apache License, Version 2.0 (the "License");
sam_grove 0:3f64a15357ac 11 * you may not use this file except in compliance with the License.
sam_grove 0:3f64a15357ac 12 * You may obtain a copy of the License at
sam_grove 0:3f64a15357ac 13 *
sam_grove 0:3f64a15357ac 14 * http://www.apache.org/licenses/LICENSE-2.0
sam_grove 0:3f64a15357ac 15 *
sam_grove 0:3f64a15357ac 16 * Unless required by applicable law or agreed to in writing, software
sam_grove 0:3f64a15357ac 17 * distributed under the License is distributed on an "AS IS" BASIS,
sam_grove 0:3f64a15357ac 18 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
sam_grove 0:3f64a15357ac 19 * See the License for the specific language governing permissions and
sam_grove 0:3f64a15357ac 20 * limitations under the License.
sam_grove 0:3f64a15357ac 21 */
sam_grove 0:3f64a15357ac 22
sam_grove 0:3f64a15357ac 23 #include "LinkedList.h" // api wrapper
sam_grove 1:a032c0392ba1 24 #include "LogUtil.h"
sam_grove 0:3f64a15357ac 25
sam_grove 0:3f64a15357ac 26 template<class retT>
sam_grove 0:3f64a15357ac 27 LinkedList<retT>::LinkedList()
sam_grove 0:3f64a15357ac 28 {
sam_grove 4:59b2aa82b517 29 // clear the member
sam_grove 0:3f64a15357ac 30 _head = 0;
sam_grove 4:59b2aa82b517 31 // _head->next = 0;
sam_grove 0:3f64a15357ac 32
sam_grove 0:3f64a15357ac 33 return;
sam_grove 0:3f64a15357ac 34 }
sam_grove 0:3f64a15357ac 35
sam_grove 0:3f64a15357ac 36 template<class retT>
sam_grove 0:3f64a15357ac 37 LinkedList<retT>::~LinkedList()
sam_grove 0:3f64a15357ac 38 {
sam_grove 0:3f64a15357ac 39 // free any memory that is on the heap
sam_grove 0:3f64a15357ac 40 while(0 != length())
sam_grove 0:3f64a15357ac 41 {
sam_grove 0:3f64a15357ac 42 LinkedList::remove(1);
sam_grove 0:3f64a15357ac 43 }
sam_grove 0:3f64a15357ac 44
sam_grove 0:3f64a15357ac 45 return;
sam_grove 0:3f64a15357ac 46 }
sam_grove 0:3f64a15357ac 47
sam_grove 0:3f64a15357ac 48 template<class retT>
sam_grove 0:3f64a15357ac 49 retT *LinkedList<retT>::push(void *data)
sam_grove 0:3f64a15357ac 50 {
sam_grove 0:3f64a15357ac 51 retT *new_node = new retT [1];
sam_grove 0:3f64a15357ac 52 // make sure the new object was allocated
sam_grove 0:3f64a15357ac 53 if (0 == new_node)
sam_grove 0:3f64a15357ac 54 {
sam_grove 1:a032c0392ba1 55 ERROR("Memory allocation failed\n");
sam_grove 0:3f64a15357ac 56 }
sam_grove 0:3f64a15357ac 57 // update the next item in the list to the current head
sam_grove 0:3f64a15357ac 58 new_node->next = _head;
sam_grove 0:3f64a15357ac 59 // store the address to the linked datatype
sam_grove 0:3f64a15357ac 60 new_node->data = data;
sam_grove 0:3f64a15357ac 61 _head = new_node;
sam_grove 0:3f64a15357ac 62
sam_grove 0:3f64a15357ac 63 return _head;
sam_grove 0:3f64a15357ac 64 }
sam_grove 0:3f64a15357ac 65
sam_grove 1:a032c0392ba1 66 //template<class retT>
sam_grove 1:a032c0392ba1 67 //retT *LinkedList<retT>::insert(void *data, uint32_t loc)
sam_grove 1:a032c0392ba1 68 //{
sam_grove 1:a032c0392ba1 69 // retT *new_node = new retT [1];
sam_grove 1:a032c0392ba1 70 // // make sure the new object was allocated
sam_grove 1:a032c0392ba1 71 // if (0 == new_node)
sam_grove 1:a032c0392ba1 72 // {
sam_grove 1:a032c0392ba1 73 // ERROR("Memory allocation failed\n");
sam_grove 1:a032c0392ba1 74 // }
sam_grove 1:a032c0392ba1 75 // retT *current = _head->next;
sam_grove 1:a032c0392ba1 76 // retT *prev = _head;
sam_grove 1:a032c0392ba1 77 // // move to the item we want to insert
sam_grove 1:a032c0392ba1 78 // for (uint32_t i=1; i!=(loc-1); i++)
sam_grove 1:a032c0392ba1 79 // {
sam_grove 1:a032c0392ba1 80 // prev = current;
sam_grove 1:a032c0392ba1 81 // current = current->next;
sam_grove 1:a032c0392ba1 82 // }
sam_grove 1:a032c0392ba1 83 // // store the address to the linked datatype
sam_grove 1:a032c0392ba1 84 // new_node->data = data;
sam_grove 1:a032c0392ba1 85 // // clear the next pointer
sam_grove 1:a032c0392ba1 86 // new_node->next = 0;
sam_grove 1:a032c0392ba1 87 // // update the list and store the new stuff
sam_grove 1:a032c0392ba1 88 // prev->next = new_node;
sam_grove 1:a032c0392ba1 89 // new_node->next = current;
sam_grove 1:a032c0392ba1 90 // // store the address to the linked datatype
sam_grove 1:a032c0392ba1 91 // _head->data = data;
sam_grove 1:a032c0392ba1 92 //
sam_grove 1:a032c0392ba1 93 // return prev->next;
sam_grove 1:a032c0392ba1 94 //}
sam_grove 0:3f64a15357ac 95
sam_grove 0:3f64a15357ac 96 template<class retT>
sam_grove 0:3f64a15357ac 97 retT *LinkedList<retT>::append(void *data)
sam_grove 0:3f64a15357ac 98 {
sam_grove 0:3f64a15357ac 99 retT *current = _head;
sam_grove 0:3f64a15357ac 100 retT *new_node = new retT [1];
sam_grove 0:3f64a15357ac 101 // make sure the new object was allocated
sam_grove 0:3f64a15357ac 102 if (0 == new_node)
sam_grove 0:3f64a15357ac 103 {
sam_grove 1:a032c0392ba1 104 ERROR("Memory allocation failed\n");
sam_grove 0:3f64a15357ac 105 }
sam_grove 0:3f64a15357ac 106 // store the address to the linked datatype
sam_grove 0:3f64a15357ac 107 new_node->data = data;
sam_grove 0:3f64a15357ac 108 // clear the next pointer
sam_grove 0:3f64a15357ac 109 new_node->next = 0;
sam_grove 0:3f64a15357ac 110 // check for an empty list
sam_grove 0:3f64a15357ac 111 if (0 == current)
sam_grove 0:3f64a15357ac 112 {
sam_grove 0:3f64a15357ac 113 _head = new_node;
sam_grove 0:3f64a15357ac 114 return _head;
sam_grove 0:3f64a15357ac 115 }
sam_grove 0:3f64a15357ac 116 else
sam_grove 0:3f64a15357ac 117 {
sam_grove 0:3f64a15357ac 118 // look for the end of the list
sam_grove 0:3f64a15357ac 119 while (current->next != 0)
sam_grove 0:3f64a15357ac 120 {
sam_grove 0:3f64a15357ac 121 current = current->next;
sam_grove 0:3f64a15357ac 122 }
sam_grove 0:3f64a15357ac 123 // and then add the new item to the list
sam_grove 0:3f64a15357ac 124 current->next = new_node;
sam_grove 0:3f64a15357ac 125 }
sam_grove 0:3f64a15357ac 126
sam_grove 0:3f64a15357ac 127 return current->next;
sam_grove 0:3f64a15357ac 128 }
sam_grove 0:3f64a15357ac 129
sam_grove 0:3f64a15357ac 130 template<class retT>
sam_grove 0:3f64a15357ac 131 retT *LinkedList<retT>::remove(uint32_t loc)
sam_grove 0:3f64a15357ac 132 {
sam_grove 0:3f64a15357ac 133 retT *current = _head;
sam_grove 1:a032c0392ba1 134 retT *prev = 0;
sam_grove 0:3f64a15357ac 135 // make sure we have an item to remove
sam_grove 3:c14e7a918e21 136 if ((loc < length()) && (loc > 0))
sam_grove 0:3f64a15357ac 137 {
sam_grove 0:3f64a15357ac 138 // move to the item we want to delete
sam_grove 3:c14e7a918e21 139 if (1 == loc)
sam_grove 0:3f64a15357ac 140 {
sam_grove 0:3f64a15357ac 141 _head = current->next;
sam_grove 0:3f64a15357ac 142 delete [] current;
sam_grove 0:3f64a15357ac 143 }
sam_grove 0:3f64a15357ac 144 else
sam_grove 0:3f64a15357ac 145 {
sam_grove 3:c14e7a918e21 146 for (uint32_t i=2; i<=loc; ++i)
sam_grove 0:3f64a15357ac 147 {
sam_grove 0:3f64a15357ac 148 prev = current;
sam_grove 0:3f64a15357ac 149 current = current->next;
sam_grove 0:3f64a15357ac 150 }
sam_grove 0:3f64a15357ac 151 // store the item + 1 to replace what we are deleting
sam_grove 0:3f64a15357ac 152 prev->next = current->next;
sam_grove 0:3f64a15357ac 153 delete [] current;
sam_grove 0:3f64a15357ac 154 }
sam_grove 0:3f64a15357ac 155 }
sam_grove 0:3f64a15357ac 156
sam_grove 0:3f64a15357ac 157 return _head;
sam_grove 0:3f64a15357ac 158 }
sam_grove 0:3f64a15357ac 159
sam_grove 0:3f64a15357ac 160 template<class retT>
sam_grove 0:3f64a15357ac 161 retT *LinkedList<retT>::pop(uint32_t loc)
sam_grove 0:3f64a15357ac 162 {
sam_grove 0:3f64a15357ac 163 retT *current = _head;
sam_grove 0:3f64a15357ac 164 // make sure we have something in the location
sam_grove 3:c14e7a918e21 165 if ((loc > length()) || (loc == 0))
sam_grove 0:3f64a15357ac 166 {
sam_grove 0:3f64a15357ac 167 return 0;
sam_grove 0:3f64a15357ac 168 }
sam_grove 0:3f64a15357ac 169 // and if so jump down the list
sam_grove 3:c14e7a918e21 170 for (uint32_t i=2; i<=loc; ++i)
sam_grove 0:3f64a15357ac 171 {
sam_grove 0:3f64a15357ac 172 current = current->next;
sam_grove 0:3f64a15357ac 173 }
sam_grove 0:3f64a15357ac 174
sam_grove 0:3f64a15357ac 175 return current;
sam_grove 0:3f64a15357ac 176 }
sam_grove 0:3f64a15357ac 177
sam_grove 0:3f64a15357ac 178 template<class retT>
sam_grove 0:3f64a15357ac 179 uint32_t LinkedList<retT>::length(void)
sam_grove 0:3f64a15357ac 180 {
sam_grove 3:c14e7a918e21 181 int32_t count = 0;
sam_grove 0:3f64a15357ac 182 retT *current = _head;
sam_grove 0:3f64a15357ac 183 //loop until the end of the list is found
sam_grove 0:3f64a15357ac 184 while (current != 0)
sam_grove 0:3f64a15357ac 185 {
sam_grove 3:c14e7a918e21 186 ++count;
sam_grove 0:3f64a15357ac 187 current = current->next;
sam_grove 0:3f64a15357ac 188 }
sam_grove 0:3f64a15357ac 189
sam_grove 0:3f64a15357ac 190 return count;
sam_grove 0:3f64a15357ac 191 }
sam_grove 0:3f64a15357ac 192
sam_grove 1:a032c0392ba1 193 // pre-define the type for the linker
sam_grove 0:3f64a15357ac 194 template class LinkedList<node>;
sam_grove 0:3f64a15357ac 195
sam_grove 0:3f64a15357ac 196
sam_grove 0:3f64a15357ac 197
sam_grove 0:3f64a15357ac 198
sam_grove 0:3f64a15357ac 199