/*
** Copyright (C) 2004-2006 by Carnegie Mellon University.
**
** @OPENSOURCE_HEADER_START@
** 
** Use of the SILK system and related source code is subject to the terms 
** of the following licenses:
** 
** GNU Public License (GPL) Rights pursuant to Version 2, June 1991
** Government Purpose License Rights (GPLR) pursuant to DFARS 252.225-7013
** 
** NO WARRANTY
** 
** ANY INFORMATION, MATERIALS, SERVICES, INTELLECTUAL PROPERTY OR OTHER 
** PROPERTY OR RIGHTS GRANTED OR PROVIDED BY CARNEGIE MELLON UNIVERSITY 
** PURSUANT TO THIS LICENSE (HEREINAFTER THE "DELIVERABLES") ARE ON AN 
** "AS-IS" BASIS. CARNEGIE MELLON UNIVERSITY MAKES NO WARRANTIES OF ANY 
** KIND, EITHER EXPRESS OR IMPLIED AS TO ANY MATTER INCLUDING, BUT NOT 
** LIMITED TO, WARRANTY OF FITNESS FOR A PARTICULAR PURPOSE, 
** MERCHANTABILITY, INFORMATIONAL CONTENT, NONINFRINGEMENT, OR ERROR-FREE 
** OPERATION. CARNEGIE MELLON UNIVERSITY SHALL NOT BE LIABLE FOR INDIRECT, 
** SPECIAL OR CONSEQUENTIAL DAMAGES, SUCH AS LOSS OF PROFITS OR INABILITY 
** TO USE SAID INTELLECTUAL PROPERTY, UNDER THIS LICENSE, REGARDLESS OF 
** WHETHER SUCH PARTY WAS AWARE OF THE POSSIBILITY OF SUCH DAMAGES. 
** LICENSEE AGREES THAT IT WILL NOT MAKE ANY WARRANTY ON BEHALF OF 
** CARNEGIE MELLON UNIVERSITY, EXPRESS OR IMPLIED, TO ANY PERSON 
** CONCERNING THE APPLICATION OF OR THE RESULTS TO BE OBTAINED WITH THE 
** DELIVERABLES UNDER THIS LICENSE.
** 
** Licensee hereby agrees to defend, indemnify, and hold harmless Carnegie 
** Mellon University, its trustees, officers, employees, and agents from 
** all claims or demands made against them (and any related losses, 
** expenses, or attorney's fees) arising out of, or relating to Licensee's 
** and/or its sub licensees' negligent use or willful misuse of or 
** negligent conduct or willful misconduct regarding the Software, 
** facilities, or other rights or assistance granted by Carnegie Mellon 
** University under this License, including, but not limited to, any 
** claims of product liability, personal injury, death, damage to 
** property, or violation of any laws or regulations.
** 
** Carnegie Mellon University Software Engineering Institute authored 
** documents are sponsored by the U.S. Department of Defense under 
** Contract F19628-00-C-0003. Carnegie Mellon University retains 
** copyrights in all material produced under this contract. The U.S. 
** Government retains a non-exclusive, royalty-free license to publish or 
** reproduce these documents, or allow others to do so, for U.S. 
** Government purposes only pursuant to the copyright license under the 
** contract clause at 252.227.7013.
** 
** @OPENSOURCE_HEADER_END@
*/

/*
**  Standard path queue implementation
**
*/


/* Includes */
#include "silk.h"

RCSIDENT("$SiLK: skdqstd.c 3856 2006-05-26 15:38:34Z mwd $");

#include "skdqprivate.h"

/* Standard deque */
typedef struct std_dq_t {
    uint32_t size;
    item_t *dir[2];		/* 0 == back, 1 == front */
    uint8_t blocked;
} std_dq_t;

/* Standard methods */
static skDQErr_t std_status(skDeque_t self);
static skDQErr_t std_pop(skDeque_t self, void **item, 
			 uint8_t block, uint8_t front, uint32_t seconds);
static skDQErr_t std_peek(skDeque_t self, void **item, uint8_t front);
static skDQErr_t std_push(skDeque_t self, void *item, uint8_t front);
static skDQErr_t std_destroy(skDeque_t self);
static skDQErr_t std_block(skDeque_t self, uint8_t flag);
static uint32_t std_size(skDeque_t self);


