src/cx/linked_list.h

Sun, 03 Oct 2021 16:02:53 +0200

author
Mike Becker <universe@uap-core.de>
date
Sun, 03 Oct 2021 16:02:53 +0200
changeset 455
8168e16cd1e9
parent 453
bb144d08cd44
child 456
227c2eabbef8
permissions
-rw-r--r--

change test names

398
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
1 /*
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
3 *
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
4 * Copyright 2021 Mike Becker, Olaf Wintermann All rights reserved.
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
5 *
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
6 * Redistribution and use in source and binary forms, with or without
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
7 * modification, are permitted provided that the following conditions are met:
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
8 *
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
9 * 1. Redistributions of source code must retain the above copyright
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
10 * notice, this list of conditions and the following disclaimer.
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
11 *
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
12 * 2. Redistributions in binary form must reproduce the above copyright
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
13 * notice, this list of conditions and the following disclaimer in the
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
14 * documentation and/or other materials provided with the distribution.
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
15 *
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
17 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
19 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
20 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
21 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
22 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
23 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
26 * POSSIBILITY OF SUCH DAMAGE.
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
27 */
453
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 438
diff changeset
28 /**
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 438
diff changeset
29 * \file linked_list.h
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 438
diff changeset
30 * \brief Linked list implementation.
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 438
diff changeset
31 * \details Also provides several low-level functions for custom linked list implementations.
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 438
diff changeset
32 * \author Mike Becker
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 438
diff changeset
33 * \author Olaf Wintermann
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 438
diff changeset
34 * \version 3.0
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 438
diff changeset
35 * \copyright 2-Clause BSD License
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 438
diff changeset
36 */
398
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
37
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
38 #ifndef UCX_LINKED_LIST_H
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
39 #define UCX_LINKED_LIST_H
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
40
400
8cd274352419 changes off_t to ptrdiff_t
Mike Becker <universe@uap-core.de>
parents: 398
diff changeset
41 #include <stddef.h>
398
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
42 #include "list.h"
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
43
415
067aa769796a fix missing extern "C"
Mike Becker <universe@uap-core.de>
parents: 412
diff changeset
44 #ifdef __cplusplus
067aa769796a fix missing extern "C"
Mike Becker <universe@uap-core.de>
parents: 412
diff changeset
45 extern "C" {
067aa769796a fix missing extern "C"
Mike Becker <universe@uap-core.de>
parents: 412
diff changeset
46 #endif
067aa769796a fix missing extern "C"
Mike Becker <universe@uap-core.de>
parents: 412
diff changeset
47
453
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 438
diff changeset
48 CxList cxLinkedListCreate(CxAllocator allocator, CxListComparator comparator, size_t item_size);
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 438
diff changeset
49
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 438
diff changeset
50 void cxLinkedListDestroy(CxList list);
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 438
diff changeset
51
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 438
diff changeset
52 size_t cxLinkedListRecalculateSize(CxList list);
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 438
diff changeset
53
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 438
diff changeset
54
438
cd3069757010 add function cx_linked_list_at()
Mike Becker <universe@uap-core.de>
parents: 415
diff changeset
55 /**
cd3069757010 add function cx_linked_list_at()
Mike Becker <universe@uap-core.de>
parents: 415
diff changeset
56 * Finds the node at a certain index.
cd3069757010 add function cx_linked_list_at()
Mike Becker <universe@uap-core.de>
parents: 415
diff changeset
57 *
cd3069757010 add function cx_linked_list_at()
Mike Becker <universe@uap-core.de>
parents: 415
diff changeset
58 * This function can be used to start at an arbitrary position within the list.
cd3069757010 add function cx_linked_list_at()
Mike Becker <universe@uap-core.de>
parents: 415
diff changeset
59 * If the search index is large than the start index, \p loc_advance must denote
cd3069757010 add function cx_linked_list_at()
Mike Becker <universe@uap-core.de>
parents: 415
diff changeset
60 * the location of some sort of \c next pointer (i.e. a pointer to the next node).
cd3069757010 add function cx_linked_list_at()
Mike Becker <universe@uap-core.de>
parents: 415
diff changeset
61 * But it is also possible that the search index is smaller than the start index
cd3069757010 add function cx_linked_list_at()
Mike Becker <universe@uap-core.de>
parents: 415
diff changeset
62 * (e.g. in cases where traversing a list backwards is faster) in which case
cd3069757010 add function cx_linked_list_at()
Mike Becker <universe@uap-core.de>
parents: 415
diff changeset
63 * \p loc_advance must denote the location of some sort of \c prev pointer
cd3069757010 add function cx_linked_list_at()
Mike Becker <universe@uap-core.de>
parents: 415
diff changeset
64 * (i.e. a pointer to the previous node).
cd3069757010 add function cx_linked_list_at()
Mike Becker <universe@uap-core.de>
parents: 415
diff changeset
65 *
cd3069757010 add function cx_linked_list_at()
Mike Becker <universe@uap-core.de>
parents: 415
diff changeset
66 * @param start a pointer to the start node
cd3069757010 add function cx_linked_list_at()
Mike Becker <universe@uap-core.de>
parents: 415
diff changeset
67 * @param start_index the start index
cd3069757010 add function cx_linked_list_at()
Mike Becker <universe@uap-core.de>
parents: 415
diff changeset
68 * @param loc_advance the location of the pointer to advance
cd3069757010 add function cx_linked_list_at()
Mike Becker <universe@uap-core.de>
parents: 415
diff changeset
69 * @param index the search index
cd3069757010 add function cx_linked_list_at()
Mike Becker <universe@uap-core.de>
parents: 415
diff changeset
70 * @return the node found at the specified index
cd3069757010 add function cx_linked_list_at()
Mike Becker <universe@uap-core.de>
parents: 415
diff changeset
71 */
cd3069757010 add function cx_linked_list_at()
Mike Becker <universe@uap-core.de>
parents: 415
diff changeset
72 void *cx_linked_list_at(void *start, size_t start_index, ptrdiff_t loc_advance, size_t index);
cd3069757010 add function cx_linked_list_at()
Mike Becker <universe@uap-core.de>
parents: 415
diff changeset
73
453
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 438
diff changeset
74 /**
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 438
diff changeset
75 * Finds the last node in a linked list.
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 438
diff changeset
76 *
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 438
diff changeset
77 * If a pointer to \p end is provided, the result is just \c *end.
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 438
diff changeset
78 * Otherwise, this function starts with the pointer denoted by \c *begin and
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 438
diff changeset
79 * traverses the list along a next pointer whose location within the node struct is
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 438
diff changeset
80 * denoted by \p loc_next.
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 438
diff changeset
81 *
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 438
diff changeset
82 * If both \p begin and \p end are \c NULL, an empty list is assumed and this function returns \c NULL.
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 438
diff changeset
83 *
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 438
diff changeset
84 * @param begin a pointer to the begin node pointer (optional)
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 438
diff changeset
85 * @param end a pointer to the end node pointer (optional)
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 438
diff changeset
86 * @param loc_next the location of the \c next pointer (only required when \p end is \c NULL)
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 438
diff changeset
87 * @return a pointer to the last node or \c NULL if the list is empty
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 438
diff changeset
88 */
400
8cd274352419 changes off_t to ptrdiff_t
Mike Becker <universe@uap-core.de>
parents: 398
diff changeset
89 void *cx_linked_list_last(void **begin, void **end, ptrdiff_t loc_next);
398
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
90
453
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 438
diff changeset
91 /**
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 438
diff changeset
92 * Adds a new node to a linked list.
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 438
diff changeset
93 *
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 438
diff changeset
94 * \remark One of the pointers \p begin and \p end may be \c NULL, but not both.
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 438
diff changeset
95 *
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 438
diff changeset
96 * @param begin a pointer to the begin node pointer (if your list has one)
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 438
diff changeset
97 * @param end a pointer to the end node pointer (if your list has one)
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 438
diff changeset
98 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one)
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 438
diff changeset
99 * @param loc_next the location of a \c next pointer within your node struct (negative if your struct does not have one)
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 438
diff changeset
100 * @param new_node a pointer to the node that shall be appended
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 438
diff changeset
101 */
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 438
diff changeset
102 void cx_linked_list_add(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node);
406
9cbea761fbf7 adds cxLinkedListWrap and cxLinkedListRecalculateSize
Mike Becker <universe@uap-core.de>
parents: 402
diff changeset
103
415
067aa769796a fix missing extern "C"
Mike Becker <universe@uap-core.de>
parents: 412
diff changeset
104 #ifdef __cplusplus
067aa769796a fix missing extern "C"
Mike Becker <universe@uap-core.de>
parents: 412
diff changeset
105 } /* extern "C" */
067aa769796a fix missing extern "C"
Mike Becker <universe@uap-core.de>
parents: 412
diff changeset
106 #endif
067aa769796a fix missing extern "C"
Mike Becker <universe@uap-core.de>
parents: 412
diff changeset
107
398
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
108 #endif /* UCX_LINKED_LIST_H */

mercurial