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