[Date Prev][Date Next] [Chronological] [Thread] [Top]

Re: Greatest value

weston@itdonline.net wrote:
> for the rather inefficient way I ended up solving this problem. (it's close to
> something I wrote in PHP)
> while ( ldap_search( uidnumber=new_uidnumber ) )
>       //loop and increment until the new number does
> Now, this is probably really dumb code, but it works for me. If anyone has any
> other suggestions, please let me know.

Eh, that *is* dumb code ;-)

If you know the maximum UID (and you *do* know that), and the minimum,
the difference of those being N, you can search through the server with
2 log N steps to find the highest UID:


ldap_search ( uidnumber > GUESS )
	// if there is at least one value, then set BOTTOM=GUESS
	// if you found no value, set TOP=GUESS
repeat this while TOP != BOTTOM.

So lets say your uid's range from 1000-5000 and your highest UID at the
moment is 2149.

GUESS=(5000+1000) DIV 2 == 3000 search uid>GUESS, nothing found, set
GUESS=(3000+1000) DIV 2 == 2000 search.... found some, BOTTOM=2000
GUESS=(3000+2000) DIV 2 == 2500 search.... found none, TOP == 2500
GUESS=(2500+2000) DIV 2 == 2250 search.... found none, TOP == 2250
GUESS=(2250+2000) DIV 2 == 2125 search uid > 2125, found some, BOTTOM ==
GUESS=(2250+2125) DIV 2 == 2187 search uid > 2187, found none, TOP=2187
GUESS=(2187+2125) DIV 2 == 2156 search uid > 2156, found none, TOP=2156
GUESS=(2156+2125) DIV 2 == 2140 search uid > 2140, found some,
GUESS=(2156+2140) DIV 2 == 2148 search uid > 2148, found none, TOP=2148

(notice we're there, only we did not notice yet ;)

OK, so in another 3 steps, we're there, in some 10 steps total. Your
solution, however, would require some 1148 steps. Even worse is the fact
that the more users you have, *the more steps it requires*, so your
solution will ultimately hang itself ;-)

Now the code that searches like the above is no problem to use, even for
high volume LDAP servers: some 10 searches to find a new UID should form
no problem whatsoever for any LDAP implementation.

The only problem with the above code is that you cannot find any 'left
over' numbers, i.e. if you fire all employees with uid's < 1200 due to
budget restrictions, the algorithm will still come up with 2149 as next
value to use. Thus you should keep information about your old users -
and probably set their employeeType to ``fired'' ;-)

Valentijn Sessink - valentyn@nospam.openoffice.nl
Open Office - Linux for the desktop - www.openoffice.nl