template<typename T, typename _Alloc = allocator<T>>
class vector
{
    
};

enum { _ALIGN = 8 };
enum { _MAX_BYTES = 128 };
enum { _NFREELISTS = 16 };

union _Obj
{
    union _Obj* _M_free_list_link;
    char _M_client_data[1];
};

static _Obj* __STL_VOLATILE _S_free_list[_NFREELISTS];

  static void* allocate(size_t __n)
  {
    void* __ret = 0;

    if (__n > (size_t) _MAX_BYTES)
    {
      __ret = malloc_alloc::allocate(__n);
    }
    else  // 核心代码
    {
        // 返回 freelist 的某下标的指针（二级指针）
      _Obj* __STL_VOLATILE* __my_free_list
          = _S_free_list + _S_freelist_index(__n);
      // Acquire the lock here with a constructor call.
      // This ensures that it is released in exit or during stack
      // unwinding.
      
#     ifndef _NOTHREADS
      /*REFERENCED*/
      _Lock __lock_instance;
#     endif
        // 去看 freelist 这个下标，有没有已开辟且由空闲的块
      _Obj* __RESTRICT __result = *__my_free_list;
      if (__result == nullptr)  // 没有空闲块，或者没开辟。
      {
        __ret = _S_refill(_S_round_up(__n));
      }
      else                      // 有空闲块。
      {
          // 让 这个下标 指向下一块空闲块。（见_Obj联合体定义）
        *__my_free_list = __result -> _M_free_list_link;
          // 返回的是 __result 这个空闲块
        __ret = __result;
      }
    }
    return __ret;
  };

static  size_t _S_freelist_index(size_t __bytes)
{
    return (__bytes + (size_t)_ALIGN - 1 ) / (size_t)_ALIGN      - 1;
}

static size_t
_S_round_up(size_t __bytes) 
{
    return (__bytes + (size_t)_ALIGN - 1) & ~((size_t)_ALIGN - 1);
}

/* Returns an object of size __n, and optionally adds to size __n free list.*/
/* We assume that __n is properly aligned.                                */
/* We hold the allocation lock.                                         */
template <bool __threads, int __inst>
void*
__default_alloc_template<__threads, __inst>::_S_refill(size_t __n)
{
    int __nobjs = 20;
    char* __chunk = _S_chunk_alloc(__n, __nobjs);
    
    _Obj* __STL_VOLATILE* __my_free_list;
    _Obj* __result;
    _Obj* __current_obj;
    _Obj* __next_obj;
    int __i;

    if (1 == __nobjs) return(__chunk);
    
    __my_free_list = _S_free_list + _S_freelist_index(__n);

    /* Build free list in chunk */
    __result = (_Obj*)__chunk;
    *__my_free_list = __next_obj = (_Obj*)(__chunk + __n);
    for (__i = 1; ; __i++)
    {
        __current_obj = __next_obj;
        __next_obj = (_Obj*)((char*)__next_obj + __n);
        if (__nobjs - 1 == __i)
        {
            __current_obj -> _M_free_list_link = 0;
            break;
        }
        else
        {
            __current_obj -> _M_free_list_link = __next_obj;
        }
    }
    return(__result);
}

