git
/
pseudo-merge.c
765 строк · 19.7 Кб
1#define USE_THE_REPOSITORY_VARIABLE2{26double result = 1;27while (1) {28if (exp % 2)29result *= base;30exp >>= 1;31if (!exp)32break;33base *= base;34}35return result;36}37{42double C = 0.0f;43uint32_t n;44* The size of pseudo-merge groups decays according to a power series,47* which looks like:48*49* f(n) = C * n^-k50*51* , where 'n' is the n-th pseudo-merge group, 'f(n)' is its size, 'k'52* is the decay rate, and 'C' is a scaling value.53*54* The value of C depends on the number of groups, decay rate, and total55* number of commits. It is computed such that if there are M and N56* total groups and commits, respectively, that:57*58* N = f(0) + f(1) + ... f(M-1)59*60* Rearranging to isolate C, we get:61*62* N = \sum_{n=1}^M C / n^k63*64* N / C = \sum_{n=1}^M n^-k65*66* C = N / \sum_{n=1}^M n^-k67*68* For example, if we have a decay rate of 'k' being equal to 1.5, 'N'69* total commits equal to 10,000, and 'M' being equal to 6 groups, then70* the (rounded) group sizes are:71*72* { 5469, 1934, 1053, 684, 489, 372 }73*74* increasing the number of total groups, say to 10, scales the group75* sizes appropriately:76*77* { 5012, 1772, 964, 626, 448, 341, 271, 221, 186, 158 }78*/79for (n = 0; n < group->max_merges; n++)80C += 1.0 / gitexp(n + 1, group->decay);81C = matches->unstable_nr / C;82}85{88memset(group, 0, sizeof(struct pseudo_merge_group));89}99{104struct string_list *list = cb_data;105struct string_list_item *item;106struct pseudo_merge_group *group;107struct strbuf buf = STRBUF_INIT;108const char *sub, *key;109size_t sub_len;110int ret = 0;111}185{189struct string_list_item *item;190}203{210struct bitmap_writer *writer = _data;211struct object_id peeled;212struct commit *c;213uint32_t i;214int has_bitmap;215}278{281struct commit *merge;282}293{298struct pseudo_merge_commit_idx *pmc;299int hash_ret;300khiter_t hash_pos = kh_put_oid_map(pseudo_merge_commits, *oid,301&hash_ret);302}312{319uint32_t i, j;320uint32_t stable_merges_nr;321* For each pseudo-merge created above, add parents to the339* allocated commit node from the stable set of commits340* (un-bitmapped, newer than the stable threshold).341*/342do {343struct commit *c;344struct pseudo_merge_commit_idx *pmc;345* Here and below, make sure that we keep our mapping of352* commits -> pseudo-merge(s) which include the key'd353* commit up-to-date.354*/355pmc = pseudo_merge_idx(writer->pseudo_merge_commits,356&c->object.oid);357* For each pseudo-merge commit created above, add parents to384* the allocated commit node from the unstable set of commits385* (newer than the stable threshold).386*387* Account for the sample rate, since not every candidate from388* the set of stable commits will be included as a pseudo-merge389* parent.390*/391for (; j < end && j < matches->unstable_nr; j++) {392struct commit *c = matches->unstable[j];393struct pseudo_merge_commit_idx *pmc;394}414{417timestamp_t a = (*(const struct commit **)va)->date;418timestamp_t b = (*(const struct commit **)vb)->date;419}426{429QSORT(matches->stable, matches->stable_nr, commit_date_cmp);430QSORT(matches->unstable, matches->unstable_nr, commit_date_cmp);431}432{435struct progress *progress = NULL;436uint32_t i;437}467{470uint32_t i;471for (i = 0; i < pm->nr; i++) {472ewah_pool_free(pm->v[i].commits);473ewah_pool_free(pm->v[i].bitmap);474}475free(pm->v);476}477{486if (at >= pm->map_size)487return error(_("extended pseudo-merge read out-of-bounds "488"(%"PRIuMAX" >= %"PRIuMAX")"),489(uintmax_t)at, (uintmax_t)pm->map_size);490if (at + 4 >= pm->map_size)491return error(_("extended pseudo-merge entry is too short "492"(%"PRIuMAX" >= %"PRIuMAX")"),493(uintmax_t)(at + 4), (uintmax_t)pm->map_size);494}500{504if (!merge->loaded_commits)505BUG("cannot use unloaded pseudo-merge bitmap");506}516{520if (!merge->loaded_commits) {521size_t pos = merge->at;522}529{534size_t lo = 0;535size_t hi = pm->nr;536}554{565merge->commit_pos = get_be32(at);566merge->pseudo_merge_ofs = get_be64(at + sizeof(uint32_t));567}568{574size_t ofs;575}589{595if (merge->satisfied)596return 0;597}608{611struct pseudo_merge_commit merge;612uint32_t key = *(uint32_t*)va;613}622{626if (!pm->commits_nr)627return NULL;628}632{637struct pseudo_merge *merge;638struct pseudo_merge_commit *merge_commit;639int ret = 0;640}686{691unsigned any_satisfied;692int ret = 0;693}711{715struct pseudo_merge *match = NULL;716size_t i;717* NOTE: this loop is quadratic in the worst-case (where no723* matching pseudo-merge bitmaps are found), but in practice724* this is OK for a few reasons:725*726* - Rejecting pseudo-merge bitmaps that do not match the727* given commit is done quickly (i.e. `bitmap_equals_ewah()`728* returns early when we know the two bitmaps aren't equal.729*730* - Already matched pseudo-merge bitmaps (which we track with731* the `->satisfied` bit here) are skipped as potential732* candidates.733*734* - The number of pseudo-merges should be small (in the735* hundreds for most repositories).736*737* If in the future this semi-quadratic behavior does become a738* problem, another approach would be to keep track of which739* pseudo-merges are still "viable" after enumerating the740* pseudo-merge commit's parents:741*742* - A pseudo-merge bitmap becomes non-viable when the bit(s)743* corresponding to one or more parent(s) of the given744* commit are not set in a candidate pseudo-merge's commits745* bitmap.746*747* - After processing all bits, enumerate the remaining set of748* viable pseudo-merge bitmaps, and check that their749* popcount() matches the number of parents in the given750* commit.751*/752for (i = 0; i < pm->nr; i++) {753struct pseudo_merge *candidate = use_pseudo_merge(pm, &pm->v[i]);754if (!candidate || candidate->satisfied)755continue;756if (!bitmap_equals_ewah(parents, candidate->commits))757continue;758}766