<div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">On Fri, Feb 27, 2015 at 9:03 AM, Zbigniew Jędrzejewski-Szmek <span dir="ltr"><<a href="mailto:zbyszek@in.waw.pl" target="_blank">zbyszek@in.waw.pl</a>></span> wrote:<br><span style="color:rgb(80,0,80)">> > We need two operations: sorting kernels to list them, and picking (I</span><br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div class="HOEnZb"><div class="h5">On Fri, Feb 27, 2015 at 08:58:04AM -0800, Shawn Landden wrote:<br>
> On Thu, Feb 26, 2015 at 6:22 PM, Zbigniew Jędrzejewski-Szmek <<br>
> <a href="mailto:zbyszek@in.waw.pl">zbyszek@in.waw.pl</a>> wrote:<br>
><br>
> > On Thu, Feb 26, 2015 at 08:04:08AM +0000, Jan Janssen wrote:<br>
> > > Shawn Landden <shawn <at> <a href="http://churchofgit.com" target="_blank">churchofgit.com</a>> writes:<br>
> > ><br>
> > > >  void strv_free(char **l) {<br>
> > > > -        strv_clear(l);<br>
> > > > +        char **k;<br>
> > > > +<br>
> > > > +        if (!l)<br>
> > > > +                return;<br>
> > > > +<br>
> > > > +        for (k = l; *k; k++)<br>
> > > > +                free(*k);<br>
> > > > +<br>
> > > >          free(l);<br>
> > > >  }<br>
> > > What are you trying to achieve here? I see no point in optimizing out<br>
> > the *l<br>
> > > = NULL from strv_clear.<br>
> > ><br>
> > > > +                                entry->linux_loc  = l + strspn(l,<br>
> > > WHITESPACE);<br>
> > > > +                        else if ((l = startswith(m, "initrd ")))<br>
> > > > +                                entry->initrd     = l + strspn(l,<br>
> > > WHITESPACE);<br>
> > > You need to support more than one initrd per kernel, see<br>
> > > <a href="https://wiki.archlinux.org/index.php/Microcode" target="_blank">https://wiki.archlinux.org/index.php/Microcode</a> for why. Also, I am<br>
> > pretty<br>
> > > sure you can have a initrd=/path/to/initrd in the kernel options entry.<br>
> > > Since the efi bootloader just appends each given initrd to the kernel<br>
> > > command line.<br>
> > ><br>
> > ><br>
> > > All in all I am wondering why you need a rbtree for all this in the first<br>
> > > place? A simple hashmap should do just fine.<br>
> > A hashmap does not keep order. But a simple array + qsort_safe() should<br>
> > work too. I'm wary of introducing yet another data structure into systemd<br>
> > which raises the bar for people editing the code later on or making<br>
> > changes.<br>
> ><br>
> > presume) the<br>
> > latest kernel or the kernel with the given version. Both of those<br>
> > operations<br>
> > are done once over the lifetime of the program, so any speedup in using<br>
> > a data structure should take into account the time to set up the structure.<br>
> > Neither of those operations is speed sensitive, and the more common<br>
> > operation<br>
> > of picking a specific version can be done in O(n) over an array. So using<br>
> > an rbtree will not save any time actually.<br>
> ><br>
> I was initially using a vector of pointers here for the same reasons you<br>
> reiterated, but I felt the use of greedy_realloc0() was messy and<br>
> error-prone.<br>
</div></div>greedy_realloc0() is not that messy. And it would be just a few lines<br>
of code. We have similar patterns in many other places, and<br>
consistency is good.<br>
<span class=""><br>
> The rbtree does not require the use of realloc(). There is no<br>
> way to know how long the array needs to be from the start. Even the O(n)<br>
> you mention could be turned into O(logn) by using a binary search.<br>
</span>Nope. The array needs to be sorted to do a binary search. So the<br>
upfront cost of sorting kills any gain you get later on.<br></blockquote><div>Oh I see, you don't have to sort in that case. But the code would be longer, so perhaps I will sort in all cases.</div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
<div class="HOEnZb"><div class="h5"><br>
Zbyszek<br>
_______________________________________________<br>
systemd-devel mailing list<br>
<a href="mailto:systemd-devel@lists.freedesktop.org">systemd-devel@lists.freedesktop.org</a><br>
<a href="http://lists.freedesktop.org/mailman/listinfo/systemd-devel" target="_blank">http://lists.freedesktop.org/mailman/listinfo/systemd-devel</a><br>
</div></div></blockquote></div><br><br clear="all"><div><br></div>-- <br><div class="gmail_signature">Shawn Landden</div>
</div></div>