/src/nss/lib/base/list.c

Source
/* This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */

/*
 * list.c
 *
 * This contains the implementation of NSS's thread-safe linked list.
 */

#ifndef BASE_H
#include "base.h"
#endif /* BASE_H */

struct nssListElementStr {
    PRCList link;
    void *data;
};

typedef struct nssListElementStr nssListElement;

struct nssListStr {
    NSSArena *arena;
    PRLock *lock;
    nssListElement *head;
    PRUint32 count;
    nssListCompareFunc compareFunc;
    nssListSortFunc sortFunc;
    PRBool i_alloced_arena;
};

struct nssListIteratorStr {
    PRLock *lock;
    nssList *list;
    nssListElement *current;
};

#define NSSLIST_LOCK_IF(list) \
    if ((list)->lock)         \
    PR_Lock((list)->lock)

#define NSSLIST_UNLOCK_IF(list) \
    if ((list)->lock)           \
    PR_Unlock((list)->lock)

static PRBool
pointer_compare(void *a, void *b)
{
    return (PRBool)(a == b);
}

static nssListElement *
nsslist_get_matching_element(nssList *list, void *data)
{
    nssListElement *node;
    node = list->head;
    if (!node) {
        return NULL;
    }
    while (node) {
        /* using a callback slows things down when it's just compare ... */
        if (list->compareFunc(node->data, data)) {
            break;
        }
        if (&node->link == PR_LIST_TAIL(&list->head->link)) {
            node = NULL;
            break;
        }
        node = (nssListElement *)PR_NEXT_LINK(&node->link);
    }
    return node;
}

NSS_IMPLEMENT nssList *
nssList_Create(NSSArena *arenaOpt, PRBool threadSafe)
{
    NSSArena *arena;
    nssList *list;
    PRBool i_alloced;
    if (arenaOpt) {
        arena = arenaOpt;
        i_alloced = PR_FALSE;
    } else {
        arena = nssArena_Create();
        i_alloced = PR_TRUE;
    }
    if (!arena) {
        return (nssList *)NULL;
    }
    list = nss_ZNEW(arena, nssList);
    if (!list) {
        if (!arenaOpt) {
            NSSArena_Destroy(arena);
        }
        return (nssList *)NULL;
    }
    if (threadSafe) {
        list->lock = PR_NewLock();
        if (!list->lock) {
            if (arenaOpt) {
                nss_ZFreeIf(list);
            } else {
                NSSArena_Destroy(arena);
            }
            return (nssList *)NULL;
        }
    }
    list->arena = arena;
    list->i_alloced_arena = i_alloced;
    list->compareFunc = pointer_compare;
    return list;
}

NSS_IMPLEMENT PRStatus
nssList_Destroy(nssList *list)
{
    if (!list) {
        return PR_SUCCESS;
    }
    if (!list->i_alloced_arena) {
        nssList_Clear(list, NULL);
    }
    if (list->lock) {
        (void)PR_DestroyLock(list->lock);
    }
    if (list->i_alloced_arena) {
        NSSArena_Destroy(list->arena);
        list = NULL;
    }
    nss_ZFreeIf(list);
    return PR_SUCCESS;
}

NSS_IMPLEMENT void
nssList_SetSortFunction(nssList *list, nssListSortFunc sortFunc)
{
    /* XXX if list already has elements, sort them */
    list->sortFunc = sortFunc;
}

NSS_IMPLEMENT void
nssList_Clear(nssList *list, nssListElementDestructorFunc destructor)
{
    PRCList *link;
    nssListElement *node, *tmp;
    if (!list) {
        return;
    }
    NSSLIST_LOCK_IF(list);
    node = list->head;
    list->head = NULL;
    while (node && list->count > 0) {
        if (destructor)
            (*destructor)(node->data);
        link = &node->link;
        tmp = (nssListElement *)PR_NEXT_LINK(link);
        PR_REMOVE_LINK(link);
        nss_ZFreeIf(node);
        node = tmp;
        --list->count;
    }
    NSSLIST_UNLOCK_IF(list);
}

