src/array.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_array_h__
   8 #define INCLUDE_array_h__
   9
  10 #include "common.h"
  11
  12 /*
  13  * Use this to declare a typesafe resizable array of items, a la:
  14  *
  15  *     git_array_t(int) my_ints = GIT_ARRAY_INIT;
  16  *     ...
  17  *     int *i = git_array_alloc(my_ints);
  18  *     GIT_ERROR_CHECK_ALLOC(i);
  19  *     ...
  20  *     git_array_clear(my_ints);
  21  *
  22  * You may also want to do things like:
  23  *
  24  *     typedef git_array_t(my_struct) my_struct_array_t;
  25  */
  26 #define git_array_t(type) struct { type *ptr; size_t size, asize; }
  27
  28 #define GIT_ARRAY_INIT { NULL, 0, 0 }
  29
  30 #define git_array_init(a) \
  31         do { (a).size = (a).asize = 0; (a).ptr = NULL; } while (0)
  32
  33 #define git_array_init_to_size(a, desired) \
  34         do { (a).size = 0; (a).asize = desired; (a).ptr = git__calloc(desired, sizeof(*(a).ptr)); } while (0)
  35
  36 #define git_array_clear(a) \
  37         do { git__free((a).ptr); git_array_init(a); } while (0)
  38
  39 #define GIT_ERROR_CHECK_ARRAY(a) GIT_ERROR_CHECK_ALLOC((a).ptr)
  40
  41
  42 typedef git_array_t(char) git_array_generic_t;
  43
  44 /* use a generic array for growth so this can return the new item */
  45 GIT_INLINE(void *) git_array_grow(void *_a, size_t item_size)
  46 {
  47         volatile git_array_generic_t *a = _a;
  48         size_t new_size;
  49         char *new_array;
  50
  51         if (a->size < 8) {
  52                 new_size = 8;
  53         } else {
  54                 if (GIT_MULTIPLY_SIZET_OVERFLOW(&new_size, a->size, 3))
  55                         goto on_oom;
  56                 new_size /= 2;
  57         }
  58
  59         if ((new_array = git__reallocarray(a->ptr, new_size, item_size)) == NULL)
  60                 goto on_oom;
  61
  62         a->ptr = new_array; a->asize = new_size; a->size++;
  63         return a->ptr + (a->size - 1) * item_size;
  64
  65 on_oom:
  66         git_array_clear(*a);
  67         return NULL;
  68 }
  69
  70 #define git_array_alloc(a) \
  71         (((a).size >= (a).asize) ? \
  72         git_array_grow(&(a), sizeof(*(a).ptr)) : \
  73         ((a).ptr ? &(a).ptr[(a).size++] : NULL))
  74
  75 #define git_array_last(a) ((a).size ? &(a).ptr[(a).size - 1] : NULL)
  76
  77 #define git_array_pop(a) ((a).size ? &(a).ptr[--(a).size] : NULL)
  78
  79 #define git_array_get(a, i) (((i) < (a).size) ? &(a).ptr[(i)] : NULL)
  80
  81 #define git_array_size(a) (a).size
  82
  83 #define git_array_valid_index(a, i) ((i) < (a).size)
  84
  85 #define git_array_foreach(a, i, element) \
  86         for ((i) = 0; (i) < (a).size && ((element) = &(a).ptr[(i)]); (i)++)
  87
  88 GIT_INLINE(int) git_array__search(
  89         size_t *out,
  90         void *array_ptr,
  91         size_t item_size,
  92         size_t array_len,
  93         int (*compare)(const void *, const void *),
  94         const void *key)
  95 {
  96         size_t lim;
  97         unsigned char *part, *array = array_ptr, *base = array_ptr;
  98         int cmp = -1;
  99
 100         for (lim = array_len; lim != 0; lim >>= 1) {
 101                 part = base + (lim >> 1) * item_size;
 102                 cmp = (*compare)(key, part);
 103
 104                 if (cmp == 0) {
 105                         base = part;
 106                         break;
 107                 }
 108                 if (cmp > 0) { /* key > p; take right partition */
 109                         base = part + 1 * item_size;
 110                         lim--;
 111                 } /* else take left partition */
 112         }
 113
 114         if (out)
 115                 *out = (base - array) / item_size;
 116
 117         return (cmp == 0) ? 0 : GIT_ENOTFOUND;
 118 }
 119
 120 #define git_array_search(out, a, cmp, key) \
 121         git_array__search(out, (a).ptr, sizeof(*(a).ptr), (a).size, \
 122                 (cmp), (key))
 123
 124 #endif