/* We allocate memory in large chunks in order to avoid fragmenting     */
/* the malloc heap too much.                                            */
/* We assume that size is properly aligned.                             */
/* We hold the allocation lock.                                         */
template <bool __threads, int __inst>
char*
__default_alloc_template<__threads, __inst>::_S_chunk_alloc(size_t __size, 
                                                            int& __nobjs)
{
    char* __result;
    size_t __total_bytes = __size * __nobjs;
    size_t __bytes_left = _S_end_free - _S_start_free;

    if (__bytes_left >= __total_bytes)
    {
        __result = _S_start_free;
        _S_start_free += __total_bytes;
        return(__result);
    }
    else if (__bytes_left >= __size)
    {
        __nobjs = (int)(__bytes_left / __size);
        __total_bytes = __size * __nobjs;
        __result = _S_start_free;
        _S_start_free += __total_bytes;
        return(__result);
    }
    else
    {
        size_t __bytes_to_get = 2 * __total_bytes + _S_round_up(_S_heap_size >> 4);
        // Try to make use of the left-over piece.
        if (__bytes_left > 0)
        {
            _Obj* __STL_VOLATILE* __my_free_list =
                        _S_free_list + _S_freelist_index(__bytes_left);

            ((_Obj*)_S_start_free) -> _M_free_list_link = *__my_free_list;
            *__my_free_list = (_Obj*)_S_start_free;
        }
        _S_start_free = (char*)malloc(__bytes_to_get);
        if (0 == _S_start_free)
        {
            size_t __i;
            _Obj* __STL_VOLATILE* __my_free_list;
            _Obj* __p;
            // Try to make do with what we have.  That can't
            // hurt.  We do not try smaller requests, since that tends
            // to result in disaster on multi-process machines.
            for (__i = __size; __i <= (size_t) _MAX_BYTES; __i += (size_t) _ALIGN)
            {
                __my_free_list = _S_free_list + _S_freelist_index(__i);
                __p = *__my_free_list;
                if (0 != __p)
                {
                    *__my_free_list = __p -> _M_free_list_link;
                    _S_start_free = (char*)__p;
                    _S_end_free = _S_start_free + __i;
                    return(_S_chunk_alloc(__size, __nobjs));
                    // Any leftover piece will eventually make it to the
                    // right free list.
                }
            }
            _S_end_free = 0;	// In case of exception.
            _S_start_free = (char*)malloc_alloc::allocate(__bytes_to_get);
            // This should either throw an
            // exception or remedy the situation.  Thus we assume it
            // succeeded.
        }
        _S_heap_size += __bytes_to_get;
        _S_end_free = _S_start_free + __bytes_to_get;
        return(_S_chunk_alloc(__size, __nobjs));
    }
}

template <int __inst>
class __malloc_alloc_template
{
private:
#ifndef __STL_STATIC_TEMPLATE_MEMBER_BUG
  static void (* __malloc_alloc_oom_handler)();
#endif
public:
  static void* allocate(size_t __n)
  {
    void* __result = malloc(__n);
    if (0 == __result)
    {
        __result = _S_oom_malloc(__n);
    }
    return __result;
  }
  // ...
};

template <int __inst>
void*
__malloc_alloc_template<__inst>::_S_oom_malloc(size_t __n)
{
    void (* __my_malloc_handler)();
    void* __result;

    for (;;)
    {
        __my_malloc_handler = __malloc_alloc_oom_handler;
        if (0 == __my_malloc_handler)
        {
            __THROW_BAD_ALLOC;
        }
        
        (*__my_malloc_handler)();
        
        __result = malloc(__n);
        
        if (__result)
        {
            return(__result);
        }
    }
}

template <bool __threads, int __inst>
char* __default_alloc_template<__threads, __inst>::_S_start_free = 0;

template <bool __threads, int __inst>
char* __default_alloc_template<__threads, __inst>::_S_end_free = 0;

template <bool __threads, int __inst>
size_t __default_alloc_template<__threads, __inst>::_S_heap_size = 0;

template <bool threads, int inst>
class __default_alloc_template {
// ...
public:
// ...

  /* __p may not be 0 */
    static void deallocate(void* __p, size_t __n)
    {
        if (__n > (size_t) _MAX_BYTES)
        {
            malloc_alloc::deallocate(__p, __n);
        }
        else
        {
            _Obj* __STL_VOLATILE*  __my_free_list = 
                _S_free_list + _S_freelist_index(__n);
            _Obj* __q = (_Obj*)__p;
            
            // acquire lock
#           ifndef _NOTHREADS
            /*REFERENCED*/
            _Lock __lock_instance;
#           endif /* _NOTHREADS */
    
            __q -> _M_free_list_link = *__my_free_list;
            *__my_free_list = __q;
            // lock is released here
        }
    }

//...
};

