* Determine optimal on-disk fanout for this part of the notes tree * * Given a (sub)tree and the level in the internal tree structure, determine * whether or not the given existing fanout should be expanded for this * (sub)tree. * * Values of the 'fanout' variable: * - 0: No fanout (all notes are stored directly in the root notes tree) * - 1: 2/38 fanout * - 2: 2/2/36 fanout * - 3: 2/2/2
| 516 | * etc. |
| 517 | */ |
| 518 | static unsigned char determine_fanout(struct int_node *tree, unsigned char n, |
| 519 | unsigned char fanout) |
| 520 | { |
| 521 | /* |
| 522 | * The following is a simple heuristic that works well in practice: |
| 523 | * For each even-numbered 16-tree level (remember that each on-disk |
| 524 | * fanout level corresponds to _two_ 16-tree levels), peek at all 16 |
| 525 | * entries at that tree level. If all of them are either int_nodes or |
| 526 | * subtree entries, then there are likely plenty of notes below this |
| 527 | * level, so we return an incremented fanout. |
| 528 | */ |
| 529 | unsigned int i; |
| 530 | if ((n % 2) || (n > 2 * fanout)) |
| 531 | return fanout; |
| 532 | for (i = 0; i < 16; i++) { |
| 533 | switch (GET_PTR_TYPE(tree->a[i])) { |
| 534 | case PTR_TYPE_SUBTREE: |
| 535 | case PTR_TYPE_INTERNAL: |
| 536 | continue; |
| 537 | default: |
| 538 | return fanout; |
| 539 | } |
| 540 | } |
| 541 | return fanout + 1; |
| 542 | } |
| 543 | |
| 544 | /* hex oid + '/' between each pair of hex digits + NUL */ |
| 545 | #define FANOUT_PATH_MAX GIT_MAX_HEXSZ + FANOUT_PATH_SEPARATORS_MAX + 1 |
no outgoing calls
no test coverage detected