bdbuf.c

RTEMS (Real-Time Executive for Multiprocessor Systems) is a free open source real-time operating sys

    memset(buf_stack, 0, sizeof(buf_stack));

    while (p != NULL)
    {
        *buf_prev++ = p;

        if ((p->dev < dev) || ((p->dev == dev) && (p->block < block)))
        {
            p->avl.cache = 1;
            p = p->avl.right;
        }
        else if ((p->dev != dev) || (p->block != block))
        {
            p->avl.cache = -1;
            p = p->avl.left;
        }
        else
        {
            /* node found */
            break;
        }
    }
    
    if (p == NULL)
    {
        /* there is no such node */
        return -1;
    }

    q = p;

    buf_prev--;
    if (buf_prev > buf_stack)
    {
        p = *(buf_prev - 1);
    }
    else
    {
        p = NULL;
    }

    /* at this moment q - is a node to delete, p is q's parent */
    if (q->avl.right == NULL)
    {
        r = q->avl.left;
        if (r != NULL)
        {   
            r->avl.bal = 0;
        }
        q = r;
    }
    else
    {
        bdbuf_buffer **t;

        r = q->avl.right;

        if (r->avl.left == NULL)
        {
            r->avl.left = q->avl.left;
            r->avl.bal = q->avl.bal;
            r->avl.cache = 1;
            *buf_prev++ = q = r;
        }
        else
        {
            t = buf_prev++;
            s = r;
            
            while (s->avl.left != NULL)
            {
                *buf_prev++ = r = s;
                s = r->avl.left;
                r->avl.cache = -1;
            }
            
            s->avl.left = q->avl.left;
            r->avl.left = s->avl.right;
            s->avl.right = q->avl.right;
            s->avl.bal = q->avl.bal;
            s->avl.cache = 1;
            
            *t = q = s;
        }
    }

    if (p != NULL)
    {
        if (p->avl.cache == -1)
        {
            p->avl.left = q;
        }
        else
        {
            p->avl.right = q;
        }
    }
    else
    {
        *root = q;
    }

    modified = TRUE;

    while (modified)
    {
        if (buf_prev > buf_stack)
        {
            p = *--buf_prev;
        }
        else
        {
            break;
        }
        
        if (p->avl.cache == -1)
        {
            /* rebalance left branch */
            switch (p->avl.bal)
            {
                case -1:
                    p->avl.bal = 0;
                    break;
                case  0:
                    p->avl.bal = 1;
                    modified = FALSE;
                    break;

                case +1:
                    p1 = p->avl.right;

                    if (p1->avl.bal >= 0) /* simple RR-turn */
                    {
                        p->avl.right = p1->avl.left;
                        p1->avl.left = p;

                        if (p1->avl.bal == 0)
                        {
                            p1->avl.bal = -1;
                            modified = FALSE;
                        }
                        else
                        {
                            p->avl.bal = 0;
                            p1->avl.bal = 0;
                        }
                        p = p1;
                    }
                    else /* double RL-turn */
                    {
                        p2 = p1->avl.left;

                        p1->avl.left = p2->avl.right;
                        p2->avl.right = p1;
                        p->avl.right = p2->avl.left;
                        p2->avl.left = p;
                        
                        if (p2->avl.bal == +1) p->avl.bal = -1; else p->avl.bal = 0;
                        if (p2->avl.bal == -1) p1->avl.bal = 1; else p1->avl.bal = 0;
                        
                        p = p2;
                        p2->avl.bal = 0;
                    }
                    break;

                default:
                    break;
            }
        }
        else
        {
            /* rebalance right branch */
            switch (p->avl.bal)
            {
                case +1:
                    p->avl.bal = 0;
                    break;

                case  0:
                    p->avl.bal = -1;
                    modified = FALSE;
                    break;

                case -1:
                    p1 = p->avl.left;

                    if (p1->avl.bal <= 0) /* simple LL-turn */
                    {
                        p->avl.left = p1->avl.right;
                        p1->avl.right = p;
                        if (p1->avl.bal == 0)
                        {
                            p1->avl.bal = 1;
                            modified = FALSE;
                        }
                        else
                        {
                            p->avl.bal = 0;
                            p1->avl.bal = 0;
                        }
                        p = p1;
                    }
                    else /* double LR-turn */
                    {
                        p2 = p1->avl.right;

                        p1->avl.right = p2->avl.left;
                        p2->avl.left = p1;
                        p->avl.left = p2->avl.right;
                        p2->avl.right = p;
                        
                        if (p2->avl.bal == -1) p->avl.bal = 1; else p->avl.bal = 0;
                        if (p2->avl.bal == +1) p1->avl.bal = -1; else p1->avl.bal = 0;

                        p = p2;
                        p2->avl.bal = 0;
                    }
                    break;

                default:
                    break;
            }
        }

        if (buf_prev > buf_stack)
        {
            q = *(buf_prev - 1);
            
            if (q->avl.cache == -1)
            {
                q->avl.left = p;
            }
            else
            {
                q->avl.right = p;
            }
        }
        else
        {
            *root = p;
            break;
        }

    }
    
    return 0;
}

