nl_tokens: / * this function allocates space for the inserted value and as it searches uses that space to store the previous links . when it finds the insertion point it flips those values around updates the previous pointers to point to this value and sets these pointers to point to the previous s next s values .
pl_tokens: function insert ( b , ptr , target , level , compare ) { level = level || r_levels ( b , ptr ) compare = compare || _compare var free = b . readUInt32LE ( 0 ) || 8 //figure out before hand how many levels deep we want to insert this value for ( var _level = 0 ; _level < level && Math . random ( ) > 0.5 ; ) _level ++ //update free space pointer: address of last level + 4 (space for target value) b . writeUInt32LE ( 4 + get_next ( free , _level ) , 0 ) //make space for this item. //insert value at start of previous free space b . writeUInt32LE ( target , free ) while ( true ) { if ( level < 0 ) break ; //if this level is last item var next_ptr = r_level ( b , ptr , level ) if ( next_ptr === 0 || compare ( r_value ( b , next_ptr ) , target , b ) > 0 ) { //store value of previous pointer if ( level <= _level ) b . writeUInt32LE ( ptr , get_next ( free , level ) ) <mask> -- } else { ptr = next_ptr } } //write a backlink. b . writeUInt32LE ( b . readUInt32LE ( free + get_next ( 0 ) ) & 0x7fffffff ) //I think if insert items bottom up, and set the new pointer first //then this should be fully threadsafe. for ( var i = 0 ; i <= _level ; i ++ ) { var prev = b . readUInt32LE ( get_next ( free , i ) ) var next = b . readUInt32LE ( get_next ( prev , i ) ) //includes msb continue flag //these say Int 32, but remember the msb is 1 which means negative. //so this is actually correct. b . writeInt32LE ( i < _level ? next | 0x80000000 : next & 0x7fffffff , get_next ( free , i ) ) //free, free | (next & 0x80000000)) b . writeInt32LE ( free | ( next & 0x80000000 ) , get_next ( prev , i ) ) } return free }