/***************************************************************************

 * Copyright (c) 2009-2010 Open Information Security Foundation

 * Copyright (c) 2010-2013 Qualys, Inc.

 * All rights reserved.

 *

 * Redistribution and use in source and binary forms, with or without

 * modification, are permitted provided that the following conditions are

 * met:

 *

 * - Redistributions of source code must retain the above copyright

 *   notice, this list of conditions and the following disclaimer.

 * - Redistributions in binary form must reproduce the above copyright

 *   notice, this list of conditions and the following disclaimer in the

 *   documentation and/or other materials provided with the distribution.

 * - Neither the name of the Qualys, Inc. nor the names of its

 *   contributors may be used to endorse or promote products derived from

 *   this software without specific prior written permission.

 *

 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS

 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT

 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR

 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT

 * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,

 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT

 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,

 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY

 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT

 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE

 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

 ***************************************************************************/

/**

 * @file

 * @author Ivan Ristic <ivanr@webkreator.com>

 */

#include "htp_config_auto.h"

#include "htp_private.h"

// Array-backed list

htp_status_t htp_list_array_init(htp_list_t *l, size_t size) {

    // Allocate the initial batch of elements.

    l->elements = malloc(size * sizeof (void *));

    if (l->elements == NULL) {

        return HTP_ERROR;

    }

    // Initialize the structure.

    l->first = 0;

    l->last = 0;

    l->current_size = 0;

    l->max_size = size;

    return HTP_OK;

}

htp_list_t *htp_list_array_create(size_t size) {

    // It makes no sense to create a zero-size list.

    if (size == 0) return NULL;

    // Allocate the list structure.

    htp_list_array_t *l = calloc(1, sizeof (htp_list_array_t));

    if (l == NULL) return NULL;

    if (htp_list_array_init(l, size) == HTP_ERROR) {

        free(l);

        return NULL;

    }

    return (htp_list_t *) l;

}

void htp_list_array_clear(htp_list_array_t *l) {

    if (l == NULL) return;

    // Continue using already allocated memory; just reset the fields.

    l->first = 0;

    l->last = 0;

    l->current_size = 0;

}

void htp_list_array_destroy(htp_list_array_t *l) {

    if (l == NULL) return;

    free(l->elements);

    free(l);

}

void htp_list_array_release(htp_list_array_t *l) {

    if (l == NULL) return;

    free(l->elements);

}

void *htp_list_array_get(const htp_list_array_t *l, size_t idx) {

    if (l == NULL) return NULL;    

    if (idx >= l->current_size) return NULL;

    if (l->first + idx < l->max_size) {

        return (void *) l->elements[l->first + idx];

    } else {        

        return (void *) l->elements[idx - (l->max_size - l->first)];

    }

}

void *htp_list_array_pop(htp_list_array_t *l) {

    if (l == NULL) return NULL;

    const void *r = NULL;

    if (l->current_size == 0) {

        return NULL;

    }

    size_t pos = l->first + l->current_size - 1;

    if (pos > l->max_size - 1) pos -= l->max_size;

    r = l->elements[pos];

    l->last = pos;

    l->current_size--;

    return (void *) r;

}

htp_status_t htp_list_array_push(htp_list_array_t *l, void *e) {

    if (l == NULL) return HTP_ERROR;

    // Check whether we're full

    if (l->current_size >= l->max_size) {

        size_t new_size = l->max_size * 2;

        void *newblock = NULL;

        if (l->first == 0) {

            // The simple case of expansion is when the first

            // element in the list resides in the first slot. In

            // that case we just add some new space to the end,

            // adjust the max_size and that's that.

            newblock = realloc(l->elements, new_size * sizeof (void *));

            if (newblock == NULL) return HTP_ERROR;

        } else {

            // When the first element is not in the first

            // memory slot, we need to rearrange the order

            // of the elements in order to expand the storage area.

            /* coverity[suspicious_sizeof] */

            newblock = malloc((size_t) (new_size * sizeof (void *)));

            if (newblock == NULL) return HTP_ERROR;

            // Copy the beginning of the list to the beginning of the new memory block

            /* coverity[suspicious_sizeof] */

            memcpy(newblock,

                    (void *) ((char *) l->elements + l->first * sizeof (void *)),

                    (size_t) ((l->max_size - l->first) * sizeof (void *)));

            // Append the second part of the list to the end

            memcpy((void *) ((char *) newblock + (l->max_size - l->first) * sizeof (void *)),

                    (void *) l->elements,

                    (size_t) (l->first * sizeof (void *)));

            free(l->elements);

        }

        l->first = 0;

        l->last = l->current_size;

        l->max_size = new_size;

        l->elements = newblock;

    }

    l->elements[l->last] = e;

    l->current_size++;

    l->last++;

    if (l->last == l->max_size) {

        l->last = 0;

    }

    return HTP_OK;

}

