For example we have an array of 1 Million records, each record is a structure.
How can we achieve high performance to identify the empty slot for use?
we can use the same trick Oracle used:
We use integers's every bit to save the status flag of each element of the array.
normally one un-signed integer is 32 bits, so for one Million records, we need total : 1000000 / 32 = 31250 integers, if it is long, we can devide it by 2 again.
for when we look for an empty slot, we can check whether first integer's value is 4294967295 (MAX_INT if I am correct)
if it is less than MAX_INT, we then search bit by bit of this unsigned integer to get one bit with zero value.
if it is equal to MAX_INT, then move to next integer.
to search for 31250 unsigned integers, it is still quite a lot, maybe we can find some other ways to achieve a more effecient method.
Once we find the empty slot and used it, we should bring along its index when the information of that record has to be passed among processes via message queue or other ways, otherwise search such big array could be a painful experience.