freshlybakedca.ke
Git fork
1#ifndef OID_ARRAY_H
2#define OID_ARRAY_H
3
4#include "hash.h"
5
6/**
7 * The API provides storage and manipulation of sets of object identifiers.
8 * The emphasis is on storage and processing efficiency, making them suitable
9 * for large lists. Note that the ordering of items is not preserved over some
10 * operations.
11 *
12 * Examples
13 * --------
14 * -----------------------------------------
15 * int print_callback(const struct object_id *oid,
16 * void *data)
17 * {
18 * printf("%s\n", oid_to_hex(oid));
19 * return 0; // always continue
20 * }
21 *
22 * void some_func(void)
23 * {
24 * struct oid_array hashes = OID_ARRAY_INIT;
25 * struct object_id oid;
26 *
27 * // Read objects into our set
28 * while (read_object_from_stdin(oid.hash))
29 * oid_array_append(&hashes, &oid);
30 *
31 * // Check if some objects are in our set
32 * while (read_object_from_stdin(oid.hash)) {
33 * if (oid_array_lookup(&hashes, &oid) >= 0)
34 * printf("it's in there!\n");
35 *
36 * // Print the unique set of objects. We could also have
37 * // avoided adding duplicate objects in the first place,
38 * // but we would end up re-sorting the array repeatedly.
39 * // Instead, this will sort once and then skip duplicates
40 * // in linear time.
41 *
42 * oid_array_for_each_unique(&hashes, print_callback, NULL);
43 * }
44 */
45
46/**
47 * A single array of object IDs. This should be initialized by assignment from
48 * `OID_ARRAY_INIT`. The `oid` member contains the actual data. The `nr` member
49 * contains the number of items in the set. The `alloc` and `sorted` members
50 * are used internally, and should not be needed by API callers.
51 */
52struct oid_array {
53 struct object_id *oid;
54 size_t nr;
55 size_t alloc;
56 int sorted;
57};
58
59#define OID_ARRAY_INIT { 0 }
60
61/**
62 * Add an item to the set. The object ID will be placed at the end of the array
63 * (but note that some operations below may lose this ordering).
64 */
65void oid_array_append(struct oid_array *array, const struct object_id *oid);
66
67/**
68 * Perform a binary search of the array for a specific object ID. If found,
69 * returns the offset (in number of elements) of the object ID. If not found,
70 * returns a negative integer. If the array is not sorted, this function has
71 * the side effect of sorting it.
72 */
73int oid_array_lookup(struct oid_array *array, const struct object_id *oid);
74
75/**
76 * Free all memory associated with the array and return it to the initial,
77 * empty state.
78 */
79void oid_array_clear(struct oid_array *array);
80
81typedef int (*for_each_oid_fn)(const struct object_id *oid,
82 void *data);
83/**
84 * Iterate over each element of the list, executing the callback function for
85 * each one. Does not sort the list, so any custom hash order is retained.
86 * If the callback returns a non-zero value, the iteration ends immediately
87 * and the callback's return is propagated; otherwise, 0 is returned.
88 */
89int oid_array_for_each(struct oid_array *array,
90 for_each_oid_fn fn,
91 void *data);
92
93/**
94 * Iterate over each unique element of the list in sorted order, but otherwise
95 * behave like `oid_array_for_each`. If the array is not sorted, this function
96 * has the side effect of sorting it.
97 */
98int oid_array_for_each_unique(struct oid_array *array,
99 for_each_oid_fn fn,
100 void *data);
101
102/**
103 * Apply the callback function `want` to each entry in the array, retaining
104 * only the entries for which the function returns true. Preserve the order
105 * of the entries that are retained.
106 */
107void oid_array_filter(struct oid_array *array,
108 for_each_oid_fn want,
109 void *cbdata);
110
111/**
112 * Sort the array in order of ascending object id.
113 */
114void oid_array_sort(struct oid_array *array);
115
116/**
117 * Find the next unique oid in the array after position "cur".
118 * The array must be sorted for this to work. You can iterate
119 * over unique elements like this:
120 *
121 * size_t i;
122 * oid_array_sort(array);
123 * for (i = 0; i < array->nr; i = oid_array_next_unique(array, i))
124 * printf("%s", oid_to_hex(array->oids[i]);
125 *
126 * Non-unique iteration can just increment with "i++" to visit each element.
127 */
128static inline size_t oid_array_next_unique(struct oid_array *array, size_t cur)
129{
130 do {
131 cur++;
132 } while (cur < array->nr &&
133 oideq(array->oid + cur, array->oid + cur - 1));
134 return cur;
135}
136
137#endif /* OID_ARRAY_H */