]>
Commit | Line | Data |
---|---|---|
fb3920fd JK |
1 | #ifndef OID_ARRAY_H |
2 | #define OID_ARRAY_H | |
902bb364 | 3 | |
12c4b4ce JK |
4 | #include "hash.h" |
5 | ||
405c6b1f HW |
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 | * { | |
fe299ec5 | 24 | * struct oid_array hashes = OID_ARRAY_INIT; |
405c6b1f HW |
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 | */ | |
910650d2 | 52 | struct oid_array { |
ee3051bd | 53 | struct object_id *oid; |
600bee4e JK |
54 | size_t nr; |
55 | size_t alloc; | |
902bb364 JK |
56 | int sorted; |
57 | }; | |
58 | ||
9865b6e6 | 59 | #define OID_ARRAY_INIT { 0 } |
902bb364 | 60 | |
405c6b1f HW |
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 | */ | |
910650d2 | 65 | void oid_array_append(struct oid_array *array, const struct object_id *oid); |
405c6b1f HW |
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 | */ | |
910650d2 | 73 | int oid_array_lookup(struct oid_array *array, const struct object_id *oid); |
405c6b1f HW |
74 | |
75 | /** | |
76 | * Free all memory associated with the array and return it to the initial, | |
77 | * empty state. | |
78 | */ | |
910650d2 | 79 | void oid_array_clear(struct oid_array *array); |
902bb364 | 80 | |
1b7ba794 | 81 | typedef int (*for_each_oid_fn)(const struct object_id *oid, |
82 | void *data); | |
405c6b1f HW |
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 | */ | |
5cc044e0 ÆAB |
89 | int oid_array_for_each(struct oid_array *array, |
90 | for_each_oid_fn fn, | |
91 | void *data); | |
405c6b1f HW |
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 | */ | |
910650d2 | 98 | int oid_array_for_each_unique(struct oid_array *array, |
72486729 ÆAB |
99 | for_each_oid_fn fn, |
100 | void *data); | |
405c6b1f HW |
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 | */ | |
161b1cf3 SB |
107 | void oid_array_filter(struct oid_array *array, |
108 | for_each_oid_fn want, | |
109 | void *cbdata); | |
cff38a5e | 110 | |
d0482b44 JK |
111 | /** |
112 | * Sort the array in order of ascending object id. | |
113 | */ | |
114 | void oid_array_sort(struct oid_array *array); | |
115 | ||
12c4b4ce JK |
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 | */ | |
128 | static 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 | ||
fb3920fd | 137 | #endif /* OID_ARRAY_H */ |