htp_status_t htp_list_array_replace(htp_list_array_t *l, size_t idx, void *e) {

    if (l == NULL) return HTP_ERROR;

    if (idx + 1 > l->current_size) return HTP_DECLINED;

    l->elements[(l->first + idx) % l->max_size] = e;

    return HTP_OK;

}

size_t htp_list_array_size(const htp_list_array_t *l) {

    if (l == NULL) return HTP_ERROR;

    return l->current_size;

}

void *htp_list_array_shift(htp_list_array_t *l) {

    if (l == NULL) return NULL;

    void *r = NULL;

    if (l->current_size == 0) {

        return NULL;

    }

    r = l->elements[l->first];

    l->first++;

    if (l->first == l->max_size) {

        l->first = 0;

    }

    l->current_size--;

    return r;

}

#if 0

// Linked list

htp_list_linked_t *htp_list_linked_create(void) {

    htp_list_linked_t *l = calloc(1, sizeof (htp_list_linked_t));

    if (l == NULL) return NULL;

    return l;

}

void htp_list_linked_destroy(htp_list_linked_t *l) {

    if (l == NULL) return;

    // Free the list structures

    htp_list_linked_element_t *temp = l->first;

    htp_list_linked_element_t *prev = NULL;

    while (temp != NULL) {

        free(temp->data);

        prev = temp;

        temp = temp->next;

        free(prev);

    }

    // Free the list itself

    free(l);

}

int htp_list_linked_empty(const htp_list_linked_t *l) {

    if (!l->first) {

        return 1;

    } else {

        return 0;

    }

}

void *htp_list_linked_pop(htp_list_linked_t *l) {

    void *r = NULL;

    if (!l->first) {

        return NULL;

    }

    // Find the last element

    htp_list_linked_element_t *qprev = NULL;

    htp_list_linked_element_t *qe = l->first;

    while (qe->next != NULL) {

        qprev = qe;

        qe = qe->next;

    }

    r = qe->data;

    free(qe);

    if (qprev != NULL) {

        qprev->next = NULL;

        l->last = qprev;

    } else {

        l->first = NULL;

        l->last = NULL;

    }

    return r;

}

int htp_list_linked_push(htp_list_linked_t *l, void *e) {

    htp_list_linked_element_t *le = calloc(1, sizeof (htp_list_linked_element_t));

    if (le == NULL) return -1;

    // Remember the element

    le->data = e;

    // If the queue is empty, make this element first

    if (!l->first) {

        l->first = le;

    }

    if (l->last) {

        l->last->next = le;

    }

    l->last = le;

    return 1;

}

void *htp_list_linked_shift(htp_list_linked_t *l) {

    void *r = NULL;

    if (!l->first) {

        return NULL;

    }

    htp_list_linked_element_t *le = l->first;

    l->first = le->next;

    r = le->data;

    if (!l->first) {

        l->last = NULL;

    }

    free(le);

    return r;

}

#endif

#if 0

int main(int argc, char **argv) {

    htp_list_t *q = htp_list_array_create(4);

    htp_list_push(q, "1");

    htp_list_push(q, "2");

    htp_list_push(q, "3");

    htp_list_push(q, "4");

    htp_list_shift(q);

    htp_list_push(q, "5");

    htp_list_push(q, "6");

    char *s = NULL;

    while ((s = (char *) htp_list_pop(q)) != NULL) {

        printf("Got: %s\n", s);

    }

    printf("---\n");

    htp_list_push(q, "1");

    htp_list_push(q, "2");

    htp_list_push(q, "3");

    htp_list_push(q, "4");

    while ((s = (char *) htp_list_shift(q)) != NULL) {

        printf("Got: %s\n", s);

    }

    free(q);

    return 0;

}

#endif