/* bdbuf_initialize_pool --
 *      Initialize single buffer pool.
 *
 * PARAMETERS:
 *     config - buffer pool configuration
 *     pool   - pool number
 *
 * RETURNS:
 *     RTEMS_SUCCESSFUL, if buffer pool initialized successfully, or error
 *     code if error occured.
 */
static rtems_status_code
bdbuf_initialize_pool(rtems_bdbuf_config *config, int pool)
{
    bdbuf_pool *p = bd_ctx.pool + pool;
    unsigned char *bufs;
    bdbuf_buffer *b;
    rtems_status_code rc;
    int i;
    
    p->blksize = config->size;
    p->nblks = config->num;
    p->tree = NULL;
    
    Chain_Initialize_empty(&p->free);
    Chain_Initialize_empty(&p->lru);
    
    /* Allocate memory for buffer descriptors */
    p->bdbufs = calloc(config->num, sizeof(bdbuf_buffer));
    if (p->bdbufs == NULL)
    {
        return RTEMS_NO_MEMORY;
    }
    
    /* Allocate memory for buffers if required */
    if (config->mem_area == NULL)
    {
        bufs = p->mallocd_bufs = malloc(config->num * config->size);
        if (bufs == NULL)
        {
            free(p->bdbufs);
            return RTEMS_NO_MEMORY;
        }
    }
    else
    {
        bufs = config->mem_area;
        p->mallocd_bufs = NULL;
    }
    
    for (i = 0, b = p->bdbufs; i < p->nblks; i++, b++, bufs += p->blksize)
    {
        b->dev = -1; b->block = 0;
        b->buffer = bufs;
        b->actual = b->modified = b->in_progress = FALSE;
        b->use_count = 0;
        b->pool = pool;
        _Chain_Append(&p->free, &b->link);
    }
    
    rc = rtems_semaphore_create(
        rtems_build_name('B', 'U', 'F', 'G'),
        p->nblks,
        RTEMS_FIFO | RTEMS_COUNTING_SEMAPHORE | RTEMS_NO_INHERIT_PRIORITY |
        RTEMS_NO_PRIORITY_CEILING | RTEMS_LOCAL,
        0,
        &p->bufget_sema);
    
    if (rc != RTEMS_SUCCESSFUL)
    {
        free(p->bdbufs);
        free(p->mallocd_bufs);
        return rc;
    }
    
    return RTEMS_SUCCESSFUL;
}

/* bdbuf_release_pool --
 *     Free resources allocated for buffer pool with specified number.
 *
 * PARAMETERS:
 *     pool - buffer pool number
 *
 * RETURNS:
 *     RTEMS_SUCCESSFUL
 */
static rtems_status_code
bdbuf_release_pool(rtems_bdpool_id pool)
{
    bdbuf_pool *p = bd_ctx.pool + pool;
    rtems_semaphore_delete(p->bufget_sema);
    free(p->bdbufs);
    free(p->mallocd_bufs);
    return RTEMS_SUCCESSFUL;
}

/* rtems_bdbuf_init --
 *     Prepare buffering layer to work - initialize buffer descritors 
 *     and (if it is neccessary)buffers. Buffers will be allocated accoriding
 *     to the configuration table, each entry describes kind of block and 
 *     amount requested. After initialization all blocks is placed into
 *     free elements lists.
 *
 * PARAMETERS:
 *     conf_table - pointer to the buffers configuration table
 *     size       - number of entries in configuration table
 *
 * RETURNS:
 *     RTEMS status code (RTEMS_SUCCESSFUL if operation completed successfully
 *     or error code if error is occured)
 */
rtems_status_code
rtems_bdbuf_init(rtems_bdbuf_config *conf_table, int size)
{
    rtems_bdpool_id i;
    rtems_status_code rc;

    if (size <= 0)
        return RTEMS_INVALID_SIZE;
    
    bd_ctx.npools = size;

    /*
     * Allocate memory for buffer pool descriptors
     */
    bd_ctx.pool = calloc(size, sizeof(bdbuf_pool));
    if (bd_ctx.pool == NULL)
    {
        return RTEMS_NO_MEMORY;
    }

    Chain_Initialize_empty(&bd_ctx.mod);
    
    /* Initialize buffer pools and roll out if something failed */
    for (i = 0; i < size; i++)
    {
        rc = bdbuf_initialize_pool(conf_table + i, i);
        if (rc != RTEMS_SUCCESSFUL)
        {
             rtems_bdpool_id j;
             for (j = 0; j < i - 1; j++)
             {
                 bdbuf_release_pool(j);
             }
             return rc;
        }
    }

    /* Create buffer flush semaphore */
    rc = rtems_semaphore_create(
        rtems_build_name('B', 'F', 'L', 'U'), 0,
        RTEMS_FIFO | RTEMS_COUNTING_SEMAPHORE | RTEMS_NO_INHERIT_PRIORITY |
        RTEMS_NO_PRIORITY_CEILING | RTEMS_LOCAL, 0,
        &bd_ctx.flush_sema);
    if (rc != RTEMS_SUCCESSFUL)
    {
        for (i = 0; i < size; i++)
            bdbuf_release_pool(i);
        free(bd_ctx.pool);
        return rc;
    }
    
    /* Create and start swapout task */
    rc = rtems_task_create(