1sha1-array API 2============== 3 4The sha1-array API provides storage and manipulation of sets of SHA1 5identifiers. The emphasis is on storage and processing efficiency, 6making them suitable for large lists. Note that the ordering of items is 7not preserved over some operations. 8 9Data Structures 10--------------- 11 12`struct sha1_array`:: 13 14 A single array of SHA1 hashes. This should be initialized by 15 assignment from `SHA1_ARRAY_INIT`. The `sha1` member contains 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 20Functions 21--------- 22 23`sha1_array_append`:: 24 Add an item to the set. The sha1 will be placed at the end of 25 the array (but note that some operations below may lose this 26 ordering). 27 28`sha1_array_sort`:: 29 Sort the elements in the array. 30 31`sha1_array_lookup`:: 32 Perform a binary search of the array for a specific sha1. 33 If found, returns the offset (in number of elements) of the 34 sha1. If not found, returns a negative integer. If the array is 35 not sorted, this function has the side effect of sorting it. 36 37`sha1_array_clear`:: 38 Free all memory associated with the array and return it to the 39 initial, empty state. 40 41`sha1_array_for_each_unique`:: 42 Efficiently iterate over each unique element of the list, 43 executing the callback function for each one. If the array is 44 not sorted, this function has the side effect of sorting it. 45 46Examples 47-------- 48 49----------------------------------------- 50void print_callback(const unsigned char sha1[20], 51 void *data) 52{ 53 printf("%s\n", sha1_to_hex(sha1)); 54} 55 56void some_func(void) 57{ 58 struct sha1_array hashes = SHA1_ARRAY_INIT; 59 unsigned char sha1[20]; 60 61 /* Read objects into our set */ 62 while (read_object_from_stdin(sha1)) 63 sha1_array_append(&hashes, sha1); 64 65 /* Check if some objects are in our set */ 66 while (read_object_from_stdin(sha1)) { 67 if (sha1_array_lookup(&hashes, sha1) >= 0) 68 printf("it's in there!\n"); 69 70 /* 71 * Print the unique set of objects. We could also have 72 * avoided adding duplicate objects in the first place, 73 * but we would end up re-sorting the array repeatedly. 74 * Instead, this will sort once and then skip duplicates 75 * in linear time. 76 */ 77 sha1_array_for_each_unique(&hashes, print_callback, NULL); 78} 79-----------------------------------------