From 5fdd39289affe341151839a48e227d51b08c4a25 Mon Sep 17 00:00:00 2001 From: JP Cimalando Date: Tue, 15 May 2018 18:09:04 +0200 Subject: specialized hash table for bank number mappings --- src/adlmidi_bankmap.tcc | 253 ++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 253 insertions(+) create mode 100644 src/adlmidi_bankmap.tcc (limited to 'src/adlmidi_bankmap.tcc') diff --git a/src/adlmidi_bankmap.tcc b/src/adlmidi_bankmap.tcc new file mode 100644 index 0000000..e049fc6 --- /dev/null +++ b/src/adlmidi_bankmap.tcc @@ -0,0 +1,253 @@ +/* + * libADLMIDI is a free MIDI to WAV conversion library with OPL3 emulation + * + * Original ADLMIDI code: Copyright (c) 2010-2014 Joel Yliluoma + * ADLMIDI Library API: Copyright (c) 2015-2018 Vitaly Novichkov + * + * Library is based on the ADLMIDI, a MIDI player for Linux and Windows with OPL3 emulation: + * http://iki.fi/bisqwit/source/adlmidi.html + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see . + */ + +#include "adlmidi_bankmap.h" +#include + +template +inline BasicBankMap::BasicBankMap() +{ + m_buckets.reset(new Slot *[hash_buckets]()); +} + +template +inline size_t BasicBankMap::hash(key_type key) +{ + // disregard the 0 high bit in LSB + key = (key & 127) | ((key >> 8) << 7); + // take low part as hash value + return key & (hash_buckets - 1); +} + +template +void BasicBankMap::reserve(size_t capacity) +{ + if(m_capacity >= capacity) + return; + + size_t need = capacity - m_capacity; + need = (need < minimum_allocation) ? minimum_allocation : need; + + Slot *slots = new Slot[need]; + m_allocations.push_back(std::unique_ptr(slots)); + m_capacity += need; + + for(size_t i = need; i-- > 0;) + free_slot(&slots[i]); +} + +template +typename BasicBankMap::iterator +BasicBankMap::begin() const +{ + iterator it(m_buckets.get(), nullptr, 0); + while(it.index < hash_buckets && !(it.slot = m_buckets[it.index])) + ++it.index; + return it; +} + +template +typename BasicBankMap::iterator +BasicBankMap::end() const +{ + iterator it(m_buckets.get(), nullptr, hash_buckets); + return it; +} + +template +typename BasicBankMap::iterator BasicBankMap::find(key_type key) +{ + size_t index = hash(key); + Slot *slot = bucket_find(index, key); + if(!slot) + return end(); + return iterator(m_buckets.get(), slot, index); +} + +template +void BasicBankMap::erase(iterator it) +{ + bucket_remove(it.index, it.slot); + free_slot(it.slot); + --m_size; +} + +template +BasicBankMap::iterator::iterator(Slot **buckets, Slot *slot, size_t index) + : buckets(buckets), slot(slot), index(index) +{ +} + +template +typename BasicBankMap::iterator & +BasicBankMap::iterator::operator++() +{ + if(slot->next) + slot = slot->next; + else { + Slot *slot = nullptr; + ++index; + while(index < hash_buckets && !(slot = buckets[index])) + ++index; + this->slot = slot; + } + return *this; +} + +template +bool BasicBankMap::iterator::operator==(const iterator &o) const +{ + return buckets == o.buckets && slot == o.slot && index == o.index; +} + +template +inline bool BasicBankMap::iterator::operator!=(const iterator &o) const +{ + return !operator==(o); +} + +template +std::pair::iterator, bool> +BasicBankMap::insert(const value_type &value) +{ + size_t index = hash(value.first); + Slot *slot = bucket_find(index, value.first); + if(slot) + return {iterator(m_buckets.get(), slot, index), false}; + slot = allocate_slot(); + if(!slot) { + reserve(m_capacity + minimum_allocation); + slot = ensure_allocate_slot(); + } + slot->value = value; + bucket_add(index, slot); + ++m_size; + return {iterator(m_buckets.get(), slot, index), true}; +} + +template +std::pair::iterator, bool> +BasicBankMap::insert(const value_type &value, do_not_expand_t) +{ + size_t index = hash(value.first); + Slot *slot = bucket_find(index, value.first); + if(slot) + return {iterator(m_buckets.get(), slot, index), false}; + slot = allocate_slot(); + if(!slot) + return {end(), false}; + slot->value = value; + bucket_add(index, slot); + ++m_size; + return {iterator(m_buckets.get(), slot, index), true}; +} + +template +void BasicBankMap::clear() +{ + for(size_t i = 0; i < hash_buckets; ++i) { + Slot *slot = m_buckets[i]; + while (Slot *cur = slot) { + slot = slot->next; + free_slot(cur); + } + m_buckets[i] = nullptr; + } + m_size = 0; +} + +template +inline T &BasicBankMap::operator[](key_type key) +{ + return insert({key, T()}).first->second; +} + +template +typename BasicBankMap::Slot * +BasicBankMap::allocate_slot() +{ + Slot *slot = m_freeslots; + if(!slot) + return nullptr; + Slot *next = slot->next; + if(next) + next->prev = nullptr; + m_freeslots = next; + return slot; +} + +template +inline typename BasicBankMap::Slot * +BasicBankMap::ensure_allocate_slot() +{ + Slot *slot = allocate_slot(); + assert(slot); + return slot; +} + +template +void BasicBankMap::free_slot(Slot *slot) +{ + Slot *next = m_freeslots; + if(next) + next->prev = slot; + slot->prev = nullptr; + slot->next = next; + m_freeslots = slot; + m_freeslots->value.second = T(); +} + +template +typename BasicBankMap::Slot * +BasicBankMap::bucket_find(size_t index, key_type key) +{ + Slot *slot = m_buckets[index]; + while(slot && slot->value.first != key) + slot = slot->next; + return slot; +} + +template +void BasicBankMap::bucket_add(size_t index, Slot *slot) +{ + assert(slot); + Slot *next = m_buckets[index]; + if(next) + next->prev = slot; + slot->next = next; + m_buckets[index] = slot; +} + +template +void BasicBankMap::bucket_remove(size_t index, Slot *slot) +{ + assert(slot); + Slot *prev = slot->prev; + Slot *next = slot->next; + if(!prev) + m_buckets[index] = next; + else + prev->next = next; + if(next) + next->prev = prev; +} -- cgit v1.2.3 From 8cce88f8706ca6fb52592458aa12641c43469a6e Mon Sep 17 00:00:00 2001 From: JP Cimalando Date: Wed, 16 May 2018 03:27:07 +0200 Subject: c++98 support for bank map --- src/adlmidi_bankmap.tcc | 56 +++++++++++++++++++++++++++++-------------------- 1 file changed, 33 insertions(+), 23 deletions(-) (limited to 'src/adlmidi_bankmap.tcc') diff --git a/src/adlmidi_bankmap.tcc b/src/adlmidi_bankmap.tcc index e049fc6..0387418 100644 --- a/src/adlmidi_bankmap.tcc +++ b/src/adlmidi_bankmap.tcc @@ -26,6 +26,9 @@ template inline BasicBankMap::BasicBankMap() + : m_freeslots(NULL), + m_size(0), + m_capacity(0) { m_buckets.reset(new Slot *[hash_buckets]()); } @@ -48,20 +51,21 @@ void BasicBankMap::reserve(size_t capacity) size_t need = capacity - m_capacity; need = (need < minimum_allocation) ? minimum_allocation : need; - Slot *slots = new Slot[need]; - m_allocations.push_back(std::unique_ptr(slots)); + AdlMIDI_SPtrArray slots; + slots.reset(new Slot[need]); + m_allocations.push_back(slots); m_capacity += need; for(size_t i = need; i-- > 0;) - free_slot(&slots[i]); + free_slot(&slots.get()[i]); } template typename BasicBankMap::iterator BasicBankMap::begin() const { - iterator it(m_buckets.get(), nullptr, 0); - while(it.index < hash_buckets && !(it.slot = m_buckets[it.index])) + iterator it(m_buckets.get(), NULL, 0); + while(it.index < hash_buckets && !(it.slot = m_buckets.get()[it.index])) ++it.index; return it; } @@ -70,7 +74,7 @@ template typename BasicBankMap::iterator BasicBankMap::end() const { - iterator it(m_buckets.get(), nullptr, hash_buckets); + iterator it(m_buckets.get(), NULL, hash_buckets); return it; } @@ -93,7 +97,13 @@ void BasicBankMap::erase(iterator it) } template -BasicBankMap::iterator::iterator(Slot **buckets, Slot *slot, size_t index) +inline BasicBankMap::iterator::iterator() + : buckets(NULL), slot(NULL), index(0) +{ +} + +template +inline BasicBankMap::iterator::iterator(Slot **buckets, Slot *slot, size_t index) : buckets(buckets), slot(slot), index(index) { } @@ -105,7 +115,7 @@ BasicBankMap::iterator::operator++() if(slot->next) slot = slot->next; else { - Slot *slot = nullptr; + Slot *slot = NULL; ++index; while(index < hash_buckets && !(slot = buckets[index])) ++index; @@ -133,7 +143,7 @@ BasicBankMap::insert(const value_type &value) size_t index = hash(value.first); Slot *slot = bucket_find(index, value.first); if(slot) - return {iterator(m_buckets.get(), slot, index), false}; + return std::make_pair(iterator(m_buckets.get(), slot, index), false); slot = allocate_slot(); if(!slot) { reserve(m_capacity + minimum_allocation); @@ -142,7 +152,7 @@ BasicBankMap::insert(const value_type &value) slot->value = value; bucket_add(index, slot); ++m_size; - return {iterator(m_buckets.get(), slot, index), true}; + return std::make_pair(iterator(m_buckets.get(), slot, index), true); } template @@ -152,26 +162,26 @@ BasicBankMap::insert(const value_type &value, do_not_expand_t) size_t index = hash(value.first); Slot *slot = bucket_find(index, value.first); if(slot) - return {iterator(m_buckets.get(), slot, index), false}; + return std::make_pair(iterator(m_buckets.get(), slot, index), false); slot = allocate_slot(); if(!slot) - return {end(), false}; + return std::make_pair(end(), false); slot->value = value; bucket_add(index, slot); ++m_size; - return {iterator(m_buckets.get(), slot, index), true}; + return std::make_pair(iterator(m_buckets.get(), slot, index), true); } template void BasicBankMap::clear() { for(size_t i = 0; i < hash_buckets; ++i) { - Slot *slot = m_buckets[i]; + Slot *slot = m_buckets.get()[i]; while (Slot *cur = slot) { slot = slot->next; free_slot(cur); } - m_buckets[i] = nullptr; + m_buckets.get()[i] = NULL; } m_size = 0; } @@ -179,7 +189,7 @@ void BasicBankMap::clear() template inline T &BasicBankMap::operator[](key_type key) { - return insert({key, T()}).first->second; + return insert(value_type(key, T())).first->second; } template @@ -188,10 +198,10 @@ BasicBankMap::allocate_slot() { Slot *slot = m_freeslots; if(!slot) - return nullptr; + return NULL; Slot *next = slot->next; if(next) - next->prev = nullptr; + next->prev = NULL; m_freeslots = next; return slot; } @@ -211,7 +221,7 @@ void BasicBankMap::free_slot(Slot *slot) Slot *next = m_freeslots; if(next) next->prev = slot; - slot->prev = nullptr; + slot->prev = NULL; slot->next = next; m_freeslots = slot; m_freeslots->value.second = T(); @@ -221,7 +231,7 @@ template typename BasicBankMap::Slot * BasicBankMap::bucket_find(size_t index, key_type key) { - Slot *slot = m_buckets[index]; + Slot *slot = m_buckets.get()[index]; while(slot && slot->value.first != key) slot = slot->next; return slot; @@ -231,11 +241,11 @@ template void BasicBankMap::bucket_add(size_t index, Slot *slot) { assert(slot); - Slot *next = m_buckets[index]; + Slot *next = m_buckets.get()[index]; if(next) next->prev = slot; slot->next = next; - m_buckets[index] = slot; + m_buckets.get()[index] = slot; } template @@ -245,7 +255,7 @@ void BasicBankMap::bucket_remove(size_t index, Slot *slot) Slot *prev = slot->prev; Slot *next = slot->next; if(!prev) - m_buckets[index] = next; + m_buckets.get()[index] = next; else prev->next = next; if(next) -- cgit v1.2.3 From 5b6ec1a766ae922f898a942eade2841a828c0ed0 Mon Sep 17 00:00:00 2001 From: JP Cimalando Date: Wed, 16 May 2018 18:27:43 +0200 Subject: smart pointers cleanup --- src/adlmidi_bankmap.tcc | 16 ++++++++-------- 1 file changed, 8 insertions(+), 8 deletions(-) (limited to 'src/adlmidi_bankmap.tcc') diff --git a/src/adlmidi_bankmap.tcc b/src/adlmidi_bankmap.tcc index 0387418..938192d 100644 --- a/src/adlmidi_bankmap.tcc +++ b/src/adlmidi_bankmap.tcc @@ -57,7 +57,7 @@ void BasicBankMap::reserve(size_t capacity) m_capacity += need; for(size_t i = need; i-- > 0;) - free_slot(&slots.get()[i]); + free_slot(&slots[i]); } template @@ -65,7 +65,7 @@ typename BasicBankMap::iterator BasicBankMap::begin() const { iterator it(m_buckets.get(), NULL, 0); - while(it.index < hash_buckets && !(it.slot = m_buckets.get()[it.index])) + while(it.index < hash_buckets && !(it.slot = m_buckets[it.index])) ++it.index; return it; } @@ -176,12 +176,12 @@ template void BasicBankMap::clear() { for(size_t i = 0; i < hash_buckets; ++i) { - Slot *slot = m_buckets.get()[i]; + Slot *slot = m_buckets[i]; while (Slot *cur = slot) { slot = slot->next; free_slot(cur); } - m_buckets.get()[i] = NULL; + m_buckets[i] = NULL; } m_size = 0; } @@ -231,7 +231,7 @@ template typename BasicBankMap::Slot * BasicBankMap::bucket_find(size_t index, key_type key) { - Slot *slot = m_buckets.get()[index]; + Slot *slot = m_buckets[index]; while(slot && slot->value.first != key) slot = slot->next; return slot; @@ -241,11 +241,11 @@ template void BasicBankMap::bucket_add(size_t index, Slot *slot) { assert(slot); - Slot *next = m_buckets.get()[index]; + Slot *next = m_buckets[index]; if(next) next->prev = slot; slot->next = next; - m_buckets.get()[index] = slot; + m_buckets[index] = slot; } template @@ -255,7 +255,7 @@ void BasicBankMap::bucket_remove(size_t index, Slot *slot) Slot *prev = slot->prev; Slot *next = slot->next; if(!prev) - m_buckets.get()[index] = next; + m_buckets[index] = next; else prev->next = next; if(next) -- cgit v1.2.3 From d7b9439df5d09d121c55a15f2bc25c360deeebe0 Mon Sep 17 00:00:00 2001 From: JP Cimalando Date: Thu, 17 May 2018 21:33:28 +0200 Subject: dynamic instrument API --- src/adlmidi_bankmap.tcc | 19 +++++++++++++++++++ 1 file changed, 19 insertions(+) (limited to 'src/adlmidi_bankmap.tcc') diff --git a/src/adlmidi_bankmap.tcc b/src/adlmidi_bankmap.tcc index 938192d..9303f0d 100644 --- a/src/adlmidi_bankmap.tcc +++ b/src/adlmidi_bankmap.tcc @@ -136,6 +136,25 @@ inline bool BasicBankMap::iterator::operator!=(const iterator &o) const return !operator==(o); } +template +void BasicBankMap::iterator::to_ptrs(void *ptrs[3]) +{ + ptrs[0] = buckets; + ptrs[1] = slot; + ptrs[2] = (void *)index; +} + +template +typename BasicBankMap::iterator +BasicBankMap::iterator::from_ptrs(void *const ptrs[3]) +{ + iterator it; + it.buckets = (Slot **)ptrs[0]; + it.slot = (Slot *)ptrs[1]; + it.index = (size_t)ptrs[2]; + return it; +} + template std::pair::iterator, bool> BasicBankMap::insert(const value_type &value) -- cgit v1.2.3 From 4cfba5ee6a404e71c3d7b86b7b1ec680c3d7521d Mon Sep 17 00:00:00 2001 From: Wohlstand Date: Sun, 3 Jun 2018 14:34:21 +0300 Subject: Fixed some warnings on MinGW --- src/adlmidi_bankmap.tcc | 11 ++++++----- 1 file changed, 6 insertions(+), 5 deletions(-) (limited to 'src/adlmidi_bankmap.tcc') diff --git a/src/adlmidi_bankmap.tcc b/src/adlmidi_bankmap.tcc index 9303f0d..76e7001 100644 --- a/src/adlmidi_bankmap.tcc +++ b/src/adlmidi_bankmap.tcc @@ -49,15 +49,16 @@ void BasicBankMap::reserve(size_t capacity) return; size_t need = capacity - m_capacity; - need = (need < minimum_allocation) ? minimum_allocation : need; + const size_t minalloc = static_cast(minimum_allocation); + need = (need < minalloc) ? minalloc : need; - AdlMIDI_SPtrArray slots; - slots.reset(new Slot[need]); - m_allocations.push_back(slots); + AdlMIDI_SPtrArray slotz; + slotz.reset(new Slot[need]); + m_allocations.push_back(slotz); m_capacity += need; for(size_t i = need; i-- > 0;) - free_slot(&slots[i]); + free_slot(&slotz[i]); } template -- cgit v1.2.3