1/* 2 * Copyright (c) 2000-2004,2006-2007,2011 Apple Inc. All Rights Reserved. 3 * 4 * @APPLE_LICENSE_HEADER_START@ 5 * 6 * This file contains Original Code and/or Modifications of Original Code 7 * as defined in and that are subject to the Apple Public Source License 8 * Version 2.0 (the 'License'). You may not use this file except in 9 * compliance with the License. Please obtain a copy of the License at 10 * http://www.opensource.apple.com/apsl/ and read it before using this 11 * file. 12 * 13 * The Original Code and all software distributed under the License are 14 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER 15 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, 16 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, 17 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT. 18 * Please see the License for the specific language governing rights and 19 * limitations under the License. 20 * 21 * @APPLE_LICENSE_HEADER_END@ 22 */ 23 24 25// 26// cssmlist - CSSM_LIST operational utilities 27// 28#include <security_cdsa_utilities/cssmlist.h> 29#include <security_cdsa_utilities/cssmdata.h> 30 31 32// 33// Managing list elements 34// 35ListElement *ListElement::last() 36{ 37 for (ListElement *p = this; ; p = p->next()) 38 if (p->next() == NULL) 39 return p; 40 // not reached 41} 42 43 44ListElement::ListElement(CSSM_WORDID_TYPE word) 45{ 46 ElementType = CSSM_LIST_ELEMENT_WORDID; 47 WordID = word; 48} 49 50ListElement::ListElement(const CssmData &data) 51{ 52 ElementType = CSSM_LIST_ELEMENT_DATUM; 53 WordID = 0; 54 Element.Word = data; 55} 56 57ListElement::ListElement(Allocator &alloc, const CssmData &data) 58{ 59 ElementType = CSSM_LIST_ELEMENT_DATUM; 60 WordID = 0; 61 Element.Word = CssmAutoData(alloc, data).release(); 62} 63 64ListElement::ListElement(Allocator &alloc, const string &s) 65{ 66 ElementType = CSSM_LIST_ELEMENT_DATUM; 67 WordID = 0; 68 Element.Word = CssmAutoData(alloc, s.data(), s.size()).release(); 69} 70 71ListElement::ListElement(const CssmList &list) 72{ 73 ElementType = CSSM_LIST_ELEMENT_SUBLIST; 74 WordID = 0; 75 Element.Sublist = list; 76} 77 78 79CssmData &ListElement::data() 80{ 81 assert(type() == CSSM_LIST_ELEMENT_DATUM); 82 return CssmData::overlay(Element.Word); 83} 84 85const CssmData &ListElement::data() const 86{ 87 assert(type() == CSSM_LIST_ELEMENT_DATUM); 88 return CssmData::overlay(Element.Word); 89} 90 91ListElement &ListElement::operator = (const CssmData &data) 92{ 93 assert(type() == CSSM_LIST_ELEMENT_DATUM); 94 Element.Word = data; 95 return *this; 96} 97 98 99CssmList &ListElement::list() 100{ 101 assert(type() == CSSM_LIST_ELEMENT_SUBLIST); 102 return CssmList::overlay(Element.Sublist); 103} 104 105const CssmList &ListElement::list() const 106{ 107 assert(type() == CSSM_LIST_ELEMENT_SUBLIST); 108 return CssmList::overlay(Element.Sublist); 109} 110 111TypedList &ListElement::typedList() 112{ 113 return static_cast<TypedList &>(list()); 114} 115 116const TypedList &ListElement::typedList() const 117{ 118 return static_cast<const TypedList &>(list()); 119} 120 121ListElement &ListElement::operator = (const CssmList &list) 122{ 123 assert(type() == CSSM_LIST_ELEMENT_SUBLIST); 124 Element.Sublist = list; 125 return *this; 126} 127 128 129CSSM_WORDID_TYPE ListElement::word() const 130{ 131 assert(type() == CSSM_LIST_ELEMENT_WORDID); 132 return WordID; 133} 134 135ListElement &ListElement::operator = (CSSM_WORDID_TYPE word) 136{ 137 assert(type() == CSSM_LIST_ELEMENT_WORDID); 138 WordID = word; 139 return *this; 140} 141 142 143// 144// List operations 145// 146ListElement &CssmList::operator [] (unsigned ix) const 147{ 148 for (ListElement *elem = first(); elem; elem = elem->next(), ix--) { 149 if (ix == 0) 150 return *elem; 151 } 152 throw 999; //@@@ 153} 154 155unsigned int CssmList::length() const 156{ 157 unsigned int len = 0; 158 for (ListElement *elem = first(); elem; elem = elem->next()) 159 len++; 160 return len; 161} 162 163CssmList &CssmList::append(ListElement *elem) 164{ 165 if (Tail == NULL) { // first element 166 Head = Tail = elem; 167 } else { 168 Tail->NextElement = elem; 169 Tail = elem; 170 } 171 elem->NextElement = NULL; 172 return *this; 173} 174 175CssmList &CssmList::insert(ListElement *elem, ListElement *before) 176{ 177 // null before -> append 178 if (before == NULL) 179 return append(elem); 180 181 // we have a real position 182 assert(!empty()); 183 if (Head == before) { // before first element 184 elem->NextElement = before; 185 Head = elem; 186 } else { // before is not first 187 for (CSSM_LIST_ELEMENT *p = Head; p; p = p->NextElement) { 188 if (p->NextElement == before) { 189 elem->NextElement = before; 190 p->NextElement = elem; 191 return *this; 192 } 193 } 194 // end of list, before not in list 195 throw 999; //@@@ 196 } 197 return *this; 198} 199 200CssmList &CssmList::remove(ListElement *elem) 201{ 202 assert(elem); 203 if (elem == Head) { // remove first element 204 Head = Head->NextElement; 205 } else { // subsequent element 206 for (CSSM_LIST_ELEMENT *p = Head; p; p = p->NextElement) 207 if (p->NextElement == elem) { 208 p->NextElement = elem->NextElement; 209 if (elem->NextElement == NULL) // removing last element 210 Tail = p; 211 return *this; 212 } 213 // end of list, elem not found 214 throw 999; //@@@ 215 } 216 return *this; 217} 218 219void CssmList::snip() 220{ 221 assert(Head); // can't be empty 222 if (Head == Tail) { // single element, empty when snipped 223 Head = Tail = NULL; 224 } else { // more than one, bypass first 225 Head = first()->next(); 226 } 227} 228 229 230// 231// Deep-destruction of CssmLists and ListElements. 232// The underlying assumption is that all components were allocated from a single 233// Allocator in canonical chunks. 234// 235void ListElement::clear(Allocator &alloc) 236{ 237 switch (type()) { 238 case CSSM_LIST_ELEMENT_WORDID: 239 break; // no substructure 240 case CSSM_LIST_ELEMENT_DATUM: 241 alloc.free(data().data()); 242 break; 243 case CSSM_LIST_ELEMENT_SUBLIST: 244 list().clear(alloc); 245 break; 246 default: 247 assert(false); 248 } 249} 250 251void CssmList::clear(Allocator &alloc) 252{ 253 ListElement *elem = first(); 254 while (elem) { 255 ListElement *next = elem->next(); 256 destroy(elem, alloc); 257 elem = next; 258 } 259} 260 261 262// 263// Building TypedLists 264// 265TypedList::TypedList(Allocator &alloc, CSSM_WORDID_TYPE type) 266{ 267 append(new(alloc) ListElement(type)); 268} 269 270TypedList::TypedList(Allocator &alloc, CSSM_WORDID_TYPE type, ListElement *elem1) 271{ 272 append(new(alloc) ListElement(type)); 273 append(elem1); 274} 275 276TypedList::TypedList(Allocator &alloc, CSSM_WORDID_TYPE type, ListElement *elem1, ListElement *elem2) 277{ 278 append(new(alloc) ListElement(type)); 279 append(elem1); 280 append(elem2); 281} 282 283TypedList::TypedList(Allocator &alloc, CSSM_WORDID_TYPE type, ListElement *elem1, ListElement *elem2, ListElement *elem3) 284{ 285 append(new(alloc) ListElement(type)); 286 append(elem1); 287 append(elem2); 288 append(elem3); 289} 290 291TypedList::TypedList(Allocator &alloc, CSSM_WORDID_TYPE type, ListElement *elem1, ListElement *elem2, ListElement *elem3, ListElement *elem4) 292{ 293 append(new(alloc) ListElement(type)); 294 append(elem1); 295 append(elem2); 296 append(elem3); 297 append(elem4); 298} 299 300 301// 302// Verify that a TypedList is "proper", i.e. has a first element of WORDID form 303// 304bool TypedList::isProper() const 305{ 306 return first() && first()->type() == CSSM_LIST_ELEMENT_WORDID; 307} 308 309void TypedList::checkProper(CSSM_RETURN error) const 310{ 311 if (!isProper()) 312 CssmError::throwMe(error); 313} 314