Re: [PATCH v7 1/3] worktree: add top-level worktree.c

[Mike Rappazzo <rappazzo@gmail.com>]

On Wed, Sep 16, 2015 at 4:32 PM, Eric Sunshine <sunshine@sunshineco.com> wrote:
> On Mon, Sep 14, 2015 at 8:20 AM, Mike Rappazzo <rappazzo@gmail.com> wrote:
>> On Sat, Sep 12, 2015 at 10:39 PM, Eric Sunshine <sunshine@sunshineco.com> wrote:
>>>> +struct worktree {
>>>> +       char *path;
>>>> +       char *git_dir;
>>>> +       char *head_ref;
>>>> +       unsigned char head_sha1[20];
>>>> +       int is_detached;
>>>> +       int is_bare;
>>>> +};
>>>> +
>>>> +struct worktree_list {
>>>> +       struct worktree *worktree;
>>>> +       struct worktree_list *next;
>>>> +};
>>>
>>> I don't care too strongly, but an alternate approach (which I probably
>>> would have taken) would be to have get_worktrees() simply return an
>>> array of 'struct worktree' objects, hence no need for the additional
>>> 'struct worktree_list'. The slight complication with this approach,
>>> though, is that get_worktrees() either also needs to return the length
>>> of the array, or the array should end with some sort of end-of-array
>>> sentinel. An obvious sentinel would be path==NULL or git_dir==NULL or
>>> all of the above.
>>>
>>> Client iteration is just about the same with the array approach as
>>> with the linked-list approach.
>>
>> I can't see what benefit this would provide.  I would sooner change
>> the returned list into
>> an array-backed list struct.  Alternatively, I think adding a
>> list_head pointer to this structure
>> could benefit client code.
>
> The benefit is a reduction in complexity, which is an important goal.
> Linked lists are inherently more complex than arrays, requiring extra
> effort, and especially extra care, to manage the head, each "next"
> pointer (and possibly a tail pointer). Arrays are used often in Git,
> thus are familiar in this code-base, and Git has decent support for
> making their management relatively painless. Your suggestions of
> changing into "an array-backed list structure" or "adding list_head
> pointer" increase complexity, rather than reduce it.
>
> Aside from the complexity issue, arrays allow random access, whereas
> linked lists allow only sequential access. While this limitation may
> not impact your current, planned use of get_worktrees(), it places a
> potentially unnecessary restriction on future clients.
>
> And, as noted, client iteration is at least as convenient with arrays,
> if not moreso, due to the reduction in noise ("p++" rather than "p =
> p->next").
>
>     struct worktree *p;
>     for (p = get_worktrees(); p->path; p++)
>         blarp(p);
>
> There are cases where linked lists are an obvious win, but this
> doesn't seem to be such a case. On the other hand, there are obvious
> benefits to making this an array, such as reduced complexity and
> removal of the sequential-access-only restriction.

What you are suggesting makes sense, but I feel it falls short when it
comes to the "sentinel".  Would the last element in the list be a
dummy worktree?  I would sooner add a NULL to the end.  Would that be
an acceptable implementation?

I have re-coded it to put the next pointer in the worktree structure
as Junio has suggested, but I am open to changing it to use the array
approach.