Merge pull request #192 from jpcima/std-structures

Std structures

4 files changed, 694 insertions, 368 deletions

diff --git a/src/adlmidi_midiplay.cpp b/src/adlmidi_midiplay.cpp
index 11e3f1a..f96243e 100644
--- a/src/adlmidi_midiplay.cpp
+++ b/src/adlmidi_midiplay.cpp
@@ -106,7 +106,7 @@ inline bool isXgPercChannel(uint8_t msb, uint8_t lsb)
 void MIDIplay::AdlChannel::addAge(int64_t us)
 {
     const int64_t neg = 1000 * static_cast<int64_t>(-0x1FFFFFFFll);
-    if(users_empty())
+    if(users.empty())
     {
         koff_time_until_neglible_us = std::max(koff_time_until_neglible_us - us, neg);
         if(koff_time_until_neglible_us < 0)
@@ -115,11 +115,12 @@ void MIDIplay::AdlChannel::addAge(int64_t us)
     else
     {
         koff_time_until_neglible_us = 0;
-        for(LocationData *i = users_first; i; i = i->next)
+        for(users_iterator i = users.begin(); !i.is_end(); ++i)
         {
-            if(!i->fixed_sustain)
-                i->kon_time_until_neglible_us = std::max(i->kon_time_until_neglible_us - us, neg);
-            i->vibdelay_us += us;
+            LocationData &d = i->value;
+            if(!d.fixed_sustain)
+                d.kon_time_until_neglible_us = std::max(d.kon_time_until_neglible_us - us, neg);
+            d.vibdelay_us += us;
         }
     }
 }
@@ -293,12 +294,13 @@ bool MIDIplay::realTime_NoteOn(uint8_t channel, uint8_t note, uint8_t velocity)
     if((synth.m_musicMode == Synth::MODE_RSXX) && (velocity != 0))
     {
         // Check if this is just a note after-touch
-        MIDIchannel::activenoteiterator i = m_midiChannels[channel].activenotes_find(note);
-        if(i)
+        MIDIchannel::notes_iterator i = m_midiChannels[channel].find_activenote(note);
+        if(!i.is_end())
         {
-            const int veloffset = i->ains->midi_velocity_offset;
+            MIDIchannel::NoteInfo &ni = i->value;
+            const int veloffset = ni.ains->midi_velocity_offset;
             velocity = (uint8_t)std::min(127, std::max(1, (int)velocity + veloffset));
-            i->vol = velocity;
+            ni.vol = velocity;
             noteUpdate(channel, i, Upd_Volume);
             return false;
         }
@@ -467,11 +469,11 @@ bool MIDIplay::realTime_NoteOn(uint8_t channel, uint8_t note, uint8_t velocity)
     if(isBlankNote)
     {
         // Don't even try to play the blank instrument! But, insert the dummy note.
-        std::pair<MIDIchannel::activenoteiterator, bool>
-        dummy = midiChan.activenotes_insert(note);
-        dummy.first->isBlank = true;
-        dummy.first->ains = NULL;
-        dummy.first->chip_channels_count = 0;
+        MIDIchannel::notes_iterator i = midiChan.ensure_find_or_create_activenote(note);
+        MIDIchannel::NoteInfo &dummy = i->value;
+        dummy.isBlank = true;
+        dummy.ains = NULL;
+        dummy.chip_channels_count = 0;
         // Record the last note on MIDI channel as source of portamento
         midiChan.portamentoSource = static_cast<int8_t>(note);
         return false;
@@ -564,18 +566,18 @@ bool MIDIplay::realTime_NoteOn(uint8_t channel, uint8_t note, uint8_t velocity)
         velocity = static_cast<uint8_t>(std::floor(static_cast<float>(velocity) * 0.8f));
 
     // Allocate active note for MIDI channel
-    std::pair<MIDIchannel::activenoteiterator, bool>
-    ir = midiChan.activenotes_insert(note);
-    ir.first->vol     = velocity;
-    ir.first->vibrato = midiChan.noteAftertouch[note];
-    ir.first->noteTone = static_cast<int16_t>(tone);
-    ir.first->currentTone = tone;
-    ir.first->glideRate = HUGE_VAL;
-    ir.first->midiins = midiins;
-    ir.first->isPercussion = isPercussion;
-    ir.first->isBlank = isBlankNote;
-    ir.first->ains = ains;
-    ir.first->chip_channels_count = 0;
+    MIDIchannel::notes_iterator ir = midiChan.ensure_find_or_create_activenote(note);
+    MIDIchannel::NoteInfo &ni = ir->value;
+    ni.vol     = velocity;
+    ni.vibrato = midiChan.noteAftertouch[note];
+    ni.noteTone = static_cast<int16_t>(tone);
+    ni.currentTone = tone;
+    ni.glideRate = HUGE_VAL;
+    ni.midiins = midiins;
+    ni.isPercussion = isPercussion;
+    ni.isBlank = isBlankNote;
+    ni.ains = ains;
+    ni.chip_channels_count = 0;
 
     int8_t currentPortamentoSource = midiChan.portamentoSource;
     double currentPortamentoRate = midiChan.portamentoRate;
@@ -588,8 +590,8 @@ bool MIDIplay::realTime_NoteOn(uint8_t channel, uint8_t note, uint8_t velocity)
     // Enable gliding on portamento note
     if (portamentoEnable && currentPortamentoSource >= 0)
     {
-        ir.first->currentTone = currentPortamentoSource;
-        ir.first->glideRate = currentPortamentoRate;
+        ni.currentTone = currentPortamentoSource;
+        ni.glideRate = currentPortamentoRate;
         ++midiChan.gliding_note_count;
     }
 
@@ -599,10 +601,10 @@ bool MIDIplay::realTime_NoteOn(uint8_t channel, uint8_t note, uint8_t velocity)
         if(c < 0)
             continue;
         uint16_t chipChan = static_cast<uint16_t>(adlchannel[ccount]);
-        ir.first->phys_ensure_find_or_create(chipChan)->assign(voices[ccount]);
+        ni.phys_ensure_find_or_create(chipChan)->assign(voices[ccount]);
     }
 
-    noteUpdate(channel, ir.first, Upd_All | Upd_Patch);
+    noteUpdate(channel, ir, Upd_All | Upd_Patch);
 
     for(unsigned ccount = 0; ccount < MIDIchannel::NoteInfo::MaxNumPhysChans; ++ccount)
     {
@@ -628,10 +630,10 @@ void MIDIplay::realTime_NoteAfterTouch(uint8_t channel, uint8_t note, uint8_t at
     if(static_cast<size_t>(channel) > m_midiChannels.size())
         channel = channel % 16;
     MIDIchannel &chan = m_midiChannels[channel];
-    MIDIchannel::activenoteiterator i = m_midiChannels[channel].activenotes_find(note);
-    if(i)
+    MIDIchannel::notes_iterator i = m_midiChannels[channel].find_activenote(note);
+    if(!i.is_end())
     {
-        i->vibrato = atVal;
+        i->value.vibrato = atVal;
     }
 
     uint8_t oldAtVal = chan.noteAftertouch[note % 128];
@@ -1115,12 +1117,12 @@ void MIDIplay::AudioTick(uint32_t chipId, uint32_t rate)
 #endif
 
 void MIDIplay::noteUpdate(size_t midCh,
-                          MIDIplay::MIDIchannel::activenoteiterator i,
+                          MIDIplay::MIDIchannel::notes_iterator i,
                           unsigned props_mask,
                           int32_t select_adlchn)
 {
     Synth &synth = *m_synth;
-    MIDIchannel::NoteInfo &info = *i;
+    MIDIchannel::NoteInfo &info = i->value;
     const int16_t noteTone    = info.noteTone;
     const double currentTone    = info.currentTone;
     const uint8_t vol     = info.vol;
@@ -1133,7 +1135,7 @@ void MIDIplay::noteUpdate(size_t midCh,
     if(info.isBlank)
     {
         if(props_mask & Upd_Off)
-            m_midiChannels[midCh].activenotes_erase(i);
+            m_midiChannels[midCh].activenotes.erase(i);
         return;
     }
 
@@ -1147,14 +1149,15 @@ void MIDIplay::noteUpdate(size_t midCh,
         if(props_mask & Upd_Patch)
         {
             synth.setPatch(c, ins.ains);
-            AdlChannel::LocationData *d = m_chipChannels[c].users_find_or_create(my_loc);
-            if(d)    // inserts if necessary
+            AdlChannel::users_iterator i = m_chipChannels[c].find_or_create_user(my_loc);
+            if(!i.is_end())    // inserts if necessary
             {
-                d->sustained = AdlChannel::LocationData::Sustain_None;
-                d->vibdelay_us = 0;
-                d->fixed_sustain = (ains.ms_sound_kon == static_cast<uint16_t>(adlNoteOnMaxTime));
-                d->kon_time_until_neglible_us = 1000 * ains.ms_sound_kon;
-                d->ins       = ins;
+                AdlChannel::LocationData &d = i->value;
+                d.sustained = AdlChannel::LocationData::Sustain_None;
+                d.vibdelay_us = 0;
+                d.fixed_sustain = (ains.ms_sound_kon == static_cast<uint16_t>(adlNoteOnMaxTime));
+                d.kon_time_until_neglible_us = 1000 * ains.ms_sound_kon;
+                d.ins       = ins;
             }
         }
     }
@@ -1172,15 +1175,15 @@ void MIDIplay::noteUpdate(size_t midCh,
         {
             if(!m_midiChannels[midCh].sustain)
             {
-                AdlChannel::LocationData *k = m_chipChannels[c].users_find(my_loc);
-                bool do_erase_user = (k && ((k->sustained & AdlChannel::LocationData::Sustain_Sostenuto) == 0));
+                AdlChannel::users_iterator k = m_chipChannels[c].find_user(my_loc);
+                bool do_erase_user = (!k.is_end() && ((k->value.sustained & AdlChannel::LocationData::Sustain_Sostenuto) == 0));
                 if(do_erase_user)
-                    m_chipChannels[c].users_erase(k);
+                    m_chipChannels[c].users.erase(k);
 
                 if(hooks.onNote)
                     hooks.onNote(hooks.onNote_userData, c, noteTone, midiins, 0, 0.0);
 
-                if(do_erase_user && m_chipChannels[c].users_empty())
+                if(do_erase_user && m_chipChannels[c].users.empty())
                 {
                     synth.noteOff(c);
                     if(props_mask & Upd_Mute) // Mute the note
@@ -1198,9 +1201,9 @@ void MIDIplay::noteUpdate(size_t midCh,
             {
                 // Sustain: Forget about the note, but don't key it off.
                 //          Also will avoid overwriting it very soon.
-                AdlChannel::LocationData *d = m_chipChannels[c].users_find_or_create(my_loc);
-                if(d)
-                    d->sustained |= AdlChannel::LocationData::Sustain_Pedal; // note: not erased!
+                AdlChannel::users_iterator d = m_chipChannels[c].find_or_create_user(my_loc);
+                if(!d.is_end())
+                    d->value.sustained |= AdlChannel::LocationData::Sustain_Pedal; // note: not erased!
                 if(hooks.onNote)
                     hooks.onNote(hooks.onNote_userData, c, noteTone, midiins, -1, 0.0);
             }
@@ -1302,24 +1305,24 @@ void MIDIplay::noteUpdate(size_t midCh,
 
         if(props_mask & Upd_Pitch)
         {
-            AdlChannel::LocationData *d = m_chipChannels[c].users_find(my_loc);
+            AdlChannel::users_iterator d = m_chipChannels[c].find_user(my_loc);
 
             // Don't bend a sustained note
-            if(!d || (d->sustained == AdlChannel::LocationData::Sustain_None))
+            if(d.is_end() || (d->value.sustained == AdlChannel::LocationData::Sustain_None))
             {
                 MIDIchannel &chan = m_midiChannels[midCh];
                 double midibend = chan.bend * chan.bendsense;
                 double bend = midibend + ins.ains.finetune;
                 double phase = 0.0;
                 uint8_t vibrato = std::max(chan.vibrato, chan.aftertouch);
-                vibrato = std::max(vibrato, i->vibrato);
+                vibrato = std::max(vibrato, info.vibrato);
 
                 if((ains.flags & adlinsdata::Flag_Pseudo4op) && ins.pseudo4op)
                 {
                     phase = ains.voice2_fine_tune;//0.125; // Detune the note slightly (this is what Doom does)
                 }
 
-                if(vibrato && (!d || d->vibdelay_us >= chan.vibdelay_us))
+                if(vibrato && (d.is_end() || d->value.vibdelay_us >= chan.vibdelay_us))
                     bend += static_cast<double>(vibrato) * chan.vibdepth * std::sin(chan.vibpos);
 
 #define BEND_COEFFICIENT 172.4387
@@ -1333,18 +1336,18 @@ void MIDIplay::noteUpdate(size_t midCh,
 
     if(info.chip_channels_count == 0)
     {
-        if(i->glideRate != HUGE_VAL)
+        if(info.glideRate != HUGE_VAL)
             --m_midiChannels[midCh].gliding_note_count;
-        m_midiChannels[midCh].activenotes_erase(i);
+        m_midiChannels[midCh].activenotes.erase(i);
     }
 }
 
 void MIDIplay::noteUpdateAll(size_t midCh, unsigned props_mask)
 {
-    for(MIDIchannel::activenoteiterator
-        i = m_midiChannels[midCh].activenotes_begin(); i;)
+    for(MIDIchannel::notes_iterator
+        i = m_midiChannels[midCh].activenotes.begin(); !i.is_end();)
     {
-        MIDIchannel::activenoteiterator j(i++);
+        MIDIchannel::notes_iterator j(i++);
         noteUpdate(midCh, j, props_mask);
     }
 }
@@ -1367,7 +1370,7 @@ int64_t MIDIplay::calculateChipChannelGoodness(size_t c, const MIDIchannel::Note
     int64_t s = -koff_ms;
 
     // Rate channel with a releasing note
-    if(s < 0 && chan.users_empty())
+    if(s < 0 && chan.users.empty())
     {
         s -= 40000;
         // If it's same instrument, better chance to get it when no free channels
@@ -1377,31 +1380,34 @@ int64_t MIDIplay::calculateChipChannelGoodness(size_t c, const MIDIchannel::Note
     }
 
     // Same midi-instrument = some stability
-    for(AdlChannel::LocationData *j = chan.users_first; j; j = j->next)
+    for(AdlChannel::const_users_iterator j = chan.users.begin(); !j.is_end(); ++j)
     {
+        const AdlChannel::LocationData &jd = j->value;
         s -= 4000000;
 
-        int64_t kon_ms = j->kon_time_until_neglible_us / 1000;
-        s -= (j->sustained == AdlChannel::LocationData::Sustain_None) ?
+        int64_t kon_ms = jd.kon_time_until_neglible_us / 1000;
+        s -= (jd.sustained == AdlChannel::LocationData::Sustain_None) ?
             kon_ms : (kon_ms / 2);
 
-        MIDIchannel::activenoteiterator
-        k = const_cast<MIDIchannel &>(m_midiChannels[j->loc.MidCh]).activenotes_find(j->loc.note);
+        MIDIchannel::notes_iterator
+        k = const_cast<MIDIchannel &>(m_midiChannels[jd.loc.MidCh]).find_activenote(jd.loc.note);
 
-        if(k)
+        if(!k.is_end())
         {
+            const MIDIchannel::NoteInfo &info = k->value;
+
             // Same instrument = good
-            if(j->ins == ins)
+            if(jd.ins == ins)
             {
                 s += 300;
                 // Arpeggio candidate = even better
-                if(j->vibdelay_us < 70000
-                   || j->kon_time_until_neglible_us > 20000000)
+                if(jd.vibdelay_us < 70000
+                   || jd.kon_time_until_neglible_us > 20000000)
                     s += 10;
             }
 
             // Percussion is inferior to melody
-            s += k->isPercussion ? 50 : 0;
+            s += info.isPercussion ? 50 : 0;
             /*
                     if(k->second.midiins >= 25
                     && k->second.midiins < 40
@@ -1424,11 +1430,12 @@ int64_t MIDIplay::calculateChipChannelGoodness(size_t c, const MIDIchannel::Note
             if(synth.m_channelCategory[c2]
                != synth.m_channelCategory[c]) continue;
 
-            for(AdlChannel::LocationData *m = m_chipChannels[c2].users_first; m; m = m->next)
+            for(AdlChannel::const_users_iterator m = m_chipChannels[c2].users.begin(); !m.is_end(); ++m)
             {
-                if(m->sustained != AdlChannel::LocationData::Sustain_None) continue;
-                if(m->vibdelay_us >= 200000) continue;
-                if(m->ins != j->ins) continue;
+                const AdlChannel::LocationData &md = m->value;
+                if(md.sustained != AdlChannel::LocationData::Sustain_None) continue;
+                if(md.vibdelay_us >= 200000) continue;
+                if(md.ins != jd.ins) continue;
                 n_evacuation_stations += 1;
             }
         }
@@ -1442,27 +1449,28 @@ int64_t MIDIplay::calculateChipChannelGoodness(size_t c, const MIDIchannel::Note
 
 void MIDIplay::prepareChipChannelForNewNote(size_t c, const MIDIchannel::NoteInfo::Phys &ins)
 {
-    if(m_chipChannels[c].users_empty()) return; // Nothing to do
+    if(m_chipChannels[c].users.empty()) return; // Nothing to do
 
     Synth &synth = *m_synth;
 
     //bool doing_arpeggio = false;
-    for(AdlChannel::LocationData *jnext = m_chipChannels[c].users_first; jnext;)
+    for(AdlChannel::users_iterator jnext = m_chipChannels[c].users.begin(); !jnext.is_end();)
     {
-        AdlChannel::LocationData *j = jnext;
-        jnext = jnext->next;
+        AdlChannel::users_iterator j = jnext;
+        AdlChannel::LocationData &jd = jnext->value;
+        ++jnext;
 
-        if(j->sustained == AdlChannel::LocationData::Sustain_None)
+        if(jd.sustained == AdlChannel::LocationData::Sustain_None)
         {
             // Collision: Kill old note,
             // UNLESS we're going to do arpeggio
-            MIDIchannel::activenoteiterator i
-            (m_midiChannels[j->loc.MidCh].activenotes_ensure_find(j->loc.note));
+            MIDIchannel::notes_iterator i
+            (m_midiChannels[jd.loc.MidCh].ensure_find_activenote(jd.loc.note));
 
             // Check if we can do arpeggio.
-            if((j->vibdelay_us < 70000
-                || j->kon_time_until_neglible_us > 20000000)
-               && j->ins == ins)
+            if((jd.vibdelay_us < 70000
+                || jd.kon_time_until_neglible_us > 20000000)
+               && jd.ins == ins)
             {
                 // Do arpeggio together with this note.
                 //doing_arpeggio = true;
@@ -1481,16 +1489,18 @@ void MIDIplay::prepareChipChannelForNewNote(size_t c, const MIDIchannel::NoteInf
 
     // Keyoff the channel so that it can be retriggered,
     // unless the new note will be introduced as just an arpeggio.
-    if(m_chipChannels[c].users_empty())
+    if(m_chipChannels[c].users.empty())
         synth.noteOff(c);
 }
 
 void MIDIplay::killOrEvacuate(size_t from_channel,
-                              AdlChannel::LocationData *j,
-                              MIDIplay::MIDIchannel::activenoteiterator i)
+                              AdlChannel::users_iterator j,
+                              MIDIplay::MIDIchannel::notes_iterator i)
 {
     Synth &synth = *m_synth;
     uint32_t maxChannels = ADL_MAX_CHIPS * 18;
+    AdlChannel::LocationData &jd = j->value;
+    MIDIchannel::NoteInfo &info = i->value;
 
     // Before killing the note, check if it can be
     // evacuated to another channel as an arpeggio
@@ -1509,33 +1519,34 @@ void MIDIplay::killOrEvacuate(size_t from_channel,
             continue;
 
         AdlChannel &adlch = m_chipChannels[c];
-        if(adlch.users_size == AdlChannel::users_max)
+        if(adlch.users.size() == adlch.users.capacity())
             continue;  // no room for more arpeggio on channel
 
-        for(AdlChannel::LocationData *m = adlch.users_first; m; m = m->next)
+        for(AdlChannel::users_iterator m = adlch.users.begin(); !m.is_end(); ++m)
         {
-            if(m->vibdelay_us >= 200000
-               && m->kon_time_until_neglible_us < 10000000) continue;
-            if(m->ins != j->ins)
+            AdlChannel::LocationData &mv = m->value;
+
+            if(mv.vibdelay_us >= 200000
+               && mv.kon_time_until_neglible_us < 10000000) continue;
+            if(mv.ins != jd.ins)
                 continue;
             if(hooks.onNote)
             {
                 hooks.onNote(hooks.onNote_userData,
                              (int)from_channel,
-                             i->noteTone,
-                             static_cast<int>(i->midiins), 0, 0.0);
+                             info.noteTone,
+                             static_cast<int>(info.midiins), 0, 0.0);
                 hooks.onNote(hooks.onNote_userData,
                              (int)c,
-                             i->noteTone,
-                             static_cast<int>(i->midiins),
-                             i->vol, 0.0);
+                             info.noteTone,
+                             static_cast<int>(info.midiins),
+                             info.vol, 0.0);
             }
 
-            i->phys_erase(static_cast<uint16_t>(from_channel));
-            i->phys_ensure_find_or_create(cs)->assign(j->ins);
-            if(!m_chipChannels[cs].users_insert(*j))
-                assert(false);
-            m_chipChannels[from_channel].users_erase(j);
+            info.phys_erase(static_cast<uint16_t>(from_channel));
+            info.phys_ensure_find_or_create(cs)->assign(jd.ins);
+            m_chipChannels[cs].users.push_back(jd);
+            m_chipChannels[from_channel].users.erase(j);
             return;
         }
     }
@@ -1548,7 +1559,7 @@ void MIDIplay::killOrEvacuate(size_t from_channel,
                 ins
                 );*/
     // Kill it
-    noteUpdate(j->loc.MidCh,
+    noteUpdate(jd.loc.MidCh,
                i,
                Upd_Off,
                static_cast<int32_t>(from_channel));
@@ -1576,28 +1587,29 @@ void MIDIplay::killSustainingNotes(int32_t midCh, int32_t this_adlchn, uint32_t
 
     for(uint32_t c = first; c < last; ++c)
     {
-        if(m_chipChannels[c].users_empty())
+        if(m_chipChannels[c].users.empty())
             continue; // Nothing to do
 
-        for(AdlChannel::LocationData *jnext = m_chipChannels[c].users_first; jnext;)
+        for(AdlChannel::users_iterator jnext = m_chipChannels[c].users.begin(); !jnext.is_end();)
         {
-            AdlChannel::LocationData *j = jnext;
-            jnext = jnext->next;
+            AdlChannel::users_iterator j = jnext;
+            AdlChannel::LocationData &jd = j->value;
+            ++jnext;
 
-            if((midCh < 0 || j->loc.MidCh == midCh)
-                && ((j->sustained & sustain_type) != 0))
+            if((midCh < 0 || jd.loc.MidCh == midCh)
+                && ((jd.sustained & sustain_type) != 0))
             {
                 int midiins = '?';
                 if(hooks.onNote)
-                    hooks.onNote(hooks.onNote_userData, (int)c, j->loc.note, midiins, 0, 0.0);
-                j->sustained &= ~sustain_type;
-                if(j->sustained == AdlChannel::LocationData::Sustain_None)
-                    m_chipChannels[c].users_erase(j);//Remove only when note is clean from any holders
+                    hooks.onNote(hooks.onNote_userData, (int)c, jd.loc.note, midiins, 0, 0.0);
+                jd.sustained &= ~sustain_type;
+                if(jd.sustained == AdlChannel::LocationData::Sustain_None)
+                    m_chipChannels[c].users.erase(j);//Remove only when note is clean from any holders
             }
         }
 
         // Keyoff the channel, if there are no users left.
-        if(m_chipChannels[c].users_empty())
+        if(m_chipChannels[c].users.empty())
             synth.noteOff(c);
     }
 }
@@ -1608,15 +1620,16 @@ void MIDIplay::markSostenutoNotes(int32_t midCh)
     uint32_t first = 0, last = synth.m_numChannels;
     for(uint32_t c = first; c < last; ++c)
     {
-        if(m_chipChannels[c].users_empty())
+        if(m_chipChannels[c].users.empty())
             continue; // Nothing to do
 
-        for(AdlChannel::LocationData *jnext = m_chipChannels[c].users_first; jnext;)
+        for(AdlChannel::users_iterator jnext = m_chipChannels[c].users.begin(); !jnext.is_end();)
         {
-            AdlChannel::LocationData *j = jnext;
-            jnext = jnext->next;
-            if((j->loc.MidCh == midCh) && (j->sustained == AdlChannel::LocationData::Sustain_None))
-                j->sustained |= AdlChannel::LocationData::Sustain_Sostenuto;
+            AdlChannel::users_iterator j = jnext;
+            AdlChannel::LocationData &jd = j->value;
+            ++jnext;
+            if((jd.loc.MidCh == midCh) && (jd.sustained == AdlChannel::LocationData::Sustain_None))
+                jd.sustained |= AdlChannel::LocationData::Sustain_Sostenuto;
         }
     }
 }
@@ -1675,9 +1688,9 @@ void MIDIplay::updatePortamento(size_t midCh)
 
 void MIDIplay::noteOff(size_t midCh, uint8_t note)
 {
-    MIDIchannel::activenoteiterator
-    i = m_midiChannels[midCh].activenotes_find(note);
-    if(i)
+    MIDIchannel::notes_iterator
+    i = m_midiChannels[midCh].find_activenote(note);
+    if(!i.is_end())
         noteUpdate(midCh, i, Upd_Off);
 }
 
@@ -1686,7 +1699,7 @@ void MIDIplay::updateVibrato(double amount)
 {
     for(size_t a = 0, b = m_midiChannels.size(); a < b; ++a)
     {
-        if(m_midiChannels[a].hasVibrato() && !m_midiChannels[a].activenotes_empty())
+        if(m_midiChannels[a].hasVibrato() && !m_midiChannels[a].activenotes.empty())
         {
             noteUpdateAll(static_cast<uint16_t>(a), Upd_Pitch);
             m_midiChannels[a].vibpos += amount * m_midiChannels[a].vibspeed;
@@ -1744,11 +1757,11 @@ retry_arpeggio:
         if(c > uint32_t(std::numeric_limits<int32_t>::max()))
             break;
 
-        size_t n_users = m_chipChannels[c].users_size;
+        size_t n_users = m_chipChannels[c].users.size();
 
         if(n_users > 1)
         {
-            AdlChannel::LocationData *i = m_chipChannels[c].users_first;
+            AdlChannel::users_iterator i = m_chipChannels[c].users.begin();
             size_t rate_reduction = 3;
 
             if(n_users >= 3)
@@ -1759,23 +1772,24 @@ retry_arpeggio:
 
             for(size_t count = (m_arpeggioCounter / rate_reduction) % n_users,
                 n = 0; n < count; ++n)
-                i = i->next;
+                ++i;
 
-            if(i->sustained == AdlChannel::LocationData::Sustain_None)
+            AdlChannel::LocationData &d = i->value;
+            if(d.sustained == AdlChannel::LocationData::Sustain_None)
             {
-                if(i->kon_time_until_neglible_us <= 0)
+                if(d.kon_time_until_neglible_us <= 0)
                 {
                     noteUpdate(
-                        i->loc.MidCh,
-                        m_midiChannels[ i->loc.MidCh ].activenotes_ensure_find(i->loc.note),
+                        d.loc.MidCh,
+                        m_midiChannels[ d.loc.MidCh ].ensure_find_activenote(d.loc.note),
                         Upd_Off,
                         static_cast<int32_t>(c));
                     goto retry_arpeggio;
                 }
 
                 noteUpdate(
-                    i->loc.MidCh,
-                    m_midiChannels[ i->loc.MidCh ].activenotes_ensure_find(i->loc.note),
+                    d.loc.MidCh,
+                    m_midiChannels[ d.loc.MidCh ].ensure_find_activenote(d.loc.note),
                     Upd_Pitch | Upd_Volume | Upd_Pan,
                     static_cast<int32_t>(c));
             }
@@ -1793,14 +1807,15 @@ void MIDIplay::updateGlide(double amount)
         if(midiChan.gliding_note_count == 0)
             continue;
 
-        for(MIDIchannel::activenoteiterator it = midiChan.activenotes_begin();
-            it; ++it)
+        for(MIDIchannel::notes_iterator it = midiChan.activenotes.begin();
+            !it.is_end(); ++it)
         {
-            double finalTone = it->noteTone;
-            double previousTone = it->currentTone;
+            MIDIchannel::NoteInfo &info = it->value;
+            double finalTone = info.noteTone;
+            double previousTone = info.currentTone;
 
             bool directionUp = previousTone < finalTone;
-            double toneIncr = amount * (directionUp ? +it->glideRate : -it->glideRate);
+            double toneIncr = amount * (directionUp ? +info.glideRate : -info.glideRate);
 
             double currentTone = previousTone + toneIncr;
             bool glideFinished = !(directionUp ? (currentTone < finalTone) : (currentTone > finalTone));
@@ -1808,7 +1823,7 @@ void MIDIplay::updateGlide(double amount)
 
             if(currentTone != previousTone)
             {
-                it->currentTone = currentTone;
+                info.currentTone = currentTone;
                 noteUpdate(static_cast<uint16_t>(channel), it, Upd_Pitch);
             }
         }
@@ -1828,8 +1843,8 @@ void MIDIplay::describeChannels(char *str, char *attr, size_t size)
     {
         const AdlChannel &adlChannel = m_chipChannels[index];
 
-        AdlChannel::LocationData *loc = adlChannel.users_first;
-        if(!loc)  // off
+        AdlChannel::const_users_iterator loc = adlChannel.users.begin();
+        if(loc.is_end())  // off
         {
             str[index] = '-';
         }
@@ -1855,8 +1870,8 @@ void MIDIplay::describeChannels(char *str, char *attr, size_t size)
         }
 
         uint8_t attribute = 0;
-        if (loc)  // 4-bit color index of MIDI channel
-            attribute |= (uint8_t)(loc->loc.MidCh & 0xF);
+        if (!loc.is_end())  // 4-bit color index of MIDI channel
+            attribute |= (uint8_t)(loc->value.loc.MidCh & 0xF);
 
         attr[index] = (char)attribute;
         ++index;
@@ -2095,129 +2110,3 @@ ADLMIDI_EXPORT bool AdlInstrumentTester::HandleInputChar(char ch)
 }
 
 #endif /* ADLMIDI_DISABLE_CPP_EXTRAS */
-
-// Implement the user map data structure.
-
-bool MIDIplay::AdlChannel::users_empty() const
-{
-    return !users_first;
-}
-
-MIDIplay::AdlChannel::LocationData *MIDIplay::AdlChannel::users_find(Location loc)
-{
-    LocationData *user = NULL;
-    for(LocationData *curr = users_first; !user && curr; curr = curr->next)
-        if(curr->loc == loc)
-            user = curr;
-    return user;
-}
-
-MIDIplay::AdlChannel::LocationData *MIDIplay::AdlChannel::users_allocate()
-{
-    // remove free cells front
-    LocationData *user = users_free_cells;
-    if(!user)
-        return NULL;
-    users_free_cells = user->next;
-    if(users_free_cells)
-        users_free_cells->prev = NULL;
-    // add to users front
-    if(users_first)
-        users_first->prev = user;
-    user->prev = NULL;
-    user->next = users_first;
-    users_first = user;
-    ++users_size;
-    return user;
-}
-
-MIDIplay::AdlChannel::LocationData *MIDIplay::AdlChannel::users_find_or_create(Location loc)
-{
-    LocationData *user = users_find(loc);
-    if(!user)
-    {
-        user = users_allocate();
-        if(!user)
-            return NULL;
-        LocationData *prev = user->prev, *next = user->next;
-        *user = LocationData();
-        user->prev = prev;
-        user->next = next;
-        user->loc = loc;
-    }
-    return user;
-}
-
-MIDIplay::AdlChannel::LocationData *MIDIplay::AdlChannel::users_insert(const LocationData &x)
-{
-    LocationData *user = users_find(x.loc);
-    if(!user)
-    {
-        user = users_allocate();
-        if(!user)
-            return NULL;
-        LocationData *prev = user->prev, *next = user->next;
-        *user = x;
-        user->prev = prev;
-        user->next = next;
-    }
-    return user;
-}
-
-void MIDIplay::AdlChannel::users_erase(LocationData *user)
-{
-    if(user->prev)
-        user->prev->next = user->next;
-    if(user->next)
-        user->next->prev = user->prev;
-    if(user == users_first)
-        users_first = user->next;
-    user->prev = NULL;
-    user->next = users_free_cells;
-    users_free_cells = user;
-    --users_size;
-}
-
-void MIDIplay::AdlChannel::users_clear()
-{
-    users_first = NULL;
-    users_free_cells = users_cells;
-    users_size = 0;
-    for(size_t i = 0; i < users_max; ++i)
-    {
-        users_cells[i].prev = (i > 0) ? &users_cells[i - 1] : NULL;
-        users_cells[i].next = (i + 1 < users_max) ? &users_cells[i + 1] : NULL;
-    }
-}
-
-void MIDIplay::AdlChannel::users_assign(const LocationData *users, size_t count)
-{
-    ADL_UNUSED(count);//Avoid warning for release builds
-    assert(count <= users_max);
-    if(users == users_first && users)
-    {
-        // self assignment
-        assert(users_size == count);
-        return;
-    }
-    users_clear();
-    const LocationData *src_cell = users;
-    // move to the last
-    if(src_cell)
-    {
-        while(src_cell->next)
-            src_cell = src_cell->next;
-    }
-    // push cell copies in reverse order
-    while(src_cell)
-    {
-        LocationData *dst_cell = users_allocate();
-        assert(dst_cell);
-        LocationData *prev = dst_cell->prev, *next = dst_cell->next;
-        *dst_cell = *src_cell;
-        dst_cell->prev = prev;
-        dst_cell->next = next;
-        src_cell = src_cell->prev;
-    }
-    assert(users_size == count);
-}
diff --git a/src/adlmidi_midiplay.hpp b/src/adlmidi_midiplay.hpp
index 02a45a9..f4f0060 100644
--- a/src/adlmidi_midiplay.hpp
+++ b/src/adlmidi_midiplay.hpp
@@ -27,6 +27,7 @@
 #include "adldata.hh"
 #include "adlmidi_private.hpp"
 #include "adlmidi_ptr.hpp"
+#include "structures/pl_list.hpp"
 
 /**
  * @brief Hooks of the internal events
@@ -139,8 +140,6 @@ public:
         {
             //! Note number
             uint8_t note;
-            //! Is note active
-            bool active;
             //! Current pressure
             uint8_t vol;
             //! Note vibrato (a part of Note Aftertouch feature)
@@ -165,6 +164,15 @@ public:
                 MaxNumPhysItemCount = MaxNumPhysChans
             };
 
+            struct FindPredicate
+            {
+                explicit FindPredicate(unsigned note)
+                    : note(note) {}
+                bool operator()(const NoteInfo &ni) const
+                    { return ni.note == note; }
+                unsigned note;
+            };
+
             /**
              * @brief Reference to currently using chip channel
              */
@@ -244,87 +252,38 @@ public:
         unsigned gliding_note_count;
 
         //! Active notes in the channel
-        NoteInfo activenotes[128];
-
-        struct activenoteiterator
-        {
-            explicit activenoteiterator(NoteInfo *info = NULL)
-                : ptr(info) {}
-            activenoteiterator &operator++()
-            {
-                if(ptr->note == 127)
-                    ptr = NULL;
-                else
-                    for(++ptr; ptr && !ptr->active;)
-                        ptr = (ptr->note == 127) ? NULL : (ptr + 1);
-                return *this;
-            }
-            activenoteiterator operator++(int)
-            {
-                activenoteiterator pos = *this;
-                ++*this;
-                return pos;
-            }
-            NoteInfo &operator*() const
-                { return *ptr; }
-            NoteInfo *operator->() const
-                { return ptr; }
-            bool operator==(activenoteiterator other) const
-                { return ptr == other.ptr; }
-            bool operator!=(activenoteiterator other) const
-                { return ptr != other.ptr; }
-            operator NoteInfo *() const
-                { return ptr; }
-        private:
-            NoteInfo *ptr;
-        };
+        pl_list<NoteInfo> activenotes;
+        typedef typename pl_list<NoteInfo>::iterator notes_iterator;
+        typedef typename pl_list<NoteInfo>::const_iterator const_notes_iterator;
 
-        activenoteiterator activenotes_begin()
+        notes_iterator find_activenote(unsigned note)
         {
-            activenoteiterator it(activenotes);
-            return (it->active) ? it : ++it;
+            return activenotes.find_if(NoteInfo::FindPredicate(note));
         }
 
-        activenoteiterator activenotes_find(uint8_t note)
+        notes_iterator ensure_find_activenote(unsigned note)
         {
-            assert(note < 128);
-            return activenoteiterator(
-                activenotes[note].active ? &activenotes[note] : NULL);
-        }
-
-        activenoteiterator activenotes_ensure_find(uint8_t note)
-        {
-            activenoteiterator it = activenotes_find(note);
-            assert(it);
+            notes_iterator it = find_activenote(note);
+            assert(!it.is_end());
             return it;
         }
 
-        std::pair<activenoteiterator, bool> activenotes_insert(uint8_t note)
-        {
-            assert(note < 128);
-            NoteInfo &info = activenotes[note];
-            bool inserted = !info.active;
-            if(inserted) info.active = true;
-            return std::pair<activenoteiterator, bool>(activenoteiterator(&info), inserted);
-        }
-
-        void activenotes_erase(activenoteiterator pos)
-        {
-            if(pos)
-                pos->active = false;
-        }
-
-        bool activenotes_empty()
+        notes_iterator find_or_create_activenote(unsigned note)
         {
-            return !activenotes_begin();
+            notes_iterator it = find_activenote(note);
+            if(it.is_end()) {
+                NoteInfo ni;
+                ni.note = note;
+                it = activenotes.insert(activenotes.end(), ni);
+            }
+            return it;
         }
 
-        void activenotes_clear()
+        notes_iterator ensure_find_or_create_activenote(unsigned note)
         {
-            for(uint8_t i = 0; i < 128; ++i) {
-                activenotes[i].note = i;
-                activenotes[i].active = false;
-            }
+            notes_iterator it = find_or_create_activenote(note);
+            assert(!it.is_end());
+            return it;
         }
 
         /**
@@ -390,8 +349,8 @@ public:
         }
 
         MIDIchannel()
+            : activenotes(128)
         {
-            activenotes_clear();
             gliding_note_count = 0;
             reset();
         }
@@ -413,7 +372,6 @@ public:
         };
         struct LocationData
         {
-            LocationData *prev, *next;
             Location loc;
             enum {
                 Sustain_None        = 0x00,
@@ -429,6 +387,15 @@ public:
             //! Timeout until note will be allowed to be killed by channel manager while it is on
             int64_t kon_time_until_neglible_us;
             int64_t vibdelay_us;
+
+            struct FindPredicate
+            {
+                explicit FindPredicate(Location loc)
+                    : loc(loc) {}
+                bool operator()(const LocationData &ld) const
+                    { return ld.loc == loc; }
+                Location loc;
+            };
         };
 
         //! Time left until sounding will be muted after key off
@@ -437,42 +404,41 @@ public:
         //! Recently passed instrument, improves a goodness of released but busy channel when matching
         MIDIchannel::NoteInfo::Phys recent_ins;
 
-        enum { users_max = 128 };
-        LocationData *users_first, *users_free_cells;
-        LocationData users_cells[users_max];
-        unsigned users_size;
+        pl_list<LocationData> users;
+        typedef typename pl_list<LocationData>::iterator users_iterator;
+        typedef typename pl_list<LocationData>::const_iterator const_users_iterator;
+
+        users_iterator find_user(const Location &loc)
+        {
+            return users.find_if(LocationData::FindPredicate(loc));
+        }
 
-        bool users_empty() const;
-        LocationData *users_find(Location loc);
-        LocationData *users_allocate();
-        LocationData *users_find_or_create(Location loc);
-        LocationData *users_insert(const LocationData &x);
-        void users_erase(LocationData *user);
-        void users_clear();
-        void users_assign(const LocationData *users, size_t count);
+        users_iterator find_or_create_user(const Location &loc)
+        {
+            users_iterator it = find_user(loc);
+            if(it.is_end() && users.size() != users.capacity())
+            {
+                LocationData ld;
+                ld.loc = loc;
+                it = users.insert(users.end(), ld);
+            }
+            return it;
+        }
 
         // For channel allocation:
-        AdlChannel(): koff_time_until_neglible_us(0)
+        AdlChannel(): koff_time_until_neglible_us(0), users(128)
         {
-            users_clear();
             std::memset(&recent_ins, 0, sizeof(MIDIchannel::NoteInfo::Phys));
         }
 
-        AdlChannel(const AdlChannel &oth): koff_time_until_neglible_us(oth.koff_time_until_neglible_us)
+        AdlChannel(const AdlChannel &oth): koff_time_until_neglible_us(oth.koff_time_until_neglible_us), users(oth.users)
         {
-            if(oth.users_first)
-            {
-                users_first = NULL;
-                users_assign(oth.users_first, oth.users_size);
-            }
-            else
-                users_clear();
         }
 
         AdlChannel &operator=(const AdlChannel &oth)
         {
             koff_time_until_neglible_us = oth.koff_time_until_neglible_us;
-            users_assign(oth.users_first, oth.users_size);
+            users = oth.users;
             return *this;
         }
 
@@ -899,7 +865,7 @@ private:
      * @param select_adlchn Specify chip channel, or -1 - all chip channels used by the note
      */
     void noteUpdate(size_t midCh,
-                    MIDIchannel::activenoteiterator i,
+                    MIDIchannel::notes_iterator i,
                     unsigned props_mask,
                     int32_t select_adlchn = -1);
 
@@ -934,8 +900,8 @@ private:
      */
     void killOrEvacuate(
         size_t  from_channel,
-        AdlChannel::LocationData *j,
-        MIDIchannel::activenoteiterator i);
+        AdlChannel::users_iterator j,
+        MIDIchannel::notes_iterator i);
 
     /**
      * @brief Off all notes and silence sound
diff --git a/src/structures/pl_list.hpp b/src/structures/pl_list.hpp
new file mode 100644
index 0000000..0cbd233
--- /dev/null
+++ b/src/structures/pl_list.hpp
@@ -0,0 +1,133 @@
+//          Copyright Jean Pierre Cimalando 2018.
+// Distributed under the Boost Software License, Version 1.0.
+//    (See accompanying file LICENSE or copy at
+//          http://www.boost.org/LICENSE_1_0.txt)
+
+#ifndef PL_LIST_HPP
+#define PL_LIST_HPP
+
+#include <iterator>
+#include <cstddef>
+
+/*
+  pl_cell: the linked list cell
+ */
+template <class T>
+struct pl_cell;
+
+template <class T>
+struct pl_basic_cell
+{
+    pl_cell<T> *prev, *next;
+};
+
+template <class T>
+struct pl_cell : pl_basic_cell<T>
+{
+    T value;
+};
+
+/*
+  pl_iterator: the linked list iterator
+ */
+template <class Cell>
+class pl_iterator
+{
+public:
+    typedef std::bidirectional_iterator_tag iterator_category;
+    typedef Cell value_type;
+    typedef Cell &reference;
+    typedef Cell *pointer;
+    typedef std::ptrdiff_t difference_type;
+
+    pl_iterator(Cell *cell = NULL);
+    bool is_end() const;
+    Cell &operator*() const;
+    Cell *operator->() const;
+    bool operator==(const pl_iterator &i) const;
+    bool operator!=(const pl_iterator &i) const;
+    pl_iterator &operator++();
+    pl_iterator operator++(int);
+    pl_iterator &operator--();
+    pl_iterator operator--(int);
+
+private:
+    Cell *cell_;
+};
+
+/*
+  pl_list: the preallocated linked list
+ */
+template <class T>
+class pl_list
+{
+public:
+    typedef pl_cell<T> value_type;
+    typedef value_type *pointer;
+    typedef value_type &reference;
+    typedef const value_type *const_pointer;
+    typedef const value_type &const_reference;
+    typedef pl_iterator< pl_cell<T> > iterator;
+    typedef pl_iterator< const pl_cell<T> > const_iterator;
+
+    pl_list(std::size_t capacity = 0);
+    ~pl_list();
+
+    struct external_storage_policy {};
+    pl_list(pl_cell<T> *cells, std::size_t ncells, external_storage_policy);
+
+    pl_list(const pl_list &other);
+    pl_list &operator=(const pl_list &other);
+
+    std::size_t size() const;
+    std::size_t capacity() const;
+    bool empty() const;
+
+    iterator begin();
+    iterator end();
+    const_iterator begin() const;
+    const_iterator end() const;
+
+    void clear();
+
+    pl_cell<T> &front();
+    const pl_cell<T> &front() const;
+    pl_cell<T> &back();
+    const pl_cell<T> &back() const;
+
+    iterator insert(iterator pos, const T &x);
+    iterator erase(iterator pos);
+    void push_front(const T &x);
+    void push_back(const T &x);
+    void pop_front();
+    void pop_back();
+
+    iterator find(const T &x);
+    const_iterator find(const T &x) const;
+    template <class Pred> iterator find_if(const Pred &p);
+    template <class Pred> const_iterator find_if(const Pred &p) const;
+
+private:
+    // number of cells in the list
+    std::size_t size_;
+    // number of cells allocated
+    std::size_t capacity_;
+    // array of cells allocated
+    pl_cell<T> *cells_;
+    // pointer to the head cell
+    pl_cell<T> *first_;
+    // pointer to the next free cell
+    pl_cell<T> *free_;
+    // value-less cell which terminates the linked list
+    pl_basic_cell<T> endcell_;
+    // whether cell storage is allocated
+    bool cells_allocd_;
+
+    void initialize(std::size_t capacity, pl_cell<T> *extcells = NULL);
+    pl_cell<T> *allocate(pl_cell<T> *pos);
+    void deallocate(pl_cell<T> *cell);
+};
+
+#include "pl_list.tcc"
+
+#endif // PL_LIST_HPP
diff --git a/src/structures/pl_list.tcc b/src/structures/pl_list.tcc
new file mode 100644
index 0000000..959b085
--- /dev/null
+++ b/src/structures/pl_list.tcc
@@ -0,0 +1,338 @@
+//          Copyright Jean Pierre Cimalando 2018.
+// Distributed under the Boost Software License, Version 1.0.
+//    (See accompanying file LICENSE or copy at
+//          http://www.boost.org/LICENSE_1_0.txt)
+
+#include "pl_list.hpp"
+
+template <class Cell>
+pl_iterator<Cell>::pl_iterator(Cell *cell)
+    : cell_(cell)
+{
+}
+
+template <class Cell>
+bool pl_iterator<Cell>::is_end() const
+{
+    return cell_->next == NULL;
+}
+
+template <class Cell>
+Cell &pl_iterator<Cell>::operator*() const
+{
+    return *cell_;
+}
+
+template <class Cell>
+Cell *pl_iterator<Cell>::operator->() const
+{
+    return cell_;
+}
+
+template <class T>
+bool pl_iterator<T>::operator==(const pl_iterator &i) const
+{
+    return cell_ == i.cell_;
+}
+
+template <class T>
+bool pl_iterator<T>::operator!=(const pl_iterator &i) const
+{
+    return cell_ != i.cell_;
+}
+
+template <class T>
+pl_iterator<T> &pl_iterator<T>::operator++()
+{
+    cell_ = cell_->next;
+    return *this;
+}
+
+template <class T>
+pl_iterator<T> pl_iterator<T>::operator++(int)
+{
+    pl_iterator i(cell_);
+    cell_ = cell_->next;
+    return i;
+}
+
+template <class T>
+pl_iterator<T> &pl_iterator<T>::operator--()
+{
+    cell_ = cell_->prev;
+    return *this;
+}
+
+template <class T>
+pl_iterator<T> pl_iterator<T>::operator--(int)
+{
+    pl_iterator i(cell_);
+    cell_ = cell_->prev;
+    return i;
+}
+
+template <class T>
+pl_list<T>::pl_list(std::size_t capacity)
+{
+    initialize(capacity);
+}
+
+template <class T>
+pl_list<T>::~pl_list()
+{
+    if (cells_allocd_)
+        delete[] cells_;
+}
+
+template <class T>
+pl_list<T>::pl_list(pl_cell<T> *cells, std::size_t ncells, external_storage_policy)
+{
+    initialize(ncells, cells);
+}
+
+template <class T>
+pl_list<T>::pl_list(const pl_list &other)
+{
+    initialize(other.capacity());
+    for(const_iterator i = other.end(), b = other.begin(); i-- != b;)
+        push_front(i->value);
+}
+
+template <class T>
+pl_list<T> &pl_list<T>::operator=(const pl_list &other)
+{
+    if(this != &other)
+    {
+        std::size_t size = other.size();
+        if(size > capacity())
+        {
+            pl_cell<T> *oldcells = cells_;
+            bool allocd = cells_allocd_;
+            initialize(other.capacity());
+            if (allocd)
+                delete[] oldcells;
+        }
+        clear();
+        for(const_iterator i = other.end(), b = other.begin(); i-- != b;)
+            push_front(i->value);
+    }
+    return *this;
+}
+
+template <class T>
+std::size_t pl_list<T>::size() const
+{
+    return size_;
+}
+
+template <class T>
+std::size_t pl_list<T>::capacity() const
+{
+    return capacity_;
+}
+
+template <class T>
+bool pl_list<T>::empty() const
+{
+    return size_ == 0;
+}
+
+template <class T>
+typename pl_list<T>::iterator pl_list<T>::begin()
+{
+    return iterator(first_);
+}
+
+template <class T>
+typename pl_list<T>::iterator pl_list<T>::end()
+{
+    return iterator(reinterpret_cast<pl_cell<T> *>(&endcell_));
+}
+
+template <class T>
+typename pl_list<T>::const_iterator pl_list<T>::begin() const
+{
+    return const_iterator(first_);
+}
+
+template <class T>
+typename pl_list<T>::const_iterator pl_list<T>::end() const
+{
+    return const_iterator(reinterpret_cast<const pl_cell<T> *>(&endcell_));
+}
+
+template <class T>
+void pl_list<T>::clear()
+{
+    std::size_t capacity = capacity_;
+    pl_cell<T> *cells = cells_;
+    pl_cell<T> *endcell = &*end();
+    size_ = 0;
+    first_ = endcell;
+    free_ = cells;
+    endcell->prev = NULL;
+    for(std::size_t i = 0; i < capacity; ++i)
+    {
+        cells[i].prev = (i > 0) ? &cells[i - 1] : NULL;
+        cells[i].next = (i + 1 < capacity) ? &cells[i + 1] : NULL;
+        cells[i].value = T();
+    }
+}
+
+template <class T>
+pl_cell<T> &pl_list<T>::front()
+{
+    return *first_;
+}
+
+template <class T>
+const pl_cell<T> &pl_list<T>::front() const
+{
+    return *first_;
+}
+
+template <class T>
+pl_cell<T> &pl_list<T>::back()
+{
+    iterator i = end();
+    return *--i;
+}
+
+template <class T>
+const pl_cell<T> &pl_list<T>::back() const
+{
+    const_iterator i = end();
+    return *--i;
+}
+
+template <class T>
+typename pl_list<T>::iterator pl_list<T>::insert(iterator pos, const T &x)
+{
+    pl_cell<T> *cell = allocate(&*pos);
+    if (!cell)
+        throw std::bad_alloc();
+    cell->value = x;
+    return iterator(cell);
+}
+
+template <class T>
+typename pl_list<T>::iterator pl_list<T>::erase(iterator pos)
+{
+    deallocate(&*(pos++));
+    return pos;
+}
+
+template <class T>
+void pl_list<T>::push_front(const T &x)
+{
+    insert(begin(), x);
+}
+
+template <class T>
+void pl_list<T>::push_back(const T &x)
+{
+    insert(end(), x);
+}
+
+template <class T>
+void pl_list<T>::pop_front()
+{
+    deallocate(first_);
+}
+
+template <class T>
+void pl_list<T>::pop_back()
+{
+    iterator i(&*end());
+    deallocate(&*--i);
+}
+
+template <class T>
+typename pl_list<T>::iterator pl_list<T>::find(const T &x)
+{
+    const_iterator i = const_cast<const pl_list<T> *>(this)->find(x);
+    return iterator(&const_cast<reference>(*i));
+}
+
+template <class T>
+typename pl_list<T>::const_iterator pl_list<T>::find(const T &x) const
+{
+    const_iterator e = end();
+    for (const_iterator i = begin(); i != e; ++i)
+    {
+        if(i->value == x)
+            return i;
+    }
+    return e;
+}
+
+template <class T>
+template <class Pred>
+typename pl_list<T>::iterator pl_list<T>::find_if(const Pred &p)
+{
+    const_iterator i = const_cast<const pl_list<T> *>(this)->find_if(p);
+    return iterator(&const_cast<reference>(*i));
+}
+
+template <class T>
+template <class Pred>
+typename pl_list<T>::const_iterator pl_list<T>::find_if(const Pred &p) const
+{
+    const_iterator e = end();
+    for (const_iterator i = begin(); i != e; ++i)
+    {
+        if(p(i->value))
+            return i;
+    }
+    return e;
+}
+
+template <class T>
+void pl_list<T>::initialize(std::size_t capacity, pl_cell<T> *extcells)
+{
+    cells_ = extcells ? extcells : new pl_cell<T>[capacity];
+    cells_allocd_ = extcells ? false : true;
+    capacity_ = capacity;
+    endcell_.next = NULL;
+    clear();
+}
+
+template <class T>
+pl_cell<T> *pl_list<T>::allocate(pl_cell<T> *pos)
+{
+    // remove free cells front
+    pl_cell<T> *cell = free_;
+    if(!cell)
+        return NULL;
+    free_ = cell->next;
+    if(free_)
+        free_->prev = NULL;
+
+    // insert at position
+    if (pos == first_)
+        first_ = cell;
+    cell->prev = pos->prev;
+    if (cell->prev)
+        cell->prev->next = cell;
+    cell->next = pos;
+    pos->prev = cell;
+
+    ++size_;
+    return cell;
+}
+
+template <class T>
+void pl_list<T>::deallocate(pl_cell<T> *cell)
+{
+    if(cell->prev)
+        cell->prev->next = cell->next;
+    if(cell->next)
+        cell->next->prev = cell->prev;
+    if(cell == first_)
+        first_ = cell->next;
+    cell->prev = NULL;
+    cell->next = free_;
+    cell->value = T();
+    free_ = cell;
+    --size_;
+}