This is the mail archive of the
mailing list for the glibc project.
Re: [RFC] Make getenv O(1)
- From: OndÅej BÃlka <neleai at seznam dot cz>
- To: Rich Felker <dalias at aerifal dot cx>
- Cc: libc-alpha at sourceware dot org
- Date: Mon, 14 Oct 2013 19:28:52 +0200
- Subject: Re: [RFC] Make getenv O(1)
- Authentication-results: sourceware.org; auth=none
- References: <20131014155229 dot GA25159 at domone dot podge> <20131014165411 dot GZ20515 at brightrain dot aerifal dot cx>
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.