Clever memory management with constant time operations?
With fixed-size blocks, what you have described is a free list. This is a very common technique, with the following twist: the list of free blocks is stored in the free blocks themselves. In C code, it would look like this:

static void *alloc_ptr = START_OF_BIG_SEGMENT;
static void *free_list_head = NULL;

static void *
allocate(void)
{
    void *x;

    if (free_list_head == NULL) {
        x = alloc_ptr;
        alloc_ptr = (char *)alloc_ptr + SIZE_OF_BLOCK;
    } else {
        x = free_list_head;
        free_list_head = *(void **)free_list_head;
    }
    return x;
}

static void
release(void *x)
{
    *(void **)x = free_list_head;
    free_list_head = x;
}


This works well as long as all allocated blocks have the same size, and that size is a multiple of the size of a pointer, so that alignment is preserved. Allocation and deallocation are constant-time (that is, as constant-time as memory accesses and elementary additions -- in a modern computer, a memory access can involve cache misses and even virtual memory, hence disk accesses, so the "constant time" can be quite big). There is no memory overhead (no extra per-block pointers or things like that; the allocated blocks are contiguous). Also, the allocation pointer reaches a given point only if, at one time, that many blocks had to be allocated: since the allocation prefers using the free list, the allocation pointer is increased only if the space below the current pointer is clock full. In that sense, this is an optimal technique.

Decreasing the allocation pointer after a release can be more complex, since free blocks can be reliably identified only by following the free list, which goes through them in unpredictable order. If decreasing the big segment size when possible is important to you, you could want to use an alternate technique, with more overhead: between any two allocated blocks, you put a "hole". The holes are linked together with a doubly-linked list, in memory order. You need a data format for a hole such that you can locate the hole start address by knowing where it ends, and also the hole size if you know where the hole begins in memory. Then, when you release a block, you create a hole which you merge with the next and the previous holes, rebuilding (still in constant time) the ordered list of all holes. The overhead is then about two pointer-sized words per allocated block; but, at that price, you can reliably detect the occurrence of a "final hole", i.e. an occasion to decrease the big segment size.

There are many possible variations. A good introductory paper is Dynamic Storage Allocation: A Survey and Critical Review by Wilson et al.