1
\$\begingroup\$

I was trying to implement a queue implementing the small size optimization. I was wondering any ways I can make this code better (more performant, better code style, etc). It seems to work fine (in terms of correctness).

For reference, Global::specifyError is my error handling mechanism for the project, Global's allocate is right now just implemented with new.

Thank you!

Code:

#ifndef QUEUE_HPP
#define QUEUE_HPP

#include "Error.h"
#include "Allocator.h"
#include <cstddef>
#include <algorithm>

namespace Utils {
    template<typename T>
    class Queue {
        private:
            static const int FLAG_POS = (sizeof(size_t)*8)-1;
            static const size_t FLAG_SFT = 1ULL << FLAG_POS;
            static const size_t MAX_CAPACITY = (1ULL << FLAG_POS-1)-1;
        protected:
            T* start;
            size_t _front;
            size_t _back;
            size_t length;
            size_t capacity; // bit manipulation to encode stack/heap.
            
            Queue(T* st, size_t f, size_t b, size_t l, size_t c){
                if(__builtin_expect(c > MAX_CAPACITY,false)){
                    Global::specifyError("Queue requested more than 1 << sizeof(size_t)-2 capacity.");
                    throw Global::MemoryRequestError;
                }
                _front = f;
                _back = b;
                start = st;
                length = l;
                capacity = c;
            }
            ~Queue(){
            }
        public:
            // no code reuse with Vector, too many different things.
            void push_back(T val){
                const bool heap = capacity>>FLAG_POS;
                const bool leqc = (length&FLAG_SFT-1) >0 && _front == _back;
                enum:char {STACK_PUSH, STACK_MOVE_HEAP, HEAP_PUSH, HEAP_GROW};
                
                switch((heap<<1)+leqc){
                    case STACK_MOVE_HEAP:
                    case HEAP_GROW:
                    {
                        if(__builtin_expect(length*2 > MAX_CAPACITY,false)){
                            Global::specifyError("Vector requested more than (1 << sizeof(size_t)-2)-1 capacity.");
                            throw Global::MemoryRequestError;
                        }
                        T* aux = Global::getAllocator()->allocate<T>(length*2);
                        std::copy(start+_front, start+capacity, aux);
                        std::copy(start, start+_back, aux+capacity-_front);
                        capacity = FLAG_SFT+length*2;
                        if(__builtin_expect((heap<<1)+leqc==HEAP_GROW,true)){
                            Global::getAllocator()->deallocate<T>(start);
                        }
                        start = aux;
                        _front = 0;
                        _back = length;
                    }
                    case STACK_PUSH:
                    case HEAP_PUSH:
                        ++length;
                        start[_back++] = val;
                        _back &= capacity-1;
                        break;
                    // no default case.
                }
            }
            void pop_front(){
                --length;
                ++_front;
                _front &= capacity-1;
            }
            int size() const {
                return length;
            }
            T front() const {
                return start[_front];
            }
    };
      
    /*based on Chandler Carruth's talk at CppCon 2016 */
    /** Type T, threshold for stack allocation N.*/
    
    template<typename T, size_t N>
    class SmallQueue : public Queue<T> {
        private:
            static constexpr size_t nextPow2(const size_t curr){
                size_t s = curr;
                --s;
                s |= s >> 1;
                s |= s >> 2;
                s |= s >> 4;
                s |= s >> 8;
                return s+1;
            }
            // should get replaced with literal value.
            T buffer[nextPow2(N)];
        public:
            SmallQueue() : Queue<T> (buffer, 0, 0, 0, nextPow2(N)) {
            }
            ~SmallQueue(){
                if(this->capacity > nextPow2(N)){
                    Global::getAllocator()->deallocate<T>(this->start);
                }
            }
    };
}

#endif

Code where it is used (a BFS)

void Expr::print(const int width, std::ostream& out){
    /* some code */
    Utils::SmallQueue<QueueItem,100> queue;
    QueueItem inp = {this,0,0};
    queue.push_back(inp);
    
    int currHeight = -1;
    int currJustif = 0;
    
    while(queue.size() > 0) {
        QueueItem obj = queue.front();
        //std::cerr << "xJust: " << obj.xJust << "h: " << obj.height << '\n';
        queue.pop_front();
        /* more code */
```
\$\endgroup\$
3
  • 1
    \$\begingroup\$ Can you please add any unit test code you have so that we can see how the queue is used. This helps us provide a better code review. \$\endgroup\$
    – pacmaninbw
    Jul 4, 2020 at 23:06
  • 1
    \$\begingroup\$ Hi, I don't have any unit test code, I just have the code where it's being used. I'll post that on the question. Thank you \$\endgroup\$
    – Mihir Shah
    Jul 5, 2020 at 1:50
  • 1
    \$\begingroup\$ This is not a "small size optimization" like you get with std::string(), instead you are implementing a queue that does static allocation (as in, it does not dynamically allocate memory from the heap), so that it can live completely on the stack. \$\endgroup\$
    – G. Sliepen
    Jul 5, 2020 at 15:15

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.