template <bool threads, int inst>
void*
__default_alloc_template<threads, inst>::reallocate(void* __p,
                                                    size_t __old_sz,
                                                    size_t __new_sz)
{
    void* __result;
    size_t __copy_sz;

    if (__old_sz > (size_t)_MAX_BYTES && __new_sz > (size_t)_MAX_BYTES)
    {
        return(realloc(__p, __new_sz));
    }
    if (_S_round_up(__old_sz) == _S_round_up(__new_sz))
    {
        return(__p);
    }
    __result = allocate(__new_sz);
    __copy_sz = __new_sz > __old_sz ? __old_sz : __new_sz;
    memcpy(__result, __p, __copy_sz);
    deallocate(__p, __old_sz);
    return(__result);
}

int main()
{
	ThreadPool pool;
    pool.setMode(fixed(default) | cached);
    pool.start();
}

Result result = pool.submitTask(concreteTask);
result.get().Cast<T>();

enum class PoolMode
{
    MODE_FIXED,     // 固定数量的线程
    MODE_CACHED,    // 线程数量可动态增长
};
class ThreadPool
{
public:
    ThreadPool();
    ~ThreadPool();
    /* 设置线程池的工作模式 */
    void setMode(PoolMode mode);
    /* 设置初始的线程数量 */
    void setInitThreadSize(int size);
    /* 设置task队列任务数量最大阈值 */
    void setTaskQueMaxThreshHold(int threshHold);
    /* 启动线程池 */
    void start();
    /* 给线程池提交任务 */
    void submitTask(std::shared_ptr<Task> task);
private:
    PoolMode m_poolMode;                //当前线程池工作模式
    std::vector<Thread*> m_threads;     //线程列表
    int m_initThreadSize;               //初始的线程数量
    /**
     * 任务队列容器。
     * 特别要注意，需要用 shared_ptr 强引用用户传来的 task ，
     * 以保证任务对象的生命期。
     */
    std::queue<std::shared_ptr<Task>> m_taskQueue;
    /* 目前任务队列中的任务数量 */
    std::atomic_int m_taskNum;
    /* 任务队列最大上限阈值 */
    int m_taskQueMaxThreshHold;
    /* 保护安全地操作任务队列 */
    std::mutex m_taskQueMtx;
    /* 表示任务队列不满 */
    std::condition_variable m_taskQueNotFull;
    /* 表示任务队列不空 */
    std::condition_variable m_taskQueNotEmpty;
private:
    ThreadPool(const ThreadPool &) = delete;
    ThreadPool& operator=(const ThreadPool &) = delete;
};

/* 线程池构造 */
ThreadPool::ThreadPool()
   : m_initThreadSize(4),
     m_taskNum(0),
     m_taskQueMaxThreshHold(TASK_MAX_THRESHHOLD),
     m_poolMode(PoolMode::MODE_FIXED)
{

}
ThreadPool::~ThreadPool()
{

}

/* 设置线程池的工作模式 */
void ThreadPool::setMode(PoolMode mode)
{
   m_poolMode = mode;
}
/* 设置初始的线程数量 */
void ThreadPool::setInitThreadSize(int size)
{
   m_initThreadSize = size;
}
/* 设置task队列任务数量最大阈值 */
void ThreadPool::setTaskQueMaxThreshHold(int threshHold)
{
   m_taskQueMaxThreshHold = threshHold;
}

/* 启动线程池 */
void ThreadPool::start(int initThreadSize);

/* 给线程池提交任务 */
void ThreadPool::submitTask(std::shared_ptr<Task> task);

/* threadpool.h */
class ThreadPool
{
private:
  /* 定义线程函数 */
  void threadFunc();
};

void ThreadPool::start(int initThreadSize)
{
    m_initThreadSize = initThreadSize;
    for(int i = 0; i < m_initThreadSize; ++i)
    {
        m_threads.emplace_back(
            new Thread(std::bind(&ThreadPool::threadFunc, this))
        );
    }
    for(int i = 0; i < m_initThreadSize; ++i)
    {
        m_threads[i]->start();
    }
}

class Thread
{
public:
    /* 线程函数对象类型别名 */
    using ThreadFunc = std::function<void()>;
    Thread(ThreadFunc func);
    ~Thread();
    void start();
private:
    ThreadFunc m_func;
};

