[RFC] Make getenv O(1)

[Ondřej Bílka]

On Mon, Oct 14, 2013 at 12:54:12PM -0400, Rich Felker wrote:
> On Mon, Oct 14, 2013 at 05:52:29PM +0200, Ondřej Bílka wrote:
> > Hi, when I browsed getenv i found that it uses linear search.
> > 
> > But in getenv there is code that uses trees and I have doubts about its
> > usefullness.
> > 
> > The getenv/setenv could be easily changed to use hash table, does
> > something block us to do so?
> > 
> > A possible complication would be that we need additionaly maintain
> > __environ which causes some code overhead.
> > 
> > Comments?
> 
> In general it's impossible to use anything but linear search because
> the application can modify environ[] directly (although it's
> questionable whether this is permissible by the standard) 


Linear search applies only when environment variable is not present.
When it is present then getting its index in environ and checking that
it matches should be O(1). 

> or use
> putenv and modify the strings after they're added to the environment
> (this is explicitly permitted by POSIX). There may be cases where it's
> possible to detect that this does not happen and use a faster
> approach; I'm not sure.
> 
If changing environ would be disallowed then it would be matter of
keeping a list of variables added by putenv which would be empty for
most applications so overhead of this would be minimal.