cdsa/cdsa_utilities/cssmlist.cpp

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