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;
    }
}