hard-RT: elimination of the user map

2 files changed, 169 insertions, 95 deletions

diff --git a/src/adlmidi_midiplay.cpp b/src/adlmidi_midiplay.cpp
index 80f36ce..d984fe1 100644
--- a/src/adlmidi_midiplay.cpp
+++ b/src/adlmidi_midiplay.cpp
@@ -117,18 +117,18 @@ inline bool isXgPercChannel(uint8_t msb, uint8_t lsb)
 
 void MIDIplay::AdlChannel::AddAge(int64_t ms)
 {
-    if(users.empty())
+    if(users_empty())
         koff_time_until_neglible =
             std::max(int64_t(koff_time_until_neglible - ms), static_cast<int64_t>(-0x1FFFFFFFl));
     else
     {
         koff_time_until_neglible = 0;
 
-        for(users_t::iterator i = users.begin(); i != users.end(); ++i)
+        for(LocationData *i = users_first; i; i = i->next)
         {
-            i->second.kon_time_until_neglible =
-                std::max(i->second.kon_time_until_neglible - ms, static_cast<int64_t>(-0x1FFFFFFFl));
-            i->second.vibdelay += ms;
+            i->kon_time_until_neglible =
+                std::max(i->kon_time_until_neglible - ms, static_cast<int64_t>(-0x1FFFFFFFl));
+            i->vibdelay += ms;
         }
     }
 }
@@ -1455,11 +1455,13 @@ void MIDIplay::NoteUpdate(uint16_t MidCh,
         if(props_mask & Upd_Patch)
         {
             opl.Patch(c, ins.insId);
-            AdlChannel::LocationData &d = ch[c].users[my_loc];
-            d.sustained = false; // inserts if necessary
-            d.vibdelay  = 0;
-            d.kon_time_until_neglible = ains.ms_sound_kon;
-            d.ins       = ins;
+            AdlChannel::LocationData *d = ch[c].users_find_or_create(my_loc);
+            if(d) {  // inserts if necessary
+                d->sustained = false;
+                d->vibdelay  = 0;
+                d->kon_time_until_neglible = ains.ms_sound_kon;
+                d->ins       = ins;
+            }
         }
     }
 
