Security/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 unsigned 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
 163 CssmList &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
 175 CssmList &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
 200 CssmList &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
 219 void 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 //
 235 void 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
 251 void 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 //
 265 TypedList::TypedList(Allocator &alloc, CSSM_WORDID_TYPE type)
 266 {
 267         append(new(alloc) ListElement(type));
 268 }
 269
 270 TypedList::TypedList(Allocator &alloc, CSSM_WORDID_TYPE type, ListElement *elem1)
 271 {
 272         append(new(alloc) ListElement(type));
 273         append(elem1);
 274 }
 275
 276 TypedList::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
 283 TypedList::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
 291 TypedList::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 //
 304 bool TypedList::isProper() const
 305 {
 306         return first() && first()->type() == CSSM_LIST_ELEMENT_WORDID;
 307 }
 308
 309 void TypedList::checkProper(CSSM_RETURN error) const
 310 {
 311         if (!isProper())
 312                 CssmError::throwMe(error);
 313 }