|
Packit Service |
20376f |
/*
|
|
Packit Service |
20376f |
* Copyright (C) the libgit2 contributors. All rights reserved.
|
|
Packit Service |
20376f |
*
|
|
Packit Service |
20376f |
* This file is part of libgit2, distributed under the GNU GPL v2 with
|
|
Packit Service |
20376f |
* a Linking Exception. For full terms see the included COPYING file.
|
|
Packit Service |
20376f |
*/
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
#include "pqueue.h"
|
|
Packit Service |
20376f |
#include "util.h"
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
#define PQUEUE_LCHILD_OF(I) (((I)<<1)+1)
|
|
Packit Service |
20376f |
#define PQUEUE_RCHILD_OF(I) (((I)<<1)+2)
|
|
Packit Service |
20376f |
#define PQUEUE_PARENT_OF(I) (((I)-1)>>1)
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
int git_pqueue_init(
|
|
Packit Service |
20376f |
git_pqueue *pq,
|
|
Packit Service |
20376f |
uint32_t flags,
|
|
Packit Service |
20376f |
size_t init_size,
|
|
Packit Service |
20376f |
git_vector_cmp cmp)
|
|
Packit Service |
20376f |
{
|
|
Packit Service |
20376f |
int error = git_vector_init(pq, init_size, cmp);
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
if (!error) {
|
|
Packit Service |
20376f |
/* mix in our flags */
|
|
Packit Service |
20376f |
pq->flags |= flags;
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
/* if fixed size heap, pretend vector is exactly init_size elements */
|
|
Packit Service |
20376f |
if ((flags & GIT_PQUEUE_FIXED_SIZE) && init_size > 0)
|
|
Packit Service |
20376f |
pq->_alloc_size = init_size;
|
|
Packit Service |
20376f |
}
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
return error;
|
|
Packit Service |
20376f |
}
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
static void pqueue_up(git_pqueue *pq, size_t el)
|
|
Packit Service |
20376f |
{
|
|
Packit Service |
20376f |
size_t parent_el = PQUEUE_PARENT_OF(el);
|
|
Packit Service |
20376f |
void *kid = git_vector_get(pq, el);
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
while (el > 0) {
|
|
Packit Service |
20376f |
void *parent = pq->contents[parent_el];
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
if (pq->_cmp(parent, kid) <= 0)
|
|
Packit Service |
20376f |
break;
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
pq->contents[el] = parent;
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
el = parent_el;
|
|
Packit Service |
20376f |
parent_el = PQUEUE_PARENT_OF(el);
|
|
Packit Service |
20376f |
}
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
pq->contents[el] = kid;
|
|
Packit Service |
20376f |
}
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
static void pqueue_down(git_pqueue *pq, size_t el)
|
|
Packit Service |
20376f |
{
|
|
Packit Service |
20376f |
void *parent = git_vector_get(pq, el), *kid, *rkid;
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
while (1) {
|
|
Packit Service |
20376f |
size_t kid_el = PQUEUE_LCHILD_OF(el);
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
if ((kid = git_vector_get(pq, kid_el)) == NULL)
|
|
Packit Service |
20376f |
break;
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
if ((rkid = git_vector_get(pq, kid_el + 1)) != NULL &&
|
|
Packit Service |
20376f |
pq->_cmp(kid, rkid) > 0) {
|
|
Packit Service |
20376f |
kid = rkid;
|
|
Packit Service |
20376f |
kid_el += 1;
|
|
Packit Service |
20376f |
}
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
if (pq->_cmp(parent, kid) <= 0)
|
|
Packit Service |
20376f |
break;
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
pq->contents[el] = kid;
|
|
Packit Service |
20376f |
el = kid_el;
|
|
Packit Service |
20376f |
}
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
pq->contents[el] = parent;
|
|
Packit Service |
20376f |
}
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
int git_pqueue_insert(git_pqueue *pq, void *item)
|
|
Packit Service |
20376f |
{
|
|
Packit Service |
20376f |
int error = 0;
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
/* if heap is full, pop the top element if new one should replace it */
|
|
Packit Service |
20376f |
if ((pq->flags & GIT_PQUEUE_FIXED_SIZE) != 0 &&
|
|
Packit Service |
20376f |
pq->length >= pq->_alloc_size)
|
|
Packit Service |
20376f |
{
|
|
Packit Service |
20376f |
/* skip this item if below min item in heap or if
|
|
Packit Service |
20376f |
* we do not have a comparison function */
|
|
Packit Service |
20376f |
if (!pq->_cmp || pq->_cmp(item, git_vector_get(pq, 0)) <= 0)
|
|
Packit Service |
20376f |
return 0;
|
|
Packit Service |
20376f |
/* otherwise remove the min item before inserting new */
|
|
Packit Service |
20376f |
(void)git_pqueue_pop(pq);
|
|
Packit Service |
20376f |
}
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
if (!(error = git_vector_insert(pq, item)) && pq->_cmp)
|
|
Packit Service |
20376f |
pqueue_up(pq, pq->length - 1);
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
return error;
|
|
Packit Service |
20376f |
}
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
void *git_pqueue_pop(git_pqueue *pq)
|
|
Packit Service |
20376f |
{
|
|
Packit Service |
20376f |
void *rval;
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
if (!pq->_cmp) {
|
|
Packit Service |
20376f |
rval = git_vector_last(pq);
|
|
Packit Service |
20376f |
} else {
|
|
Packit Service |
20376f |
rval = git_pqueue_get(pq, 0);
|
|
Packit Service |
20376f |
}
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
if (git_pqueue_size(pq) > 1 && pq->_cmp) {
|
|
Packit Service |
20376f |
/* move last item to top of heap, shrink, and push item down */
|
|
Packit Service |
20376f |
pq->contents[0] = git_vector_last(pq);
|
|
Packit Service |
20376f |
git_vector_pop(pq);
|
|
Packit Service |
20376f |
pqueue_down(pq, 0);
|
|
Packit Service |
20376f |
} else {
|
|
Packit Service |
20376f |
/* all we need to do is shrink the heap in this case */
|
|
Packit Service |
20376f |
git_vector_pop(pq);
|
|
Packit Service |
20376f |
}
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
return rval;
|
|
Packit Service |
20376f |
}
|