src/pqueue.h

   1 /*
   2  * Copyright (C) 2009-2013 the libgit2 contributors
   3  *
   4  * This file is part of libgit2, distributed under the GNU GPL v2 with
   5  * a Linking Exception. For full terms see the included COPYING file.
   6  *
   7  * This file is based on a modified version of the priority queue found
   8  * in the Apache project and libpqueue library.
   9  *
  10  * https://github.com/vy/libpqueue
  11  *
  12  * Original file notice:
  13  *
  14  * Copyright 2010 Volkan Yazici <volkan.yazici@gmail.com>
  15  * Copyright 2006-2010 The Apache Software Foundation
  16  *
  17  * Licensed under the Apache License, Version 2.0 (the "License"); you may not
  18  * use this file except in compliance with the License. You may obtain a copy of
  19  * the License at
  20  *
  21  *     http://www.apache.org/licenses/LICENSE-2.0
  22  *
  23  * Unless required by applicable law or agreed to in writing, software
  24  * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
  25  * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
  26  * License for the specific language governing permissions and limitations under
  27  * the License.
  28  */
  29
  30 #ifndef INCLUDE_pqueue_h__
  31 #define INCLUDE_pqueue_h__
  32
  33 /** callback functions to get/set/compare the priority of an element */
  34 typedef int (*git_pqueue_cmp)(void *a, void *b);
  35
  36 /** the priority queue handle */
  37 typedef struct {
  38         size_t size, avail, step;
  39         git_pqueue_cmp cmppri;
  40         void **d;
  41 } git_pqueue;
  42
  43
  44 /**
  45  * initialize the queue
  46  *
  47  * @param n the initial estimate of the number of queue items for which memory
  48  *                      should be preallocated
  49  * @param cmppri the callback function to compare two nodes of the queue
  50  *
  51  * @Return the handle or NULL for insufficent memory
  52  */
  53 int git_pqueue_init(git_pqueue *q, size_t n, git_pqueue_cmp cmppri);
  54
  55
  56 /**
  57  * free all memory used by the queue
  58  * @param q the queue
  59  */
  60 void git_pqueue_free(git_pqueue *q);
  61
  62 /**
  63  * clear all the elements in the queue
  64  * @param q the queue
  65  */
  66 void git_pqueue_clear(git_pqueue *q);
  67
  68 /**
  69  * return the size of the queue.
  70  * @param q the queue
  71  */
  72 size_t git_pqueue_size(git_pqueue *q);
  73
  74
  75 /**
  76  * insert an item into the queue.
  77  * @param q the queue
  78  * @param d the item
  79  * @return 0 on success
  80  */
  81 int git_pqueue_insert(git_pqueue *q, void *d);
  82
  83
  84 /**
  85  * pop the highest-ranking item from the queue.
  86  * @param p the queue
  87  * @param d where to copy the entry to
  88  * @return NULL on error, otherwise the entry
  89  */
  90 void *git_pqueue_pop(git_pqueue *q);
  91
  92
  93 /**
  94  * access highest-ranking item without removing it.
  95  * @param q the queue
  96  * @param d the entry
  97  * @return NULL on error, otherwise the entry
  98  */
  99 void *git_pqueue_peek(git_pqueue *q);
 100
 101 #endif /* PQUEUE_H */
 102 /** @} */
 103