/* -*- Mode: C; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
/* vim: set ts=2 et sw=2 tw=80: */
/*
Copyright (c) 2013 D. Richard Hipp
This program is free software; you can redistribute it and/or
modify it under the terms of the Simplified BSD License (also
known as the "2-Clause License" or "FreeBSD License".)
This program is distributed in the hope that it will be useful,
but without any warranty; without even the implied warranty of
merchantability or fitness for a particular purpose.
Author contact information:
drh@hwaci.com
http://www.hwaci.com/drh/
*****************************************************************************
This file houses the priority queue class.
*/
#include <assert.h>
#include "fossil-scm/fossil.h"
#include "fossil-scm/fossil-internal.h"
void fsl_pq_clear(fsl_pq *p){
fsl_free(p->list);
*p = fsl_pq_empty;
}
/*
Change the size of the queue so that it contains N slots
*/
static int fsl_pq_resize(fsl_pq *p, fsl_size_t N){
void * re = fsl_realloc(p->list, sizeof(fsl_pq_e)*N);
if(!re) return FSL_RC_OOM;
else{
p->list = (fsl_pq_e*)re;
p->capacity = N;
return 0;
}
}
/**
Insert element e into the queue.
*/
int fsl_pq_insert(fsl_pq *p, fsl_id_t e,
fsl_double_t v, void *pData){
fsl_size_t i, j;
if( p->used+1>p->capacity ){
int const rc = fsl_pq_resize(p, p->used+5);
if(rc) return rc;
}
for(i=0; i<p->used; ++i){
if( p->list[i].value>v ){
for(j=p->used; j>i; --j){
p->list[j] = p->list[j-1];
}
break;
}
}
p->list[i].id = e;
p->list[i].p = pData;
p->list[i].value = v;
++p->used;
return 0;
}
/**
Extract the first element from the queue (the element with
the smallest value) and return its ID. Return 0 if the queue
is empty. If pp is not NULL then *pp is (on success) assigned
to the value member of the extracted element.
*/
fsl_id_t fsl_pq_extract(fsl_pq *p, void **pp){
fsl_id_t e, i;
if( p->used==0 ){
if( pp ) *pp = 0;
return 0;
}
e = p->list[0].id;
if( pp ) *pp = p->list[0].p;
for(i=0; i<((fsl_id_t)p->used-1); ++i){
p->list[i] = p->list[i+1];
}
--p->used;
return e;
}