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