src/util/vector.h

   1 /*
   2  * Copyright (C) the libgit2 contributors. All rights reserved.
   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 #ifndef INCLUDE_vector_h__
   8 #define INCLUDE_vector_h__
   9
  10 #include "git2_util.h"
  11
  12 typedef int (*git_vector_cmp)(const void *, const void *);
  13
  14 enum {
  15         GIT_VECTOR_SORTED = (1u << 0),
  16         GIT_VECTOR_FLAG_MAX = (1u << 1)
  17 };
  18
  19 typedef struct git_vector {
  20         size_t _alloc_size;
  21         git_vector_cmp _cmp;
  22         void **contents;
  23         size_t length;
  24         uint32_t flags;
  25 } git_vector;
  26
  27 #define GIT_VECTOR_INIT {0}
  28
  29 GIT_WARN_UNUSED_RESULT int git_vector_init(
  30         git_vector *v, size_t initial_size, git_vector_cmp cmp);
  31 void git_vector_free(git_vector *v);
  32 void git_vector_free_deep(git_vector *v); /* free each entry and self */
  33 void git_vector_clear(git_vector *v);
  34 GIT_WARN_UNUSED_RESULT int git_vector_dup(
  35         git_vector *v, const git_vector *src, git_vector_cmp cmp);
  36 void git_vector_swap(git_vector *a, git_vector *b);
  37 int git_vector_size_hint(git_vector *v, size_t size_hint);
  38
  39 void **git_vector_detach(size_t *size, size_t *asize, git_vector *v);
  40
  41 void git_vector_sort(git_vector *v);
  42
  43 /** Linear search for matching entry using internal comparison function */
  44 int git_vector_search(size_t *at_pos, const git_vector *v, const void *entry);
  45
  46 /** Linear search for matching entry using explicit comparison function */
  47 int git_vector_search2(size_t *at_pos, const git_vector *v, git_vector_cmp cmp, const void *key);
  48
  49 /**
  50  * Binary search for matching entry using explicit comparison function that
  51  * returns position where item would go if not found.
  52  */
  53 int git_vector_bsearch2(
  54         size_t *at_pos, git_vector *v, git_vector_cmp cmp, const void *key);
  55
  56 /** Binary search for matching entry using internal comparison function */
  57 GIT_INLINE(int) git_vector_bsearch(size_t *at_pos, git_vector *v, const void *key)
  58 {
  59         return git_vector_bsearch2(at_pos, v, v->_cmp, key);
  60 }
  61
  62 GIT_INLINE(void *) git_vector_get(const git_vector *v, size_t position)
  63 {
  64         return (position < v->length) ? v->contents[position] : NULL;
  65 }
  66
  67 #define GIT_VECTOR_GET(V,I) ((I) < (V)->length ? (V)->contents[(I)] : NULL)
  68
  69 GIT_INLINE(size_t) git_vector_length(const git_vector *v)
  70 {
  71         return v->length;
  72 }
  73
  74 GIT_INLINE(void *) git_vector_last(const git_vector *v)
  75 {
  76         return (v->length > 0) ? git_vector_get(v, v->length - 1) : NULL;
  77 }
  78
  79 #define git_vector_foreach(v, iter, elem)       \
  80         for ((iter) = 0; (iter) < (v)->length && ((elem) = (v)->contents[(iter)], 1); (iter)++ )
  81
  82 #define git_vector_rforeach(v, iter, elem)      \
  83         for ((iter) = (v)->length - 1; (iter) < SIZE_MAX && ((elem) = (v)->contents[(iter)], 1); (iter)-- )
  84
  85 int git_vector_insert(git_vector *v, void *element);
  86 int git_vector_insert_sorted(git_vector *v, void *element,
  87         int (*on_dup)(void **old, void *new));
  88 int git_vector_remove(git_vector *v, size_t idx);
  89 void git_vector_pop(git_vector *v);
  90 void git_vector_uniq(git_vector *v, void  (*git_free_cb)(void *));
  91
  92 void git_vector_remove_matching(
  93         git_vector *v,
  94         int (*match)(const git_vector *v, size_t idx, void *payload),
  95         void *payload);
  96
  97 int git_vector_resize_to(git_vector *v, size_t new_length);
  98 int git_vector_insert_null(git_vector *v, size_t idx, size_t insert_len);
  99 int git_vector_remove_range(git_vector *v, size_t idx, size_t remove_len);
 100
 101 int git_vector_set(void **old, git_vector *v, size_t position, void *value);
 102
 103 /** Check if vector is sorted */
 104 #define git_vector_is_sorted(V) (((V)->flags & GIT_VECTOR_SORTED) != 0)
 105
 106 /** Directly set sorted state of vector */
 107 #define git_vector_set_sorted(V,S) do { \
 108         (V)->flags = (S) ? ((V)->flags | GIT_VECTOR_SORTED) : \
 109                 ((V)->flags & ~GIT_VECTOR_SORTED); } while (0)
 110
 111 /** Set the comparison function used for sorting the vector */
 112 GIT_INLINE(void) git_vector_set_cmp(git_vector *v, git_vector_cmp cmp)
 113 {
 114         if (cmp != v->_cmp) {
 115                 v->_cmp = cmp;
 116                 git_vector_set_sorted(v, 0);
 117         }
 118 }
 119
 120 /* Just use this in tests, not for realz. returns -1 if not sorted */
 121 int git_vector_verify_sorted(const git_vector *v);
 122
 123 /**
 124  * Reverse the vector in-place.
 125  */
 126 void git_vector_reverse(git_vector *v);
 127
 128 #endif