@@ -1475,15 +1477,15 @@ void MIDIplay::NoteUpdate(uint16_t MidCh,
         {
             if(Ch[MidCh].sustain == 0)
             {
-                AdlChannel::users_t::iterator k = ch[c].users.find(my_loc);
+                AdlChannel::LocationData *k = ch[c].users_find(my_loc);
 
-                if(k != ch[c].users.end())
-                    ch[c].users.erase(k);
+                if(k)
+                    ch[c].users_erase(k);
 
                 if(hooks.onNote)
                     hooks.onNote(hooks.onNote_userData, c, tone, midiins, 0, 0.0);
 
-                if(ch[c].users.empty())
+                if(ch[c].users_empty())
                 {
                     opl.NoteOff(c);
                     if(props_mask & Upd_Mute) // Mute the note
@@ -1499,8 +1501,9 @@ void MIDIplay::NoteUpdate(uint16_t MidCh,
             {
                 // Sustain: Forget about the note, but don't key it off.
                 //          Also will avoid overwriting it very soon.
-                AdlChannel::LocationData &d = ch[c].users[my_loc];
-                d.sustained = true; // note: not erased!
+                AdlChannel::LocationData *d = ch[c].users_find_or_create(my_loc);
+                if(d)
+                    d->sustained = true; // note: not erased!
                 if(hooks.onNote)
                     hooks.onNote(hooks.onNote_userData, c, tone, midiins, -1, 0.0);
             }
@@ -1602,10 +1605,10 @@ void MIDIplay::NoteUpdate(uint16_t MidCh,
 
         if(props_mask & Upd_Pitch)
         {
-            AdlChannel::LocationData &d = ch[c].users[my_loc];
+            AdlChannel::LocationData *d = ch[c].users_find(my_loc);
 
             // Don't bend a sustained note
-            if(!d.sustained)
+            if(!d || !d->sustained)
             {
                 double bend = Ch[MidCh].bend + opl.GetAdlIns(ins.insId).finetune;
                 double phase = 0.0;
@@ -1615,7 +1618,7 @@ void MIDIplay::NoteUpdate(uint16_t MidCh,
                     phase = ains.voice2_fine_tune;//0.125; // Detune the note slightly (this is what Doom does)
                 }
 
-                if(Ch[MidCh].vibrato && d.vibdelay >= Ch[MidCh].vibdelay)
+                if(Ch[MidCh].vibrato && d->vibdelay >= Ch[MidCh].vibdelay)
                     bend += Ch[MidCh].vibrato * Ch[MidCh].vibdepth * std::sin(Ch[MidCh].vibpos);
 
                 #ifdef ADLMIDI_USE_DOSBOX_OPL
@@ -2130,30 +2133,27 @@ int64_t MIDIplay::CalculateAdlChannelGoodness(unsigned c, const MIDIchannel::Not
 
     // Same midi-instrument = some stability
     //if(c == MidCh) s += 4;
-    for(AdlChannel::users_t::const_iterator
-        j = ch[c].users.begin();
-        j != ch[c].users.end();
-        ++j)
+    for (AdlChannel::LocationData *j = ch[c].users_first; j; j = j->next)
     {
         s -= 4000;
 
-        if(!j->second.sustained)
-            s -= j->second.kon_time_until_neglible;
+        if(!j->sustained)
+            s -= j->kon_time_until_neglible;
         else
-            s -= (j->second.kon_time_until_neglible / 2);
+            s -= (j->kon_time_until_neglible / 2);
 
         MIDIchannel::activenoteiterator
-        k = const_cast<MIDIchannel &>(Ch[j->first.MidCh]).activenotes_find(j->first.note);
+        k = const_cast<MIDIchannel &>(Ch[j->loc.MidCh]).activenotes_find(j->loc.note);
 
         if(k)
         {
             // Same instrument = good
-            if(j->second.ins == ins)
+            if(j->ins == ins)
             {
                 s += 300;
                 // Arpeggio candidate = even better
-                if(j->second.vibdelay < 70
-                   || j->second.kon_time_until_neglible > 20000)
+                if(j->vibdelay < 70
+                   || j->kon_time_until_neglible > 20000)
                     s += 0;
             }
 
@@ -2181,14 +2181,11 @@ int64_t MIDIplay::CalculateAdlChannelGoodness(unsigned c, const MIDIchannel::Not
             if(opl.four_op_category[c2]
                != opl.four_op_category[c]) continue;
 
-            for(AdlChannel::users_t::const_iterator
-                m = ch[c2].users.begin();
-                m != ch[c2].users.end();
-                ++m)
+            for(AdlChannel::LocationData *m = ch[c2].users_first; m; m = m->next)
             {
-                if(m->second.sustained)       continue;
-                if(m->second.vibdelay >= 200) continue;
-                if(m->second.ins != j->second.ins) continue;
+                if(m->sustained)       continue;
+                if(m->vibdelay >= 200) continue;
+                if(m->ins != j->ins) continue;
                 n_evacuation_stations += 1;
             }
         }
@@ -2202,27 +2199,25 @@ int64_t MIDIplay::CalculateAdlChannelGoodness(unsigned c, const MIDIchannel::Not
 
 void MIDIplay::PrepareAdlChannelForNewNote(size_t c, const MIDIchannel::NoteInfo::Phys &ins)
 {
-    if(ch[c].users.empty()) return; // Nothing to do
+    if(ch[c].users_empty()) return; // Nothing to do
 
     //bool doing_arpeggio = false;
-    for(AdlChannel::users_t::iterator
-        jnext = ch[c].users.begin();
-        jnext != ch[c].users.end();
-       )
+    for(AdlChannel::LocationData *jnext = ch[c].users_first; jnext;)
     {
-        AdlChannel::users_t::iterator j(jnext++);
+        AdlChannel::LocationData *j = jnext;
+        jnext = jnext->next;
 
-        if(!j->second.sustained)
+        if(!j->sustained)
         {
             // Collision: Kill old note,
             // UNLESS we're going to do arpeggio
             MIDIchannel::activenoteiterator i
-            (Ch[j->first.MidCh].activenotes_ensure_find(j->first.note));
+            (Ch[j->loc.MidCh].activenotes_ensure_find(j->loc.note));
 
             // Check if we can do arpeggio.
-            if((j->second.vibdelay < 70
-                || j->second.kon_time_until_neglible > 20000)
-               && j->second.ins == ins)
+            if((j->vibdelay < 70
+                || j->kon_time_until_neglible > 20000)
+               && j->ins == ins)
             {
                 // Do arpeggio together with this note.
                 //doing_arpeggio = true;
@@ -2241,12 +2236,12 @@ void MIDIplay::PrepareAdlChannelForNewNote(size_t c, const MIDIchannel::NoteInfo
 
     // Keyoff the channel so that it can be retriggered,
     // unless the new note will be introduced as just an arpeggio.
-    if(ch[c].users.empty())
+    if(ch[c].users_empty())
         opl.NoteOff(c);
 }
 
 void MIDIplay::KillOrEvacuate(size_t from_channel,
-                              AdlChannel::users_t::iterator j,
+                              AdlChannel::LocationData *j,
                               MIDIplay::MIDIchannel::activenoteiterator i)
 {
     // Before killing the note, check if it can be
@@ -2265,14 +2260,15 @@ void MIDIplay::KillOrEvacuate(size_t from_channel,
         if(opl.four_op_category[c] != opl.four_op_category[from_channel])
             continue;
 
-        for(AdlChannel::users_t::iterator
-            m = ch[c].users.begin();
-            m != ch[c].users.end();
-            ++m)
+        AdlChannel &adlch = ch[c];
+        if(adlch.users_size == AdlChannel::users_max)
+            continue;  // no room for more arpeggio on channel
+
+        for(AdlChannel::LocationData *m = adlch.users_first; m; m = m->next)
         {
-            if(m->second.vibdelay >= 200
-               && m->second.kon_time_until_neglible < 10000) continue;
-            if(m->second.ins != j->second.ins)
+            if(m->vibdelay >= 200
+               && m->kon_time_until_neglible < 10000) continue;
+            if(m->ins != j->ins)
                 continue;
             if(hooks.onNote)
             {
@@ -2288,9 +2284,10 @@ void MIDIplay::KillOrEvacuate(size_t from_channel,
             }
 
             i->phys_erase(static_cast<uint16_t>(from_channel));
-            i->phys_ensure_find_or_create(cs)->assign(j->second.ins);
-            ch[cs].users.insert(*j);
-            ch[from_channel].users.erase(j);
+            i->phys_ensure_find_or_create(cs)->assign(j->ins);
+            if(!ch[cs].users_insert(*j))
+                assert(false);
+            ch[from_channel].users_erase(j);
             return;
         }
     }
@@ -2303,7 +2300,7 @@ void MIDIplay::KillOrEvacuate(size_t from_channel,
                 ins
                 );*/
     // Kill it
-    NoteUpdate(j->first.MidCh,
+    NoteUpdate(j->loc.MidCh,
                i,
                Upd_Off,
                static_cast<int32_t>(from_channel));
@@ -2330,27 +2327,25 @@ void MIDIplay::KillSustainingNotes(int32_t MidCh, int32_t this_adlchn)
 
     for(unsigned c = first; c < last; ++c)
     {
-        if(ch[c].users.empty()) continue; // Nothing to do
+        if(ch[c].users_empty()) continue; // Nothing to do
 
-        for(AdlChannel::users_t::iterator
-            jnext = ch[c].users.begin();
-            jnext != ch[c].users.end();
-           )
+        for(AdlChannel::LocationData *jnext = ch[c].users_first; jnext;)
         {
-            AdlChannel::users_t::iterator j(jnext++);
+            AdlChannel::LocationData *j = jnext;
+            jnext = jnext->next;
 
-            if((MidCh < 0 || j->first.MidCh == MidCh)
-               && j->second.sustained)
+            if((MidCh < 0 || j->loc.MidCh == MidCh)
+               && j->sustained)
             {
                 int midiins = '?';
                 if(hooks.onNote)
-                    hooks.onNote(hooks.onNote_userData, (int)c, j->first.note, midiins, 0, 0.0);
-                ch[c].users.erase(j);
+                    hooks.onNote(hooks.onNote_userData, (int)c, j->loc.note, midiins, 0, 0.0);
+                ch[c].users_erase(j);
             }
         }
 
         // Keyoff the channel, if there are no users left.
-        if(ch[c].users.empty())
+        if(ch[c].users_empty())
             opl.NoteOff(c);
     }
 }
@@ -2485,11 +2480,11 @@ retry_arpeggio:
         if(c > uint32_t(std::numeric_limits<int32_t>::max()))
             break;
 
-        size_t n_users = ch[c].users.size();
+        size_t n_users = ch[c].users_size;
 
         if(n_users > 1)
         {
-            AdlChannel::users_t::const_iterator i = ch[c].users.begin();
+            AdlChannel::LocationData *i = ch[c].users_first;
             size_t rate_reduction = 3;
 
             if(n_users >= 3)
@@ -2498,23 +2493,25 @@ retry_arpeggio:
             if(n_users >= 4)
                 rate_reduction = 1;
 
-            std::advance(i, (arpeggio_counter / rate_reduction) % n_users);
+            for(unsigned count = (arpeggio_counter / rate_reduction) % n_users,
+                     n = 0; n < count; ++n)
+                i = i->next;
 
-            if(i->second.sustained == false)
+            if(i->sustained == false)
             {
-                if(i->second.kon_time_until_neglible <= 0l)
+                if(i->kon_time_until_neglible <= 0l)
                 {
                     NoteUpdate(
-                        i->first.MidCh,
-                        Ch[ i->first.MidCh ].activenotes_ensure_find(i->first.note),
+                        i->loc.MidCh,
+                        Ch[ i->loc.MidCh ].activenotes_ensure_find(i->loc.note),
                         Upd_Off,
                         static_cast<int32_t>(c));
                     goto retry_arpeggio;
                 }
 
                 NoteUpdate(
-                    i->first.MidCh,
-                    Ch[ i->first.MidCh ].activenotes_ensure_find(i->first.note),
+                    i->loc.MidCh,
+                    Ch[ i->loc.MidCh ].activenotes_ensure_find(i->loc.note),
                     Upd_Pitch | Upd_Volume | Upd_Pan,
                     static_cast<int32_t>(c));
             }
diff --git a/src/adlmidi_private.hpp b/src/adlmidi_private.hpp
index 69a833c..f6eea5a 100644
--- a/src/adlmidi_private.hpp
+++ b/src/adlmidi_private.hpp
@@ -803,36 +803,113 @@ public:
     // Additional information about OPL3 channels
     struct AdlChannel
     {
-        // For collisions
         struct Location
         {
             uint16_t    MidCh;
             uint8_t     note;
-            bool operator==(const Location &b) const
-            {
-                return MidCh == b.MidCh && note == b.note;
-            }
-            bool operator< (const Location &b) const
-            {
-                return MidCh < b.MidCh || (MidCh == b.MidCh && note < b.note);
-            }
-            char ____padding[1];
+            bool operator==(const Location &l) const
+                { return MidCh == l.MidCh && note == l.note; }
+            bool operator!=(const Location &l) const
+                { return !operator==(l); }
         };
         struct LocationData
         {
+            LocationData *prev, *next;
+            Location loc;
             bool sustained;
             char ____padding[7];
             MIDIchannel::NoteInfo::Phys ins;  // a copy of that in phys[]
             int64_t kon_time_until_neglible;
             int64_t vibdelay;
         };
-        typedef std::map<Location, LocationData> users_t;
-        users_t users;
 
         // If the channel is keyoff'd
         int64_t koff_time_until_neglible;
+
+        enum { users_max = 128 };
+        LocationData *users_first, *users_free_cells;
+        LocationData users_cells[users_max];
+        unsigned users_size;
+
+        bool users_empty() const
+            { return !users_first; }
+        LocationData *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;
+        }
+        LocationData *users_allocate()
+        {
+            // remove free cells front
+            LocationData *user = users_free_cells;
+            if(!user)
+                return NULL;
+            users_free_cells = user->next;
+            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;
+        }
+        LocationData *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;
+        }
+        LocationData *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 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;
+        }
+
         // For channel allocation:
-        AdlChannel(): users(), koff_time_until_neglible(0) { }
+        AdlChannel(): koff_time_until_neglible(0), users_first(NULL), users_size(0)
+        {
+            users_free_cells = users_cells;
+            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 AddAge(int64_t ms);
     };
 
@@ -1230,7 +1307,7 @@ private:
 
     void KillOrEvacuate(
         size_t  from_channel,
-        AdlChannel::users_t::iterator j,
+        AdlChannel::LocationData *j,
         MIDIchannel::activenoteiterator i);
     void Panic();
     void KillSustainingNotes(int32_t MidCh = -1, int32_t this_adlchn = -1);