From 298160f0154a05030681a208a247e2ed309f89db Mon Sep 17 00:00:00 2001 From: JP Cimalando Date: Sat, 10 Nov 2018 16:59:35 +0100 Subject: linked list structure + users --- src/adlmidi_midiplay.cpp | 306 +++++++++++++---------------------------- src/adlmidi_midiplay.hpp | 58 ++++---- src/structures/pl_list.hpp | 128 ++++++++++++++++++ src/structures/pl_list.tcc | 329 +++++++++++++++++++++++++++++++++++++++++++++ 4 files changed, 585 insertions(+), 236 deletions(-) create mode 100644 src/structures/pl_list.hpp create mode 100644 src/structures/pl_list.tcc (limited to 'src') diff --git a/src/adlmidi_midiplay.cpp b/src/adlmidi_midiplay.cpp index 1a20e9e..62c7ee3 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(-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; } } } @@ -1147,14 +1148,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(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(adlNoteOnMaxTime)); + d.kon_time_until_neglible_us = 1000 * ains.ms_sound_kon; + d.ins = ins; } } } @@ -1172,15 +1174,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 +1200,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,10 +1304,10 @@ 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)) { double midibend = m_midiChannels[midCh].bend * m_midiChannels[midCh].bendsense; double bend = midibend + ins.ains.finetune; @@ -1318,7 +1320,7 @@ void MIDIplay::noteUpdate(size_t midCh, phase = ains.voice2_fine_tune;//0.125; // Detune the note slightly (this is what Doom does) } - if(vibrato && (!d || d->vibdelay_us >= m_midiChannels[midCh].vibdelay_us)) + if(vibrato && (d.is_end() || d->value.vibdelay_us >= m_midiChannels[midCh].vibdelay_us)) bend += static_cast(vibrato) * m_midiChannels[midCh].vibdepth * std::sin(m_midiChannels[midCh].vibpos); #define BEND_COEFFICIENT 172.4387 @@ -1366,7 +1368,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 @@ -1376,26 +1378,27 @@ 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(m_midiChannels[j->loc.MidCh]).activenotes_find(j->loc.note); + k = const_cast(m_midiChannels[jd.loc.MidCh]).activenotes_find(jd.loc.note); if(k) { // 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; } @@ -1423,11 +1426,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; } } @@ -1441,27 +1445,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)); + (m_midiChannels[jd.loc.MidCh].activenotes_ensure_find(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; @@ -1480,16 +1485,17 @@ 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, + AdlChannel::users_iterator j, MIDIplay::MIDIchannel::activenoteiterator i) { Synth &synth = *m_synth; uint32_t maxChannels = ADL_MAX_CHIPS * 18; + AdlChannel::LocationData &jd = j->value; // Before killing the note, check if it can be // evacuated to another channel as an arpeggio @@ -1508,14 +1514,16 @@ 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) { @@ -1531,10 +1539,9 @@ void MIDIplay::killOrEvacuate(size_t from_channel, } i->phys_erase(static_cast(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); + i->phys_ensure_find_or_create(cs)->assign(jd.ins); + m_chipChannels[cs].users.push_back(jd); + m_chipChannels[from_channel].users.erase(j); return; } } @@ -1547,7 +1554,7 @@ void MIDIplay::killOrEvacuate(size_t from_channel, ins );*/ // Kill it - noteUpdate(j->loc.MidCh, + noteUpdate(jd.loc.MidCh, i, Upd_Off, static_cast(from_channel)); @@ -1575,28 +1582,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); } } @@ -1607,15 +1615,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; } } } @@ -1743,11 +1752,11 @@ retry_arpeggio: if(c > uint32_t(std::numeric_limits::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) @@ -1758,23 +1767,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 ].activenotes_ensure_find(d.loc.note), Upd_Off, static_cast(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 ].activenotes_ensure_find(d.loc.note), Upd_Pitch | Upd_Volume | Upd_Pan, static_cast(c)); } @@ -1827,8 +1837,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] = '-'; } @@ -1854,8 +1864,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; @@ -2094,129 +2104,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..d16d851 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 @@ -413,7 +414,6 @@ public: }; struct LocationData { - LocationData *prev, *next; Location loc; enum { Sustain_None = 0x00, @@ -429,6 +429,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 + { + 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 +446,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 users; + typedef typename pl_list::iterator users_iterator; + typedef typename pl_list::const_iterator const_users_iterator; - 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_user(const Location &loc) + { + return users.find_if(LocationData::FindPredicate(loc)); + } + + 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; } @@ -934,7 +942,7 @@ private: */ void killOrEvacuate( size_t from_channel, - AdlChannel::LocationData *j, + AdlChannel::users_iterator j, MIDIchannel::activenoteiterator i); /** diff --git a/src/structures/pl_list.hpp b/src/structures/pl_list.hpp new file mode 100644 index 0000000..327e259 --- /dev/null +++ b/src/structures/pl_list.hpp @@ -0,0 +1,128 @@ +// 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 +#include + +/* + pl_cell: the linked list cell + */ +template +struct pl_cell; + +template +struct pl_basic_cell +{ + pl_cell *prev, *next; +}; + +template +struct pl_cell : pl_basic_cell +{ + T value; +}; + +/* + pl_iterator: the linked list iterator + */ +template +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 pl_list +{ +public: + typedef pl_cell 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 > iterator; + typedef pl_iterator< const pl_cell > const_iterator; + + pl_list(std::size_t capacity = 0); + ~pl_list(); + + 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 &front(); + const pl_cell &front() const; + pl_cell &back(); + const pl_cell &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 iterator find_if(const Pred &p); + template 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 *cells_; + // pointer to the head cell + pl_cell *first_; + // pointer to the next free cell + pl_cell *free_; + // value-less cell which terminates the linked list + pl_basic_cell endcell_; + + void initialize(std::size_t capacity); + pl_cell *allocate(pl_cell *pos); + void deallocate(pl_cell *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..37ccc75 --- /dev/null +++ b/src/structures/pl_list.tcc @@ -0,0 +1,329 @@ +// 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 +pl_iterator::pl_iterator(Cell *cell) + : cell_(cell) +{ +} + +template +bool pl_iterator::is_end() const +{ + return cell_->next == NULL; +} + +template +Cell &pl_iterator::operator*() const +{ + return *cell_; +} + +template +Cell *pl_iterator::operator->() const +{ + return cell_; +} + +template +bool pl_iterator::operator==(const pl_iterator &i) const +{ + return cell_ == i.cell_; +} + +template +bool pl_iterator::operator!=(const pl_iterator &i) const +{ + return cell_ != i.cell_; +} + +template +pl_iterator &pl_iterator::operator++() +{ + cell_ = cell_->next; + return *this; +} + +template +pl_iterator pl_iterator::operator++(int) +{ + pl_iterator i(cell_); + cell_ = cell_->next; + return i; +} + +template +pl_iterator &pl_iterator::operator--() +{ + cell_ = cell_->prev; + return *this; +} + +template +pl_iterator pl_iterator::operator--(int) +{ + pl_iterator i(cell_); + cell_ = cell_->prev; + return i; +} + +template +pl_list::pl_list(std::size_t capacity) +{ + initialize(capacity); +} + +template +pl_list::~pl_list() +{ + delete[] cells_; +} + +template +pl_list::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 +pl_list &pl_list::operator=(const pl_list &other) +{ + if(this != &other) + { + std::size_t size = other.size(); + if(size <= capacity()) + clear(); + else + { + pl_cell *oldcells = cells_; + initialize(other.capacity()); + delete[] oldcells; + } + for(const_iterator i = other.end(), b = other.begin(); i-- != b;) + push_front(i->value); + } + return *this; +} + +template +std::size_t pl_list::size() const +{ + return size_; +} + +template +std::size_t pl_list::capacity() const +{ + return capacity_; +} + +template +bool pl_list::empty() const +{ + return size_ == 0; +} + +template +typename pl_list::iterator pl_list::begin() +{ + return iterator(first_); +} + +template +typename pl_list::iterator pl_list::end() +{ + return iterator(reinterpret_cast *>(&endcell_)); +} + +template +typename pl_list::const_iterator pl_list::begin() const +{ + return const_iterator(first_); +} + +template +typename pl_list::const_iterator pl_list::end() const +{ + return const_iterator(reinterpret_cast *>(&endcell_)); +} + +template +void pl_list::clear() +{ + std::size_t capacity = capacity_; + pl_cell *cells = cells_; + pl_cell *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 +pl_cell &pl_list::front() +{ + return *first_; +} + +template +const pl_cell &pl_list::front() const +{ + return *first_; +} + +template +pl_cell &pl_list::back() +{ + iterator i = end(); + return *--i; +} + +template +const pl_cell &pl_list::back() const +{ + const_iterator i = end(); + return *--i; +} + +template +typename pl_list::iterator pl_list::insert(iterator pos, const T &x) +{ + pl_cell *cell = allocate(&*pos); + if (!cell) + throw std::bad_alloc(); + cell->value = x; + return iterator(cell); +} + +template +typename pl_list::iterator pl_list::erase(iterator pos) +{ + deallocate(&*(pos++)); + return pos; +} + +template +void pl_list::push_front(const T &x) +{ + insert(begin(), x); +} + +template +void pl_list::push_back(const T &x) +{ + insert(end(), x); +} + +template +void pl_list::pop_front() +{ + deallocate(first_); +} + +template +void pl_list::pop_back() +{ + iterator i(&*end()); + deallocate(&*--i); +} + +template +typename pl_list::iterator pl_list::find(const T &x) +{ + const_iterator i = const_cast *>(this)->find(x); + return iterator(&const_cast(*i)); +} + +template +typename pl_list::const_iterator pl_list::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 +template +typename pl_list::iterator pl_list::find_if(const Pred &p) +{ + const_iterator i = const_cast *>(this)->find_if(p); + return iterator(&const_cast(*i)); +} + +template +template +typename pl_list::const_iterator pl_list::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 +void pl_list::initialize(std::size_t capacity) +{ + cells_ = new pl_cell[capacity]; + capacity_ = capacity; + endcell_.next = NULL; + clear(); +} + +template +pl_cell *pl_list::allocate(pl_cell *pos) +{ + // remove free cells front + pl_cell *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 +void pl_list::deallocate(pl_cell *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_; +} -- cgit v1.2.3