static PRStatus
nsslist_add_element(nssList *list, void *data)
{
    nssListElement *node = nss_ZNEW(list->arena, nssListElement);
    if (!node) {
        return PR_FAILURE;
    }
    PR_INIT_CLIST(&node->link);
    node->data = data;
    if (list->head) {
        if (list->sortFunc) {
            PRCList *link;
            nssListElement *currNode;
            currNode = list->head;
            /* insert in ordered list */
            while (currNode) {
                link = &currNode->link;
                if (list->sortFunc(data, currNode->data) <= 0) {
                    /* new element goes before current node */
                    PR_INSERT_BEFORE(&node->link, link);
                    /* reset head if this is first */
                    if (currNode == list->head)
                        list->head = node;
                    break;
                }
                if (link == PR_LIST_TAIL(&list->head->link)) {
                    /* reached end of list, append */
                    PR_INSERT_AFTER(&node->link, link);
                    break;
                }
                currNode = (nssListElement *)PR_NEXT_LINK(&currNode->link);
            }
        } else {
            /* not sorting */
            PR_APPEND_LINK(&node->link, &list->head->link);
        }
    } else {
        list->head = node;
    }
    ++list->count;
    return PR_SUCCESS;
}

NSS_IMPLEMENT PRStatus
nssList_Add(nssList *list, void *data)
{
    NSSLIST_LOCK_IF(list);
    (void)nsslist_add_element(list, data);
    NSSLIST_UNLOCK_IF(list);
    return PR_SUCCESS;
}

NSS_IMPLEMENT PRStatus
nssList_AddUnique(nssList *list, void *data)
{
    PRStatus nssrv;
    nssListElement *node;
    NSSLIST_LOCK_IF(list);
    node = nsslist_get_matching_element(list, data);
    if (node) {
        /* already in, finish */
        NSSLIST_UNLOCK_IF(list);
        return PR_SUCCESS;
    }
    nssrv = nsslist_add_element(list, data);
    NSSLIST_UNLOCK_IF(list);
    return nssrv;
}

NSS_IMPLEMENT PRStatus
nssList_Remove(nssList *list, void *data)
{
    nssListElement *node;
    NSSLIST_LOCK_IF(list);
    node = nsslist_get_matching_element(list, data);
    if (node) {
        if (node == list->head) {
            list->head = (nssListElement *)PR_NEXT_LINK(&node->link);
        }
        PR_REMOVE_LINK(&node->link);
        nss_ZFreeIf(node);
        if (--list->count == 0) {
            list->head = NULL;
        }
    }
    NSSLIST_UNLOCK_IF(list);
    return PR_SUCCESS;
}

NSS_IMPLEMENT PRUint32
nssList_Count(nssList *list)
{
    return list->count;
}

NSS_IMPLEMENT PRStatus
nssList_GetArray(nssList *list, void **rvArray, PRUint32 maxElements)
{
    nssListElement *node;
    PRUint32 i = 0;
    PR_ASSERT(maxElements > 0);
    node = list->head;
    if (!node) {
        return PR_SUCCESS;
    }
    NSSLIST_LOCK_IF(list);
    while (node) {
        rvArray[i++] = node->data;
        if (i == maxElements)
            break;
        node = (nssListElement *)PR_NEXT_LINK(&node->link);
        if (node == list->head) {
            break;
        }
    }
    NSSLIST_UNLOCK_IF(list);
    return PR_SUCCESS;
}

NSS_IMPLEMENT nssList *
nssList_Clone(nssList *list)
{
    nssList *rvList;
    nssListElement *node;
    rvList = nssList_Create(NULL, (list->lock != NULL));
    if (!rvList) {
        return NULL;
    }
    NSSLIST_LOCK_IF(list);
    if (list->count > 0) {
        node = list->head;
        while (PR_TRUE) {
            nssList_Add(rvList, node->data);
            node = (nssListElement *)PR_NEXT_LINK(&node->link);
            if (node == list->head) {
                break;
            }
        }
    }
    NSSLIST_UNLOCK_IF(list);
    return rvList;
}

