Listing 5: Skiplist insertion function
template <class DATA, class KEY> int Skiplist<DATA,KEY>::rand_level() { int level = 1; while ( rand() % 4 == 0 && level < SLMAX_LEVEL ) { level++; } return( level ); } template <class DATA, class KEY> void Skiplist<DATA,KEY>::insert( DATA *data, const KEY &key ) { SLPosition<DATA,KEY> *update[SLMAX_LEVEL]; SLPosition<DATA,KEY> *cur = &head; SLPosition<DATA,KEY> *new_pos; int pos_level; int i; for( i = level-1; i >= 0; i-- ) { while( cur->forward[i] != NULL && cur->forward[i]->key < key ) { cur = cur->forward[i]; } update[i] = cur; } pos_level = rand_level(); new_pos = new SLPosition<DATA,KEY>( pos_level, data, key ); if( pos_level > level ) { for( i = level; i < pos_level; i++ ) { update[i] = &head; } level = pos_level; } for( i = 0; i < pos_level; i++ ) { new_pos->forward[i] = update[i]->forward[i]; update[i]->forward[i] = new_pos; } }