/* threadpool.cpp */
#include<thread>
/* 启动线程 */
void Thread::start()
{
    std::thread t(m_func);	//线程对象t，线程函数m_func
    t.detach();
}

void ThreadPool::threadFunc()
{
  std::cout << "begin threadFunc tid:" 
      << std::this_thread::get_id() << std::endl;
  std::cout << "end threadFunc" 
      << std::this_thread::get_id() << std::endl;
}
/* 线程池项目测试.cpp */
#include"threadpool.h"
#include<iostream>
#include<chrono>
#include<thread>
int main()
{
    ThreadPool pool;
    pool.start();
    std::this_thread::sleep_for(std::chrono::seconds(5));
}

void ThreadPool::start(int initThreadSize)
{
    m_initThreadSize = initThreadSize;
    for(int i = 0; i < m_initThreadSize; ++i)
    {
        auto ptr = std::make_unique<Thread>(
            std::bind(&ThreadPool::threadFunc, this)
        );
        m_threads.emplace_back(ptr);
    }
    for(int i = 0; i < m_initThreadSize; ++i)
    {
        m_threads[i]->start();
    }
}

m_threads.emplace_back(std::move(ptr));

/* 给线程池提交任务 */
void ThreadPool::submitTask(std::shared_ptr<Task> sp)
{
    /* 获取锁 */
    std::unique_lock<std::mutex> lock(m_taskQueMtx);
    /* 线程的通信，等待任务队列有空余 */
    //while(taskQue_.size() == taskQueMaxThreshHold_){ notFull_.wait(); }
    m_taskQueNotFull.wait(
        lock,
        [&]()->bool {
            return m_taskQueue.size() < m_taskQueMaxThreshHold;
        }
    );
    /* 如果有空余，把任务放到任务队列中 */
	m_taskQueue.emplace(sp);
    ++m_taskNum;
    /* 因为新放了任务，任务队列肯定不空了，通知notEmpty_上的等待线程 */
    m_taskQueNotEmpty.notify_all();
}

if(!m_taskQueNotFull.wait_for(
    lock,
    std::chrono::seconds(1),
    [&]()->bool {
        return taskQue_.size() < (size_t)taskQueMaxThreshHold_;
    }))
{
    std::cerr<<"task queue is full, submit out of time failed."<<endl;
    return;
}

void ThreadPool::threadFunc()
{
for(;;)
{
    std::shared_ptr<Task> task;
    /* 块作用域 */
    {
        /* 先获取锁 */
        std::unique_lock<std::mutex> lock(m_taskQueMtx);
        std::cout << "tid:" << std::this_thread::get_id()
            << "尝试获取任务..." << std::endl;
        /* 等待notEmpty条件 */
        m_taskQueNotEmpty.wait(
            lock,
            [&]()->bool {
                return m_taskQueue.size() > 0;
            }
        );
        std::cout << "tid:" << std::this_thread::get_id()
            << "获取任务成功..." << std::endl;
        /* 从任务队列中取一个任务出来 */
        task = m_taskQueue.front();
        m_taskQueue.pop();
        --m_taskNum;
        /* 如果有剩余任务，继续通知其他线程来取任务 */
        if (m_taskQueue.size() > 0)
        {
            m_taskQueNotEmpty.notify_all();
        }
        /* 取出了一个任务，任务队列此时肯定不满了，对等待提交任务的人进行通知 */
        m_taskQueNotFull.notify_one();
    }
    /* 当前线程负责执行这个任务, 没必要拥有锁, 脱离块作用域, 释放锁 */
    if(task != nullptr)
        task->run();
}
}

class MyTask : public Task
{
public:
    void run()
    {
        std::cout << "tid:" << std::this_thread::get_id()
            << "begin!" << std::endl;
        
        std::this_thread::sleep_for(std::chrono::seconds(2));
        
    	std::cout << "tid:" << std::this_thread::get_id()
            << "end!" << std::endl;
    }
};
-------------------------------------------------------------------
test example:
/* 以下为提交3个任务，预估结果为3个线程获取任务成功，1个没有获取到，一直阻塞 */
int main()
{
    ThreadPool pool;
	pool.start(4);
	pool.submitTask(std::make_shared<MyTask>());
	pool.submitTask(std::make_shared<MyTask>());
	pool.submitTask(std::make_shared<MyTask>());
    getchar();
}
/* 若4个线程，提交5个任务，则最先完成并抢到锁的线程能再次获得第5个任务 */
/* 若4个线程，提交10个任务，并把队列容量设为4，则可能有2个任务提交失败 */

