Re: [PATCH v2 12/19] read-cache: read index-v5

> A little bit more..
>
> On Sat, Jul 13, 2013 at 12:26 AM, Thomas Gummerer <t.gummerer@gmail.com> wrote:
>> +static void ce_queue_push(struct cache_entry **head,
>> +                            struct cache_entry **tail,
>> +                            struct cache_entry *ce)
>> +{
>> +       if (!*head) {
>> +               *head = *tail = ce;
>> +               (*tail)->next = NULL;
>> +               return;
>> +       }
>> +
>> +       (*tail)->next = ce;
>> +       ce->next = NULL;
>> +       *tail = (*tail)->next;
>
> No no no. "next" is for name-hash.c don't "reuse" it here. And I don't
> think you really need to maintain a linked list of cache_entries by
> the way. More on read_entries comments below..

>> +}
>> +
>> +static struct cache_entry *ce_queue_pop(struct cache_entry **head)
>> +{
>> +       struct cache_entry *ce;
>> +
>> +       ce = *head;
>> +       *head = (*head)->next;
>> +       return ce;
>> +}
>
> Same as ce_queue_push.
>
>> +static int read_entries(struct index_state *istate, struct directory_entry **de,
>> +                       unsigned int *entry_offset, void **mmap,
>> +                       unsigned long mmap_size, unsigned int *nr,
>> +                       unsigned int *foffsetblock)
>> +{
>> +       struct cache_entry *head = NULL, *tail = NULL;
>> +       struct conflict_entry *conflict_queue;
>> +       struct cache_entry *ce;
>> +       int i;
>> +
>> +       conflict_queue = NULL;
>> +       if (read_conflicts(&conflict_queue, *de, mmap, mmap_size) < 0)
>> +               return -1;
>> +       for (i = 0; i < (*de)->de_nfiles; i++) {
>> +               if (read_entry(&ce,
>> +                              *de,
>> +                              entry_offset,
>> +                              mmap,
>> +                              mmap_size,
>> +                              foffsetblock) < 0)
>> +                       return -1;
>> +               ce_queue_push(&head, &tail, ce);
>> +               *foffsetblock += 4;
>> +
>> +               /*
>> +                * Add the conflicted entries at the end of the index file
>> +                * to the in memory format
>> +                */
>> +               if (conflict_queue &&
>> +                   (conflict_queue->entries->flags & CONFLICT_CONFLICTED) != 0 &&
>> +                   !cache_name_compare(conflict_queue->name, conflict_queue->namelen,
>> +                                       ce->name, ce_namelen(ce))) {
>> +                       struct conflict_part *cp;
>> +                       cp = conflict_queue->entries;
>> +                       cp = cp->next;
>> +                       while (cp) {
>> +                               ce = convert_conflict_part(cp,
>> +                                               conflict_queue->name,
>> +                                               conflict_queue->namelen);
>> +                               ce_queue_push(&head, &tail, ce);
>> +                               conflict_part_head_remove(&cp);
>> +                       }
>> +                       conflict_entry_head_remove(&conflict_queue);
>> +               }
>
> I start to wonder if separating staged entries is a good idea. It
> seems to make the code more complicated. The good point about conflict
> section at the end of the file is you can just truncate() it out.
> Another way is putting staged entries in fileentries, sorted
> alphabetically then by stage number, and a flag indicating if the
> entry is valid. When you remove resolve an entry, just set the flag to
> invalid (partial write), so that read code will skip it.
>
> I think this approach is reasonably cheap (unless there are a lot of
> conflicts) and it simplifies this piece of code. truncate() may be
> overrated anyway. In my experience, I "git add <path>" as soon as I
> resolve <path> (so that "git diff" shrinks). One entry at a time, one
> index write at a time. I don't think I ever resolve everything then
> "git add -u .", which is where truncate() shines because staged
> entries are removed all at once. We should optimize for one file
> resolution at a time, imo.
>
>> +       }
>> +
>> +       *de = (*de)->next;
>> +
>> +       while (head) {
>> +               if (*de != NULL
>> +                   && strcmp(head->name, (*de)->pathname) > 0) {
>> +                       read_entries(istate,
>> +                                    de,
>> +                                    entry_offset,
>> +                                    mmap,
>> +                                    mmap_size,
>> +                                    nr,
>> +                                    foffsetblock);
>> +               } else {
>> +                       ce = ce_queue_pop(&head);
>> +                       set_index_entry(istate, *nr, ce);
>> +                       (*nr)++;
>> +                       ce->next = NULL;
>> +               }
>
> In this loop, you do some sort of merge sort combining a list of
> sorted files and a list of sorted directories (which will be expanded
> to bunches of files by the recursive read_entries). strcmp() does two
> things. Assume we're in directory 'a', it makes sure that subdirectory
> 'a/b' is only inserted after file 'a/a' is inserted to maintain index
> sort order. It also makes sure that 'de' of an outside directory 'b'
> will not be expanded here. strcmp will be called for every file,
> checking _full_ path. Sounds expensive.
>
> If you maintain two pointers first_subdir and next_sibling in "de" as
> in my previous mail, you know "de" 'b' is out without string
> comparison (de->next_sibling would be NULL). With that, the purpose of
> strcmp is simply making sure that 'a/b' is inserted after 'a/a'.
> Because we know all possible "de" is a subdirectory of 'a', we don't
> need to compare the prefix 'a/'. We still need to strcmp on every
> file, but we only need to compare the file name, not the leading
> directory anymore. Cheaper.
>
> Going further, I wonder if we could eliminate strcmp completely. We
> could store dummy entries in fileentries to mark the positions of the
> subdirectories. When we encounter a dummy entry, we call
> read_entries() instead of set_index_entry.

>> +       }
>> +       return 0;
>> +}
>> +
> --
> Duy