NSS_IMPLEMENT nssListIterator *
nssList_CreateIterator(nssList *list)
{
    nssListIterator *rvIterator;
    rvIterator = nss_ZNEW(NULL, nssListIterator);
    if (!rvIterator) {
        return NULL;
    }
    rvIterator->list = nssList_Clone(list);
    if (!rvIterator->list) {
        nss_ZFreeIf(rvIterator);
        return NULL;
    }
    rvIterator->current = rvIterator->list->head;
    if (list->lock) {
        rvIterator->lock = PR_NewLock();
        if (!rvIterator->lock) {
            nssList_Destroy(rvIterator->list);
            nss_ZFreeIf(rvIterator);
            rvIterator = NULL;
        }
    }
    return rvIterator;
}

NSS_IMPLEMENT void
nssListIterator_Destroy(nssListIterator *iter)
{
    if (iter->lock) {
        (void)PR_DestroyLock(iter->lock);
    }
    if (iter->list) {
        nssList_Destroy(iter->list);
    }
    nss_ZFreeIf(iter);
}

NSS_IMPLEMENT void *
nssListIterator_Start(nssListIterator *iter)
{
    NSSLIST_LOCK_IF(iter);
    if (iter->list->count == 0) {
        return NULL;
    }
    iter->current = iter->list->head;
    return iter->current->data;
}

NSS_IMPLEMENT void *
nssListIterator_Next(nssListIterator *iter)
{
    nssListElement *node;
    PRCList *link;
    if (iter->list->count == 1 || iter->current == NULL) {
        /* Reached the end of the list.  Don't change the state, force to
         * user to call nssList_Finish to clean up.
         */
        return NULL;
    }
    node = (nssListElement *)PR_NEXT_LINK(&iter->current->link);
    link = &node->link;
    if (link == PR_LIST_TAIL(&iter->list->head->link)) {
        /* Signal the end of the list. */
        iter->current = NULL;
        return node->data;
    }
    iter->current = node;
    return node->data;
}

NSS_IMPLEMENT PRStatus
nssListIterator_Finish(nssListIterator *iter)
{
    iter->current = iter->list->head;
    return (iter->lock) ? PR_Unlock(iter->lock) : PR_SUCCESS;
}

Coverage Report

Created: 2026-10-13 06:23