/* Create a deque */
skDeque_t skDequeCreate()
{
    skDeque_t deque;
    std_dq_t *data;

    /* memory allocation */
    if ((deque = (skDeque_t)malloc(sizeof(sk_deque_t))) == NULL) {
        return NULL;
    }
    if ((data = (std_dq_t *)malloc(sizeof(std_dq_t))) == NULL) {
        free(deque);
        return NULL;
    }
  
    /* Initialize data */
    data->dir[0] = data->dir[1] = NULL;
    data->size = 0;
    data->blocked = 1;

    /* Initialize deque */
    deque->ref = 1;		/* Initialize to 1 */
    pthread_mutex_init(&deque->mutex_data, NULL);
    pthread_cond_init(&deque->cond_data, NULL);
    deque->mutex = &deque->mutex_data;
    deque->cond = &deque->cond_data;
    deque->methods.status = std_status;
    deque->methods.pop = std_pop;
    deque->methods.peek = std_peek;
    deque->methods.push = std_push;
    deque->methods.destroy = std_destroy;
    deque->methods.block = std_block;
    deque->methods.size = std_size;
    deque->data = (void *)data;
  
    return deque;
}


static skDQErr_t std_status(skDeque_t self)
{
    std_dq_t *q = (std_dq_t *)self->data;

    if (q == NULL) {
        return SKDQ_ERROR;
    }
    if (q->dir[0] == NULL) {
        return SKDQ_EMPTY;
    }
    return SKDQ_SUCCESS;
}


static skDQErr_t std_pop(skDeque_t self, void **item, 
			 uint8_t block, uint8_t f,
                         uint32_t seconds)
{
    std_dq_t *q = (std_dq_t *)self->data;
    item_t *t;
    uint8_t b;
    int rv;
    struct timeval now;
    struct timespec to;
  
    if (q == NULL) {
        return SKDQ_ERROR;
    }

    if (block) {
        gettimeofday(&now, NULL);
        to.tv_sec = now.tv_sec + seconds;
        to.tv_nsec = now.tv_usec * 1000;
        while (self->data && q->dir[0] == NULL && q->blocked) {
            if (seconds) {
                rv = pthread_cond_timedwait(self->cond, self->mutex, &to);
                if (rv == ETIMEDOUT) {
                    return SKDQ_TIMEDOUT;
                }
            } else {
                pthread_cond_wait(self->cond, self->mutex);
            }
        }
        if (self->data && !q->blocked) {
            return SKDQ_UNBLOCKED;
        }
    }
    if (self->data == NULL) {
        return SKDQ_DESTROYED;
    }

    if (q->dir[0] == NULL) {
        return SKDQ_EMPTY;
    }
  
    b = 1 - f;

    t = q->dir[f];
    *item = t->item;

    q->dir[f] = t->dir[b];
    if (q->dir[f]) {
        q->dir[f]->dir[f] = NULL;
    } else {
        q->dir[b] = NULL;
    }

    q->size--;
  
    free(t);

    return SKDQ_SUCCESS;
}


static skDQErr_t std_peek(skDeque_t self, void **item, uint8_t front)
{
    std_dq_t *q = (std_dq_t *)self->data;

    if (q == NULL) {
        return SKDQ_ERROR;
    }

    if (q->dir[0] == NULL) {
        return SKDQ_EMPTY;
    }

    *item = q->dir[front]->item;

    return SKDQ_SUCCESS;
}

static skDQErr_t std_push(skDeque_t self, void *item, uint8_t f)
{
    std_dq_t *q = (std_dq_t *)self->data;
    item_t *t;
    uint8_t b;

    if (q == NULL) {
        return SKDQ_ERROR;
    }

    if ((t = (item_t *)malloc(sizeof(item_t))) == NULL) {
        return SKDQ_ERROR;
    }

    t->item = item;

    b = 1 - f;

    t->dir[f] = NULL;
    t->dir[b] = q->dir[f];
    q->dir[f] = t;
    if (q->dir[b]) {
        t->dir[b]->dir[f] = t;
    } else {
        q->dir[b] = t;
        pthread_cond_broadcast(self->cond);
    }
    
    q->size++;

    return SKDQ_SUCCESS;
}

static skDQErr_t std_destroy(skDeque_t self)
{
    std_dq_t *q = (std_dq_t *)self->data;
    item_t *t, *x;

    if (q == NULL) {
        return SKDQ_ERROR;
    }

    for (t = q->dir[1]; t; t = x) {
        x = t->dir[0];
        free(t);
    }
  
    free(q);

    self->data = NULL;
  
    return SKDQ_SUCCESS;
}

static skDQErr_t std_block(skDeque_t self, uint8_t flag)
{
    std_dq_t *q = (std_dq_t *)self->data;

    if (q == NULL) {
        return SKDQ_ERROR;
    }
 
    q->blocked = flag;
    if (!flag) {
        pthread_cond_broadcast(self->cond);
    }

    return SKDQ_SUCCESS;
}


static uint32_t std_size(skDeque_t self)
{
    std_dq_t *q = (std_dq_t *)self->data;

    return q->size;
}