Public Git Hosting - git/debian.git/blob

1 #include "cache.h"

2 #include "hash-lookup.h"

static uint32_t take2(const struct object_id *oid, size_t ofs)

5 {

        return ((oid->hash[ofs] << 8) | oid->hash[ofs   1]);

7 }

9 /*

10 * Conventional binary search loop looks like this:

11 *

12 * do {

13 * int mi = lo (hi - lo) / 2;

14 * int cmp = "entry pointed at by mi" minus "target";

15 * if (!cmp)

16 * return (mi is the wanted one)

17 * if (cmp > 0)

18 * hi = mi; "mi is larger than target"

19 * else

20 * lo = mi 1; "mi is smaller than target"

21 * } while (lo < hi);

22 *

23 * The invariants are:

24 *

25 * - When entering the loop, lo points at a slot that is never

26 * above the target (it could be at the target), hi points at a

27 * slot that is guaranteed to be above the target (it can never

28 * be at the target).

29 *

30 * - We find a point 'mi' between lo and hi (mi could be the same

31 * as lo, but never can be the same as hi), and check if it hits

32 * the target. There are three cases:

33 *

34 * - if it is a hit, we are happy.

35 *

36 * - if it is strictly higher than the target, we update hi with

37 * it.

38 *

39 * - if it is strictly lower than the target, we update lo to be

40 * one slot after it, because we allow lo to be at the target.

41 *

42 * When choosing 'mi', we do not have to take the "middle" but

43 * anywhere in between lo and hi, as long as lo <= mi < hi is

44 * satisfied. When we somehow know that the distance between the

45 * target and lo is much shorter than the target and hi, we could

46 * pick mi that is much closer to lo than the midway.

47 */

48 /*

49 * The table should contain "nr" elements.

50 * The oid of element i (between 0 and nr - 1) should be returned

51 * by "fn(i, table)".

52 */

int oid_pos(const struct object_id *oid, const void *table, size_t nr,

54 oid_access_fn fn)

55 {

56 size_t hi = nr;

57 size_t lo = 0;

58 size_t mi = 0;

60 if (!nr)

61 return -1;

        if (nr != 1) {

                size_t lov, hiv, miv, ofs;

                for (ofs = 0; ofs < the_hash_algo->rawsz - 2; ofs  = 2) {

                        lov = take2(fn(0, table), ofs);

                        hiv = take2(fn(nr - 1, table), ofs);

                        miv = take2(oid, ofs);

70 if (miv < lov)

71 return -1;

72 if (hiv < miv)

73 return index_pos_to_insert_pos(nr);

74 if (lov != hiv) {

75 /*

76 * At this point miv could be equal

77 * to hiv (but hash could still be higher);

78 * the invariant of (mi < hi) should be

79 * kept.

80 */

                                mi = (nr - 1) * (miv - lov) / (hiv - lov);

                                if (lo <= mi && mi < hi)

83 break;

84 BUG("assertion failed in binary search");

85 }

86 }

87 }

89 do {

90 int cmp;

                cmp = oidcmp(fn(mi, table), oid);

92 if (!cmp)

93 return mi;

                if (cmp > 0)

95 hi = mi;

96 else

97 lo = mi 1;

                mi = lo   (hi - lo) / 2;

        } while (lo < hi);

100 return index_pos_to_insert_pos(lo);

101 }

102

int bsearch_hash(const unsigned char *hash, const uint32_t *fanout_nbo,

                 const unsigned char *table, size_t stride, uint32_t *result)

105 {

106 uint32_t hi, lo;

107

        hi = ntohl(fanout_nbo[*hash]);

        lo = ((*hash == 0x0) ? 0 : ntohl(fanout_nbo[*hash - 1]));

110

111 while (lo < hi) {

                unsigned mi = lo   (hi - lo) / 2;

                int cmp = hashcmp(table   mi * stride, hash);

114

115 if (!cmp) {

116 if (result)

117 *result = mi;

118 return 1;

119 }

                if (cmp > 0)

121 hi = mi;

122 else

123 lo = mi 1;

124 }

125

126 if (result)

127 *result = lo;

128 return 0;

129 }