OSX/libsecurity_cdsa_utilities/lib/cssmlist.cpp

   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 //
  35 ListElement *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
  44 ListElement::ListElement(CSSM_WORDID_TYPE word)
  45 {
  46         ElementType = CSSM_LIST_ELEMENT_WORDID;
  47         WordID = word;
  48 }
  49
  50 ListElement::ListElement(const CssmData &data)
  51 {
  52         ElementType = CSSM_LIST_ELEMENT_DATUM;
  53         WordID = 0;
  54         Element.Word = data;
  55 }
  56
  57 ListElement::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
  64 ListElement::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
  71 ListElement::ListElement(const CssmList &list)
  72 {
  73         ElementType = CSSM_LIST_ELEMENT_SUBLIST;
  74         WordID = 0;
  75         Element.Sublist = list;
  76 }
  77
  78
  79 CssmData &ListElement::data()
  80 {
  81         assert(type() == CSSM_LIST_ELEMENT_DATUM);
  82         return CssmData::overlay(Element.Word);
  83 }
  84
  85 const CssmData &ListElement::data() const
  86 {
  87         assert(type() == CSSM_LIST_ELEMENT_DATUM);
  88         return CssmData::overlay(Element.Word);
  89 }
  90
  91 ListElement &ListElement::operator = (const CssmData &data)
  92 {
  93         assert(type() == CSSM_LIST_ELEMENT_DATUM);
  94         Element.Word = data;
  95         return *this;
  96 }
  97
  98
  99 CssmList &ListElement::list()
 100 {
 101         assert(type() == CSSM_LIST_ELEMENT_SUBLIST);
 102         return CssmList::overlay(Element.Sublist);
 103 }
 104
 105 const CssmList &ListElement::list() const
 106 {
 107         assert(type() == CSSM_LIST_ELEMENT_SUBLIST);
 108         return CssmList::overlay(Element.Sublist);
 109 }
 110
 111 TypedList &ListElement::typedList()
 112 {
 113         return static_cast<TypedList &>(list());
 114 }
 115
 116 const TypedList &ListElement::typedList() const
 117 {
 118         return static_cast<const TypedList &>(list());
 119 }
 120
 121 ListElement &ListElement::operator = (const CssmList &list)
 122 {
 123         assert(type() == CSSM_LIST_ELEMENT_SUBLIST);
 124         Element.Sublist = list;
 125         return *this;
 126 }
 127
 128
 129 CSSM_WORDID_TYPE ListElement::word() const
 130 {
 131         assert(type() == CSSM_LIST_ELEMENT_WORDID);
 132         return WordID;
 133 }
 134
 135 ListElement &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 //
 146 ListElement &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
 155 CssmList &CssmList::operator =(const CssmList& other)
 156 {
 157     ListType = other.ListType;
 158     Head = other.Head;
 159     Tail = other.Tail;
 160     return *this;
 161 }
 162
 163 unsigned int CssmList::length() const
 164 {
 165         unsigned int len = 0;
 166         for (ListElement *elem = first(); elem; elem = elem->next())
 167                 len++;
 168         return len;
 169 }
 170
 171 CssmList &CssmList::append(ListElement *elem)
 172 {
 173         if (Tail == NULL) {     // first element
 174                 Head = Tail = elem;
 175         } else {
 176                 Tail->NextElement = elem;
 177                 Tail = elem;
 178         }
 179         elem->NextElement = NULL;
 180         return *this;
 181 }
 182
 183 CssmList &CssmList::insert(ListElement *elem, ListElement *before)
 184 {
 185         // null before -> append
 186         if (before == NULL)
 187                 return append(elem);
 188
 189         // we have a real position
 190         assert(!empty());
 191         if (Head == before) { // before first element
 192                 elem->NextElement = before;
 193                 Head = elem;
 194         } else { // before is not first
 195                 for (CSSM_LIST_ELEMENT *p = Head; p; p = p->NextElement) {
 196                         if (p->NextElement == before) {
 197                                 elem->NextElement = before;
 198                                 p->NextElement = elem;
 199                                 return *this;
 200                         }
 201                 }
 202                 // end of list, before not in list
 203                 throw 999;      //@@@
 204         }
 205         return *this;
 206 }
 207
 208 CssmList &CssmList::remove(ListElement *elem)
 209 {
 210         assert(elem);
 211         if (elem == Head) {     // remove first element
 212                 Head = Head->NextElement;
 213         } else { // subsequent element
 214                 for (CSSM_LIST_ELEMENT *p = Head; p; p = p->NextElement)
 215                         if (p->NextElement == elem) {
 216                                 p->NextElement = elem->NextElement;
 217                                 if (elem->NextElement == NULL) // removing last element
 218                                         Tail = p;
 219                                 return *this;
 220                         }
 221                 // end of list, elem not found
 222                 throw 999;      //@@@
 223         }
 224         return *this;
 225 }
 226
 227 void CssmList::snip()
 228 {
 229     assert(Head);       // can't be empty
 230     if (Head == Tail) { // single element, empty when snipped
 231         Head = Tail = NULL;
 232     } else {            // more than one, bypass first
 233         Head = first()->next();
 234     }
 235 }
 236
 237
 238 //
 239 // Deep-destruction of CssmLists and ListElements.
 240 // The underlying assumption is that all components were allocated from a single
 241 // Allocator in canonical chunks.
 242 //
 243 void ListElement::clear(Allocator &alloc)
 244 {
 245         switch (type()) {
 246         case CSSM_LIST_ELEMENT_WORDID:
 247                 break;  // no substructure
 248         case CSSM_LIST_ELEMENT_DATUM:
 249                 alloc.free(data().data());
 250                 break;
 251         case CSSM_LIST_ELEMENT_SUBLIST:
 252                 list().clear(alloc);
 253                 break;
 254         default:
 255                 assert(false);
 256         }
 257 }
 258
 259 void CssmList::clear(Allocator &alloc)
 260 {
 261         ListElement *elem = first();
 262         while (elem) {
 263                 ListElement *next = elem->next();
 264                 destroy(elem, alloc);
 265                 elem = next;
 266         }
 267 }
 268
 269
 270 //
 271 // Building TypedLists
 272 //
 273 TypedList::TypedList(Allocator &alloc, CSSM_WORDID_TYPE type)
 274 {
 275         append(new(alloc) ListElement(type));
 276 }
 277
 278 TypedList::TypedList(Allocator &alloc, CSSM_WORDID_TYPE type, ListElement *elem1)
 279 {
 280         append(new(alloc) ListElement(type));
 281         append(elem1);
 282 }
 283
 284 TypedList::TypedList(Allocator &alloc, CSSM_WORDID_TYPE type, ListElement *elem1, ListElement *elem2)
 285 {
 286         append(new(alloc) ListElement(type));
 287         append(elem1);
 288         append(elem2);
 289 }
 290
 291 TypedList::TypedList(Allocator &alloc, CSSM_WORDID_TYPE type, ListElement *elem1, ListElement *elem2, ListElement *elem3)
 292 {
 293         append(new(alloc) ListElement(type));
 294         append(elem1);
 295         append(elem2);
 296         append(elem3);
 297 }
 298
 299 TypedList::TypedList(Allocator &alloc, CSSM_WORDID_TYPE type, ListElement *elem1, ListElement *elem2, ListElement *elem3, ListElement *elem4)
 300 {
 301         append(new(alloc) ListElement(type));
 302         append(elem1);
 303         append(elem2);
 304         append(elem3);
 305         append(elem4);
 306 }
 307
 308
 309 //
 310 // Verify that a TypedList is "proper", i.e. has a first element of WORDID form
 311 //
 312 bool TypedList::isProper() const
 313 {
 314         return first() && first()->type() == CSSM_LIST_ELEMENT_WORDID;
 315 }
 316
 317 void TypedList::checkProper(CSSM_RETURN error) const
 318 {
 319         if (!isProper())
 320                 CssmError::throwMe(error);
 321 }