THIS IS A TEST INSTANCE ONLY! REPOSITORIES CAN BE DELETED AT ANY TIME!

Git Source Code Mirror - This is a publish-only repository and all pull requests are ignored. Please follow Documentation/SubmittingPatches procedure for any of your improvements.
git
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

110 lines
3.5KB

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