]>
Commit | Line | Data |
---|---|---|
902bb364 JK |
1 | #ifndef SHA1_ARRAY_H |
2 | #define SHA1_ARRAY_H | |
3 | ||
405c6b1f HW |
4 | /** |
5 | * The API provides storage and manipulation of sets of object identifiers. | |
6 | * The emphasis is on storage and processing efficiency, making them suitable | |
7 | * for large lists. Note that the ordering of items is not preserved over some | |
8 | * operations. | |
9 | * | |
10 | * Examples | |
11 | * -------- | |
12 | * ----------------------------------------- | |
13 | * int print_callback(const struct object_id *oid, | |
14 | * void *data) | |
15 | * { | |
16 | * printf("%s\n", oid_to_hex(oid)); | |
17 | * return 0; // always continue | |
18 | * } | |
19 | * | |
20 | * void some_func(void) | |
21 | * { | |
fe299ec5 | 22 | * struct oid_array hashes = OID_ARRAY_INIT; |
405c6b1f HW |
23 | * struct object_id oid; |
24 | * | |
25 | * // Read objects into our set | |
26 | * while (read_object_from_stdin(oid.hash)) | |
27 | * oid_array_append(&hashes, &oid); | |
28 | * | |
29 | * // Check if some objects are in our set | |
30 | * while (read_object_from_stdin(oid.hash)) { | |
31 | * if (oid_array_lookup(&hashes, &oid) >= 0) | |
32 | * printf("it's in there!\n"); | |
33 | * | |
34 | * // Print the unique set of objects. We could also have | |
35 | * // avoided adding duplicate objects in the first place, | |
36 | * // but we would end up re-sorting the array repeatedly. | |
37 | * // Instead, this will sort once and then skip duplicates | |
38 | * // in linear time. | |
39 | * | |
40 | * oid_array_for_each_unique(&hashes, print_callback, NULL); | |
41 | * } | |
42 | */ | |
43 | ||
44 | /** | |
45 | * A single array of object IDs. This should be initialized by assignment from | |
46 | * `OID_ARRAY_INIT`. The `oid` member contains the actual data. The `nr` member | |
47 | * contains the number of items in the set. The `alloc` and `sorted` members | |
48 | * are used internally, and should not be needed by API callers. | |
49 | */ | |
910650d2 | 50 | struct oid_array { |
ee3051bd | 51 | struct object_id *oid; |
600bee4e JK |
52 | size_t nr; |
53 | size_t alloc; | |
902bb364 JK |
54 | int sorted; |
55 | }; | |
56 | ||
910650d2 | 57 | #define OID_ARRAY_INIT { NULL, 0, 0, 0 } |
902bb364 | 58 | |
405c6b1f HW |
59 | /** |
60 | * Add an item to the set. The object ID will be placed at the end of the array | |
61 | * (but note that some operations below may lose this ordering). | |
62 | */ | |
910650d2 | 63 | void oid_array_append(struct oid_array *array, const struct object_id *oid); |
405c6b1f HW |
64 | |
65 | /** | |
66 | * Perform a binary search of the array for a specific object ID. If found, | |
67 | * returns the offset (in number of elements) of the object ID. If not found, | |
68 | * returns a negative integer. If the array is not sorted, this function has | |
69 | * the side effect of sorting it. | |
70 | */ | |
910650d2 | 71 | int oid_array_lookup(struct oid_array *array, const struct object_id *oid); |
405c6b1f HW |
72 | |
73 | /** | |
74 | * Free all memory associated with the array and return it to the initial, | |
75 | * empty state. | |
76 | */ | |
910650d2 | 77 | void oid_array_clear(struct oid_array *array); |
902bb364 | 78 | |
1b7ba794 | 79 | typedef int (*for_each_oid_fn)(const struct object_id *oid, |
80 | void *data); | |
405c6b1f HW |
81 | /** |
82 | * Iterate over each element of the list, executing the callback function for | |
83 | * each one. Does not sort the list, so any custom hash order is retained. | |
84 | * If the callback returns a non-zero value, the iteration ends immediately | |
85 | * and the callback's return is propagated; otherwise, 0 is returned. | |
86 | */ | |
5cc044e0 ÆAB |
87 | int oid_array_for_each(struct oid_array *array, |
88 | for_each_oid_fn fn, | |
89 | void *data); | |
405c6b1f HW |
90 | |
91 | /** | |
92 | * Iterate over each unique element of the list in sorted order, but otherwise | |
93 | * behave like `oid_array_for_each`. If the array is not sorted, this function | |
94 | * has the side effect of sorting it. | |
95 | */ | |
910650d2 | 96 | int oid_array_for_each_unique(struct oid_array *array, |
72486729 ÆAB |
97 | for_each_oid_fn fn, |
98 | void *data); | |
405c6b1f HW |
99 | |
100 | /** | |
101 | * Apply the callback function `want` to each entry in the array, retaining | |
102 | * only the entries for which the function returns true. Preserve the order | |
103 | * of the entries that are retained. | |
104 | */ | |
161b1cf3 SB |
105 | void oid_array_filter(struct oid_array *array, |
106 | for_each_oid_fn want, | |
107 | void *cbdata); | |
cff38a5e | 108 | |
902bb364 | 109 | #endif /* SHA1_ARRAY_H */ |