C++ – Feeding std::streambuf for Non-Blocking std::istream Read

You have to use a blocking construct on a per-request basis.

This is called Futures (programming)

Each request will have its own Future. Once the request processing is started (possibly in a separate pool of threads, as you have described), the caller will be blocked on the Future's fulfillment, or failure.

When the result arrives, the Future is unblocked, and the call will return to the application.

When using this pattern, one must take great care prevent deadlocks and zombies. In other words, the Future needs to be unblocked at some time, whether the result is successful or failure (and in case of failure, throwing an exception back to the application is a fair game) - the call must not just hang there indefinitely.

As to thread-pool design:

• There will be at least one thread per simultaneous requester (i.e. application), which will be blocked during the request.
  • If the applications and the service are inside the same process, these threads are the same as the application threads, which will become blocked.
• There will be a separate thread pool, requiring as many threads as is necessary to do the work between the service and the internet. These threads are in addition to the request-accepting threads.
  • The exact number depends on how the work is done. It is possible to use asynchronous pattern (reactor) here, which might reduce the number of threads needed, but that will not have any effect on the number of request-accepting threads.

If the request from Application to Service occurs over network, there is a decoupling between Application threads and Service threads (in other words, a blocking of an Application request does not involve a "thread" at all; just a non-response from a network connection.) In that case the Service can also use reactor pattern, which means you can further reduce the number of threads.

StackOverflow would be a somewhat better place for asking programming/algorithm related questions. In any case, the implementation you must have read would be based on "tables". Here is how such implementation works:

• Initialize vector with size n, say n = 16

Address: 0xAAA0 to 0xAAB0 Memory reserved

• Insert 17 elements. First 16 inserted fine. Next element requires more memory.

STL Library: Allocate memory for 16 * 2 = 32. Copy 16 elements. (Actual time taken = 16 units). Insert the 17th element.

• Insert 16 more elements. First 15 inserted fine. Next element requires more space.

STL Library: Allocate memory for 16 * 2 * 2 = 64. Copy 32 elements. (Actual time taken = 32 units). Insert the 33rd element.

• Insert 32 more elements. First 31 inserted fine. Next requires more space. STL Library: Allocate memory for 16 * 2 * 2 * 2 = 128. Copy 64 elements. (Actual time taken = 64 units). Insert the 65th element.

This implementation is O(1) for accessing and O(1) amortized for insertion. How? Over a very large number of operations, the total time of inserts would be:

Time = 2^0 (inserts) + 2^0 (copy) + 2^1 / 2 ( inserts ) + 2^1(copy) + 2^2/2 (inserts) + 2^2 (copy) ... .. + 2^n(copy)

• Total number of inserts = 2^n Time = 2^0 + 2^0 + 2^0 + 2^1 + 2^1 + 2^2 + 2^2 = 1 + 2*2^0 + 2*2^1 +...+2*2^(n-1) = 1 + 2*(2^n - 1)

Average time per insert = 2 units

• Total inserts = 2^n + 1 Time = 2^0 + 2^0 + 2^0 + 2^1 + 2^1 + 2^2 + 2^2 + 2^3 ... = 1 + 2*2^0 + 2*2^1 +...+2*2^(n-1) + 2^n = 1 + 2*(2^n - 1) + 2^n

Average time per insert = 3 units

Its not a linked list- but I'm pretty this is what you read: 'increasing/decreasing' sizes. Decrease in size upon deletes is similar. When used size is less than 1/4, free up the rest of memory, free up half of memory. If you're using your own memory allocator, it shouldn't be too hard to free only what you want. But if you want to copy over as well, analysis would tell you deletes still remain O(1)