Line	Count	Source
1		/* This Source Code Form is subject to the terms of the Mozilla Public
2		* License, v. 2.0. If a copy of the MPL was not distributed with this
3		* file, You can obtain one at http://mozilla.org/MPL/2.0/. */
4
5		/*
6		* list.c
7		*
8		* This contains the implementation of NSS's thread-safe linked list.
9		*/
10
11		#ifndef BASE_H
12		#include "base.h"
13		#endif /* BASE_H */
14
15		struct nssListElementStr {
16		PRCList link;
17		void *data;
18		};
19
20		typedef struct nssListElementStr nssListElement;
21
22		struct nssListStr {
23		NSSArena *arena;
24		PRLock *lock;
25		nssListElement *head;
26		PRUint32 count;
27		nssListCompareFunc compareFunc;
28		nssListSortFunc sortFunc;
29		PRBool i_alloced_arena;
30		};
31
32		struct nssListIteratorStr {
33		PRLock *lock;
34		nssList *list;
35		nssListElement *current;
36		};
37
38		#define NSSLIST_LOCK_IF(list) \
39	567k	if ((list)->lock) \
40	567k	PR_Lock((list)->lock)
41
42		#define NSSLIST_UNLOCK_IF(list) \
43	553k	if ((list)->lock) \
44	553k	PR_Unlock((list)->lock)
45
46		static PRBool
47		pointer_compare(void a, void b)
48	88.6k	{
49	88.6k	return (PRBool)(a == b);
50	88.6k	}
51
52		static nssListElement *
53		nsslist_get_matching_element(nssList list, void data)
54	84.6k	{
55	84.6k	nssListElement *node;
56	84.6k	node = list->head;
57	84.6k	if (!node) {
58	6	return NULL;
59	6	}
60	88.6k	while (node) {
61		/* using a callback slows things down when it's just compare ... */
62	88.6k	if (list->compareFunc(node->data, data)) {
63	82.8k	break;
64	82.8k	}
65	5.84k	if (&node->link == PR_LIST_TAIL(&list->head->link)) {
66	1.82k	node = NULL;
67	1.82k	break;
68	1.82k	}
69	4.02k	node = (nssListElement *)PR_NEXT_LINK(&node->link);
70	4.02k	}
71	84.6k	return node;
72	84.6k	}
73
74		NSS_IMPLEMENT nssList *
75		nssList_Create(NSSArena *arenaOpt, PRBool threadSafe)
76	109k	{
77	109k	NSSArena *arena;
78	109k	nssList *list;
79	109k	PRBool i_alloced;
80	109k	if (arenaOpt) {
81	24	arena = arenaOpt;
82	24	i_alloced = PR_FALSE;
83	109k	} else {
84	109k	arena = nssArena_Create();
85	109k	i_alloced = PR_TRUE;
86	109k	}
87	109k	if (!arena) {
88	0	return (nssList *)NULL;
89	0	}
90	109k	list = nss_ZNEW(arena, nssList);
91	109k	if (!list) {
92	0	if (!arenaOpt) {
93	0	NSSArena_Destroy(arena);
94	0	}
95	0	return (nssList *)NULL;
96	0	}
97	109k	if (threadSafe) {
98	38	list->lock = PR_NewLock();
99	38	if (!list->lock) {
100	0	if (arenaOpt) {
101	0	nss_ZFreeIf(list);
102	0	} else {
103	0	NSSArena_Destroy(arena);
104	0	}
105	0	return (nssList *)NULL;
106	0	}
107	38	}
108	109k	list->arena = arena;
109	109k	list->i_alloced_arena = i_alloced;
110	109k	list->compareFunc = pointer_compare;
111	109k	return list;
112	109k	}
113
114		NSS_IMPLEMENT PRStatus
115		nssList_Destroy(nssList *list)
116	109k	{
117	109k	if (!list) {
118	0	return PR_SUCCESS;
119	0	}
120	109k	if (!list->i_alloced_arena) {
121	22	nssList_Clear(list, NULL);
122	22	}
123	109k	if (list->lock) {
124	34	(void)PR_DestroyLock(list->lock);
125	34	}
126	109k	if (list->i_alloced_arena) {
127	109k	NSSArena_Destroy(list->arena);
128	109k	list = NULL;
129	109k	}
130	109k	nss_ZFreeIf(list);
131	109k	return PR_SUCCESS;
132	109k	}
133
134		NSS_IMPLEMENT void
135		nssList_SetSortFunction(nssList *list, nssListSortFunc sortFunc)
136	81.0k	{
137		/* XXX if list already has elements, sort them */
138	81.0k	list->sortFunc = sortFunc;
139	81.0k	}
140
141		NSS_IMPLEMENT void
142		nssList_Clear(nssList *list, nssListElementDestructorFunc destructor)
143	38	{
144	38	PRCList *link;
145	38	nssListElement node, tmp;
146	38	if (!list) {
147	0	return;
148	0	}
149	38	NSSLIST_LOCK_IF(list);
150	38	node = list->head;
151	38	list->head = NULL;
152	70	while (node && list->count > 0) {
153	32	if (destructor)
154	32	(*destructor)(node->data);
155	32	link = &node->link;
156	32	tmp = (nssListElement *)PR_NEXT_LINK(link);
157	32	PR_REMOVE_LINK(link);
158	32	nss_ZFreeIf(node);
159	32	node = tmp;
160	32	--list->count;
161	32	}
162	38	NSSLIST_UNLOCK_IF(list);
163	38	}
164
165		static PRStatus
166		nsslist_add_element(nssList list, void data)
167	96.2k	{
168	96.2k	nssListElement *node = nss_ZNEW(list->arena, nssListElement);
169	96.2k	if (!node) {
170	0	return PR_FAILURE;
171	0	}
172	96.2k	PR_INIT_CLIST(&node->link);
173	96.2k	node->data = data;
174	96.2k	if (list->head) {
175	1.86k	if (list->sortFunc) {
176	1.82k	PRCList *link;
177	1.82k	nssListElement *currNode;
178	1.82k	currNode = list->head;
179		/* insert in ordered list */
180	3.32k	while (currNode) {
181	3.32k	link = &currNode->link;
182	3.32k	if (list->sortFunc(data, currNode->data) <= 0) {
183		/* new element goes before current node */
184	540	PR_INSERT_BEFORE(&node->link, link);
185		/* reset head if this is first */
186	540	if (currNode == list->head)
187	438	list->head = node;
188	540	break;
189	540	}
190	2.78k	if (link == PR_LIST_TAIL(&list->head->link)) {
191		/* reached end of list, append */
192	1.28k	PR_INSERT_AFTER(&node->link, link);
193	1.28k	break;
194	1.28k	}
195	1.49k	currNode = (nssListElement *)PR_NEXT_LINK(&currNode->link);
196	1.49k	}
197	1.82k	} else {
198		/* not sorting */
199	36	PR_APPEND_LINK(&node->link, &list->head->link);
200	36	}
201	94.4k	} else {
202	94.4k	list->head = node;
203	94.4k	}
204	96.2k	++list->count;
205	96.2k	return PR_SUCCESS;
206	96.2k	}
207
208		NSS_IMPLEMENT PRStatus
209		nssList_Add(nssList list, void data)
210	94.4k	{
211	94.4k	NSSLIST_LOCK_IF(list);
212	94.4k	(void)nsslist_add_element(list, data);
213	94.4k	NSSLIST_UNLOCK_IF(list);
214	94.4k	return PR_SUCCESS;
215	94.4k	}
216
217		NSS_IMPLEMENT PRStatus
218		nssList_AddUnique(nssList list, void data)
219	1.83k	{
220	1.83k	PRStatus nssrv;
221	1.83k	nssListElement *node;
222	1.83k	NSSLIST_LOCK_IF(list);
223	1.83k	node = nsslist_get_matching_element(list, data);
224	1.83k	if (node) {
225		/* already in, finish */
226	0	NSSLIST_UNLOCK_IF(list);
227	0	return PR_SUCCESS;
228	0	}
229	1.83k	nssrv = nsslist_add_element(list, data);
230	1.83k	NSSLIST_UNLOCK_IF(list);
231	1.83k	return nssrv;
232	1.83k	}
233
234		NSS_IMPLEMENT PRStatus
235		nssList_Remove(nssList list, void data)
236	82.8k	{
237	82.8k	nssListElement *node;
238	82.8k	NSSLIST_LOCK_IF(list);
239	82.8k	node = nsslist_get_matching_element(list, data);
240	82.8k	if (node) {
241	82.8k	if (node == list->head) {
242	81.6k	list->head = (nssListElement *)PR_NEXT_LINK(&node->link);
243	81.6k	}
244	82.8k	PR_REMOVE_LINK(&node->link);
245	82.8k	nss_ZFreeIf(node);
246	82.8k	if (--list->count == 0) {
247	81.0k	list->head = NULL;
248	81.0k	}
249	82.8k	}
250	82.8k	NSSLIST_UNLOCK_IF(list);
251	82.8k	return PR_SUCCESS;
252	82.8k	}
253
254		NSS_IMPLEMENT PRUint32
255		nssList_Count(nssList *list)
256	457k	{
257	457k	return list->count;
258	457k	}
259
260		NSS_IMPLEMENT PRStatus
261		nssList_GetArray(nssList list, void *rvArray, PRUint32 maxElements)
262	361k	{
263	361k	nssListElement *node;
264	361k	PRUint32 i = 0;
265	361k	PR_ASSERT(maxElements > 0);
266	361k	node = list->head;
267	361k	if (!node) {
268	0	return PR_SUCCESS;
269	0	}
270	361k	NSSLIST_LOCK_IF(list);
271	707k	while (node) {
272	707k	rvArray[i++] = node->data;
273	707k	if (i == maxElements)
274	361k	break;
275	346k	node = (nssListElement *)PR_NEXT_LINK(&node->link);
276	346k	if (node == list->head) {
277	0	break;
278	0	}
279	346k	}
280	361k	NSSLIST_UNLOCK_IF(list);
281	361k	return PR_SUCCESS;
282	361k	}
283
284		NSS_IMPLEMENT nssList *
285		nssList_Clone(nssList *list)
286	13.3k	{
287	13.3k	nssList *rvList;
288	13.3k	nssListElement *node;
289	13.3k	rvList = nssList_Create(NULL, (list->lock != NULL));
290	13.3k	if (!rvList) {
291	0	return NULL;
292	0	}
293	13.3k	NSSLIST_LOCK_IF(list);
294	13.3k	if (list->count > 0) {
295	13.3k	node = list->head;
296	13.4k	while (PR_TRUE) {
297	13.4k	nssList_Add(rvList, node->data);
298	13.4k	node = (nssListElement *)PR_NEXT_LINK(&node->link);
299	13.4k	if (node == list->head) {
300	13.3k	break;
301	13.3k	}
302	13.4k	}
303	13.3k	}
304	13.3k	NSSLIST_UNLOCK_IF(list);
305	13.3k	return rvList;
306	13.3k	}
307
308		NSS_IMPLEMENT nssListIterator *
309		nssList_CreateIterator(nssList *list)
310	13.3k	{
311	13.3k	nssListIterator *rvIterator;
312	13.3k	rvIterator = nss_ZNEW(NULL, nssListIterator);
313	13.3k	if (!rvIterator) {
314	0	return NULL;
315	0	}
316	13.3k	rvIterator->list = nssList_Clone(list);
317	13.3k	if (!rvIterator->list) {
318	0	nss_ZFreeIf(rvIterator);
319	0	return NULL;
320	0	}
321	13.3k	rvIterator->current = rvIterator->list->head;
322	13.3k	if (list->lock) {
323	18	rvIterator->lock = PR_NewLock();
324	18	if (!rvIterator->lock) {
325	0	nssList_Destroy(rvIterator->list);
326	0	nss_ZFreeIf(rvIterator);
327	0	rvIterator = NULL;
328	0	}
329	18	}
330	13.3k	return rvIterator;
331	13.3k	}
332
333		NSS_IMPLEMENT void
334		nssListIterator_Destroy(nssListIterator *iter)
335	13.3k	{
336	13.3k	if (iter->lock) {
337	16	(void)PR_DestroyLock(iter->lock);
338	16	}
339	13.3k	if (iter->list) {
340	13.3k	nssList_Destroy(iter->list);
341	13.3k	}
342	13.3k	nss_ZFreeIf(iter);
343	13.3k	}
344
345		NSS_IMPLEMENT void *
346		nssListIterator_Start(nssListIterator *iter)
347	13.3k	{
348	13.3k	NSSLIST_LOCK_IF(iter);
349	13.3k	if (iter->list->count == 0) {
350	0	return NULL;
351	0	}
352	13.3k	iter->current = iter->list->head;
353	13.3k	return iter->current->data;
354	13.3k	}
355
356		NSS_IMPLEMENT void *
357		nssListIterator_Next(nssListIterator *iter)
358	13.3k	{
359	13.3k	nssListElement *node;
360	13.3k	PRCList *link;
361	13.3k	if (iter->list->count == 1 \|\| iter->current == NULL) {
362		/* Reached the end of the list. Don't change the state, force to
363		* user to call nssList_Finish to clean up.
364		*/
365	13.3k	return NULL;
366	13.3k	}
367	0	node = (nssListElement *)PR_NEXT_LINK(&iter->current->link);
368	0	link = &node->link;
369	0	if (link == PR_LIST_TAIL(&iter->list->head->link)) {
370		/* Signal the end of the list. */
371	0	iter->current = NULL;
372	0	return node->data;
373	0	}
374	0	iter->current = node;
375	0	return node->data;
376	0	}
377
378		NSS_IMPLEMENT PRStatus
379		nssListIterator_Finish(nssListIterator *iter)
380	13.3k	{
381	13.3k	iter->current = iter->list->head;
382	13.3k	return (iter->lock) ? PR_Unlock(iter->lock) : PR_SUCCESS;
383	13.3k	}