class MyTask : public Task
{
public:
    MyTask(int begin, int end)
    	: begin_(begin), end_(end)
    {
        
    }
    void run()
    {
        std::cout << "tid:" << std::this_thread::get_id()
            << "begin!" << std::endl;
        int sum = 0;
        for(int i = begin_; i <= end_; ++i)
        {
            sum += i;
        }
        
    	std::cout << "tid:" << std::this_thread::get_id()
            << "end!" << std::endl;
        
        return sum;
    }
};

Result res1 = pool.submitTask(std::make_shared<MyTask>(1, 10000));
Result res2 = pool.submitTask(std::make_shared<MyTask>(10001, 20000));
Result res3 = pool.submitTask(std::make_shared<MyTask>(20001, 30000));
res1.get();
res2.get();
res3.get();

class Any
{
public:
    Any() = default;
    ~Any() = default;
    Any(const Any&) = delete;
    Any& operator=(const Any&) = delete;
    Any(Any &&) = default;
    Any& operator=(Any &&) = default;
    
    /* 这个构造函数可以让 Any 类型接收任意其他的数据 */
    template<typename T>
    Any(T data) : base_(std::make_unique<Derived<T>>(data))
    {}
    /* 这个方法能把 Any 对象里面存储的 data 数据提取出来 */
    template<typename T>
    T cast_()
    {
        // base_ 是定义在 Any 类中的一个 std::unique_ptr<Base>
        // get() 可以获得 其实际指针
        Derive<T>* pd = dynamic_cast<Derive<T>*>(base_.get());
        if(pd == nullptr)
        {
            throw "type is unmatch!";
        }
        return pd->data_;
    }
private:
    class Base
    {
    public:
        virtual ~Base() = default;
    };
    
    template<typename T>
    class Derived : public Base
    {
    public:
        Derived(T data) : data_(data)
        {}
    private:
        // 实际的 data 存在 Derived 类中。
        T data_;
    };
    
private:
    /* 定义一个基类的指针 */
    std::unique_ptr<Base> base_;
};
int main()
{
    ThreadPool pool;
    pool.start(4);
    
    Result res = pool.submitTask(std::make_shared<MyTask>(1, 10000));
    int sum = res.get().cast_<int>();
}

class Semaphore
{
public:
    Semaphore(int limit = 0)
        : resLimit_(limit)
    {
    }
    ~Semaphore() = default;
    /* 获取一个信号量资源 */
    void wait()
    {
        std::unique_lock<std::mutex> lock(mtx_);
        /* 等待信号量有资源，没有资源的话，阻塞当前线程 */
        cond_.wait(lock, [&]()->bool {return resLimit_ > 0;});
        --resLimit_;
    }
    /* 增加一个信号量资源 */
    void post()
    {
        std::unique_lock<std::mutex> lock(mtx_);
        ++resLimit_;
        cond_.notify_one();
    }
private:
    // 信号量目前拥有的资源数
    int resLimit_;
    std::mutex mtx_;
    std::condition_variable cond_;
};

class ThreadPool
{
/*			...			*/
public:
    Result submitTask(std::shared_ptr<Task> sp);
/*			...			*/
};
--------------------------
Result ThreadPool::submitTask(std::shared_ptr<Task> sp)
{
/*			...			*/
	if(...)
    {
        ...
/*		思考，return时用下面哪种方式？	*/
/*      return task->getResult();	 */
        // 此时是提交任务失败的返回
        return Result(task);
    }

/*			...			*/

/*	思考，return时用下面哪种方式？	*/
/*  return task->getResult();	 */
    // 此时是提交任务成功后的返回
    return Result(task);
}

