Well, TBH, I'd use the resource tracking built into my plug-ins. :p
As well as all of the standard FIND FREE XXXX functions (eg FIND FREE OBJECT etc), I recently added user-defined resources too:
dim a(9) as integer
make freelist 1, 0, 10, -1 ` Ten items numbered from 0, using -1 as 'not found'
id = -1
for i = 0 to 9
a(i) = -1
next
do
k$ = lower$(inkey$())
if k$ = "a"
id = get from freelist(1)
if id >= 0 then a(id) = rnd(100)+1
else
if k$ >= "0" and k$ <= "9"
id = val(k$)
if return to freelist(1, id) then a(id) = -1
endif
endif
cls
for i = 0 to 9
print i; " - "; a(i);
if id = i
print "*"
else
print ""
endif
next
if id = -1
print
print "No more room in the array"
endif
wait key
loop
Now for the technique I used for this...
The older functions pick a random number as a start point, then increment the id, wrapping back to 1 when they reach a certain limit and continuing until they reach the start point. If they find an unused ID along the way, then they return that number and stop.
The newer functions use a far faster technique. Each resource keeps a set of 2 integers denoting a range of unused IDs, for example objects have a single pair of 1 to 262144 (256k). When an object is allocated, the ranges are checked to find the relevant one. If the id is the first in the range, then the start is adjusted up by 1, if it's the last in the range, then the end is adjusted down by 1, and if the number is in the middle of the range, the range is split into 2 ranges.
Here's an example:
Start with a range of 1-1000
Allocate id 10 -> 1-9,11-1000
Allocate id 11 -> 1-9,12-1000
Allocate id 9 -> 1-8,12-1000
Allocate id 20 -> 1-8,12-19,21-1000
When an id is freed then a similar search is carried out. If the id is 1 less than the start of a range, the start is reduced by 1. If the id is 1 greater then the end of a range, then 1 is added to the end. Once this is carried out, a quick check is made to see if 2 ranges can be joined into a single range. If no match is found, then a new range is created with the start and end set to the same id.
Free id 9 -> 1-9,12-19,21-1000
Free id 11 -> 1-9,11-19,21-1000
Free id 20 -> 1-9,11-20,21-1000 -> Now have two ranges that can be joined -> 1-9,11-1000
Free id 10 -> 1-10,11-1000 -> Now have two ranges that can be joined -> 1-1000
The implementation I used doesn't use an array or linked list, but that's basically it.
Although I haven't implemented it, you can also use the same process for determining ids that are in use too, simply by looping from 1 to the start of the first range, then from the end of the first range to the start of the second range etc.