/* 实现接收提交到线程池的task任务执行完成后的返回值类型Result */
class Result
{
public:
    Result(std::shared_ptr<Task> task, bool isValid = true);
    ~Result() = default;
private:
    /* 存储任务的返回值 */
    Any any_;
    /* 线程通信信号量 */
    Semaphore sem_;
    /* 指向对应获取返回值的任务对象 */
    std::shared_ptr<Task> task_;
    /* 任务执行是否有效/成功 */
    std::atomic_bool isValid_;
}
------------------
//threadpool.cpp
Result::Result(std::shared_ptr<Task> task, bool isValid)
    : isValid_(isValid), task_(task)
{
}

class Result
{
public:
    void setVal(Any any);
    Any get();
private:
    Any any_;
    Semaphore sem_;
    std::shared_ptr<Task> task_;
    std::atomic_bool isValid_;
};
-------------
/* 	用户调用的 */
Any Result::get()
{
    if(!isValid_)
    {
        return "";
    }
    /* 阻塞用户的线程直到task通知其执行完毕 */
    sem_.wait();
    return std::move(any_);
}
/* 谁调用？答案是 Task 的 run 结束之后，通过Result * result_ 间接调用次函数，通知 get() 唤醒拿结果 */
void Result::setVal(Any any)
{
    /* 存储task的返回值 */
    this->any_ = std::move(any);
    sem_.post();
}

void Task::exec()
{
    if(result_ != nullptr)
    {
        // run()结束之后，setVal才能被调用成功，此时影响到了 result_ 中保存的信号量 +1，因此 外部的result.get()不再阻塞
	    result_->setVal(run());	//如此可知，task中需要封装一个result对象。
    }
}
----------------
class Task
{
public:
    Task();
    ~Task() = default;
	void exec();
    void setResult(Result *res);
    virtual Any run() = 0;
private:
/*	没必要用shared智能指针，否则就会出现：Result中有shared_ptr<Task>，Task中有shared_ptr<Result>。循环引用，无法释放！*/
    Result *result_;	//result对象的生命周期长于task，不怕。
};
----------------
void Task::setResult(Result *res)
{
    result_ = res;
}
Task::Task()
    : result_(nullptr)
{       
}
----------------
/* 谁调用setResult？此 Result 不是 Result 里的 val ， 而是保存 Val 的一个地方，不要搞混了 */
// 外部可以通过 task 来 指定 Result 要保存到哪个地方。
// 比如可以传入 外部 Result 的 this 指针；也可以 new 一个 Result 在 堆上，set 到堆上地址
// 如果 Result 绑定了一个 task 就可以 通过这个 task 设置 Result 为 自己（this）
Result::Result(std::std::shared_ptr<Task> task, bool isValid)
	: isValid_(isValid), task_(task)
{
    task_->setResult(this);
}

class MyTask : public Task
{
public:
    MyTask(int begin, int end)
    	: begin_(begin), end_(end)
    {
    }
	Any run()
    {
        std::cout << "tid:" << std::this_thread::get_id()
            << "begin!" << std::endl;
        uLong sum = 0;
        for(uLong i = begin_; i <= end_; ++i)
            sum += i;
        std::cout << "tid:" << std::this_thread::get_id()
            << "end!" << std::endl;
        return sum;
    }
};
using uLong = unsigned long long;
int main()
{
    ThreadPool pool;
    pool.start(4);
    Result res1 = pool.submitTask(std::make_shared<MyTask>(1, 100000000));
    Result res2 = pool.submitTask(std::make_shared<MyTask>(100000001, 200000000));
    Result res3 = pool.submitTask(std::make_shared<MyTask>(200000001, 300000000));
    uLong sum1 = res1.get().cast_<uLong>();
    uLong sum2 = res2.get().cast_<uLong>();
    uLong sum3 = res3.get().cast_<uLong>();
    cout << sum1 + sum2 + sum3 << endl;
}

int main()
{
    ThreadPool pool;
    /* 用户自己设置线程池的工作模式 */
    pool.setMode(PoolMode::MODE_CACHED);
    /* 开始启动线程池 */
    pool.start(4);
}