reftable/basics.c

   1 /*
   2 Copyright 2020 Google LLC
   3
   4 Use of this source code is governed by a BSD-style
   5 license that can be found in the LICENSE file or at
   6 https://developers.google.com/open-source/licenses/bsd
   7 */
   8
   9 #define REFTABLE_ALLOW_BANNED_ALLOCATORS
  10 #include "basics.h"
  11 #include "reftable-basics.h"
  12 #include "reftable-error.h"
  13
  14 static void *(*reftable_malloc_ptr)(size_t sz);
  15 static void *(*reftable_realloc_ptr)(void *, size_t);
  16 static void (*reftable_free_ptr)(void *);
  17
  18 void *reftable_malloc(size_t sz)
  19 {
  20         if (reftable_malloc_ptr)
  21                 return (*reftable_malloc_ptr)(sz);
  22         return malloc(sz);
  23 }
  24
  25 void *reftable_realloc(void *p, size_t sz)
  26 {
  27         if (reftable_realloc_ptr)
  28                 return (*reftable_realloc_ptr)(p, sz);
  29         return realloc(p, sz);
  30 }
  31
  32 void reftable_free(void *p)
  33 {
  34         if (reftable_free_ptr)
  35                 reftable_free_ptr(p);
  36         else
  37                 free(p);
  38 }
  39
  40 void *reftable_calloc(size_t nelem, size_t elsize)
  41 {
  42         void *p;
  43
  44         if (nelem && elsize > SIZE_MAX / nelem)
  45                 return NULL;
  46
  47         p = reftable_malloc(nelem * elsize);
  48         if (!p)
  49                 return NULL;
  50
  51         memset(p, 0, nelem * elsize);
  52         return p;
  53 }
  54
  55 char *reftable_strdup(const char *str)
  56 {
  57         size_t len = strlen(str);
  58         char *result = reftable_malloc(len + 1);
  59         if (!result)
  60                 return NULL;
  61         memcpy(result, str, len + 1);
  62         return result;
  63 }
  64
  65 void reftable_set_alloc(void *(*malloc)(size_t),
  66                         void *(*realloc)(void *, size_t), void (*free)(void *))
  67 {
  68         reftable_malloc_ptr = malloc;
  69         reftable_realloc_ptr = realloc;
  70         reftable_free_ptr = free;
  71 }
  72
  73 void reftable_buf_init(struct reftable_buf *buf)
  74 {
  75         struct reftable_buf empty = REFTABLE_BUF_INIT;
  76         *buf = empty;
  77 }
  78
  79 void reftable_buf_release(struct reftable_buf *buf)
  80 {
  81         reftable_free(buf->buf);
  82         reftable_buf_init(buf);
  83 }
  84
  85 void reftable_buf_reset(struct reftable_buf *buf)
  86 {
  87         if (buf->alloc) {
  88                 buf->len = 0;
  89                 buf->buf[0] = '\0';
  90         }
  91 }
  92
  93 int reftable_buf_setlen(struct reftable_buf *buf, size_t len)
  94 {
  95         if (len > buf->len)
  96                 return -1;
  97         if (len == buf->len)
  98                 return 0;
  99         buf->buf[len] = '\0';
 100         buf->len = len;
 101         return 0;
 102 }
 103
 104 int reftable_buf_cmp(const struct reftable_buf *a, const struct reftable_buf *b)
 105 {
 106         size_t len = a->len < b->len ? a->len : b->len;
 107         if (len) {
 108                 int cmp = memcmp(a->buf, b->buf, len);
 109                 if (cmp)
 110                         return cmp;
 111         }
 112         return a->len < b->len ? -1 : a->len != b->len;
 113 }
 114
 115 int reftable_buf_add(struct reftable_buf *buf, const void *data, size_t len)
 116 {
 117         size_t newlen = buf->len + len;
 118
 119         if (newlen + 1 > buf->alloc) {
 120                 char *reallocated = buf->buf;
 121                 REFTABLE_ALLOC_GROW(reallocated, newlen + 1, buf->alloc);
 122                 if (!reallocated)
 123                         return REFTABLE_OUT_OF_MEMORY_ERROR;
 124                 buf->buf = reallocated;
 125         }
 126
 127         memcpy(buf->buf + buf->len, data, len);
 128         buf->buf[newlen] = '\0';
 129         buf->len = newlen;
 130
 131         return 0;
 132 }
 133
 134 int reftable_buf_addstr(struct reftable_buf *buf, const char *s)
 135 {
 136         return reftable_buf_add(buf, s, strlen(s));
 137 }
 138
 139 char *reftable_buf_detach(struct reftable_buf *buf)
 140 {
 141         char *result = buf->buf;
 142         reftable_buf_init(buf);
 143         return result;
 144 }
 145
 146 void put_be24(uint8_t *out, uint32_t i)
 147 {
 148         out[0] = (uint8_t)((i >> 16) & 0xff);
 149         out[1] = (uint8_t)((i >> 8) & 0xff);
 150         out[2] = (uint8_t)(i & 0xff);
 151 }
 152
 153 uint32_t get_be24(uint8_t *in)
 154 {
 155         return (uint32_t)(in[0]) << 16 | (uint32_t)(in[1]) << 8 |
 156                (uint32_t)(in[2]);
 157 }
 158
 159 void put_be16(uint8_t *out, uint16_t i)
 160 {
 161         out[0] = (uint8_t)((i >> 8) & 0xff);
 162         out[1] = (uint8_t)(i & 0xff);
 163 }
 164
 165 size_t binsearch(size_t sz, int (*f)(size_t k, void *args), void *args)
 166 {
 167         size_t lo = 0;
 168         size_t hi = sz;
 169
 170         /* Invariants:
 171          *
 172          *  (hi == sz) || f(hi) == true
 173          *  (lo == 0 && f(0) == true) || fi(lo) == false
 174          */
 175         while (hi - lo > 1) {
 176                 size_t mid = lo + (hi - lo) / 2;
 177                 int ret = f(mid, args);
 178                 if (ret < 0)
 179                         return sz;
 180
 181                 if (ret > 0)
 182                         hi = mid;
 183                 else
 184                         lo = mid;
 185         }
 186
 187         if (lo)
 188                 return hi;
 189
 190         return f(0, args) ? 0 : 1;
 191 }
 192
 193 void free_names(char **a)
 194 {
 195         char **p;
 196         if (!a) {
 197                 return;
 198         }
 199         for (p = a; *p; p++) {
 200                 reftable_free(*p);
 201         }
 202         reftable_free(a);
 203 }
 204
 205 size_t names_length(const char **names)
 206 {
 207         const char **p = names;
 208         while (*p)
 209                 p++;
 210         return p - names;
 211 }
 212
 213 char **parse_names(char *buf, int size)
 214 {
 215         char **names = NULL;
 216         size_t names_cap = 0;
 217         size_t names_len = 0;
 218         char *p = buf;
 219         char *end = buf + size;
 220
 221         while (p < end) {
 222                 char *next = strchr(p, '\n');
 223                 if (next && next < end) {
 224                         *next = 0;
 225                 } else {
 226                         next = end;
 227                 }
 228                 if (p < next) {
 229                         char **names_grown = names;
 230                         REFTABLE_ALLOC_GROW(names_grown, names_len + 1, names_cap);
 231                         if (!names_grown)
 232                                 goto err;
 233                         names = names_grown;
 234
 235                         names[names_len] = reftable_strdup(p);
 236                         if (!names[names_len++])
 237                                 goto err;
 238                 }
 239                 p = next + 1;
 240         }
 241
 242         REFTABLE_REALLOC_ARRAY(names, names_len + 1);
 243         names[names_len] = NULL;
 244
 245         return names;
 246
 247 err:
 248         for (size_t i = 0; i < names_len; i++)
 249                 reftable_free(names[i]);
 250         reftable_free(names);
 251         return NULL;
 252 }
 253
 254 int names_equal(const char **a, const char **b)
 255 {
 256         size_t i = 0;
 257         for (; a[i] && b[i]; i++)
 258                 if (strcmp(a[i], b[i]))
 259                         return 0;
 260         return a[i] == b[i];
 261 }
 262
 263 int common_prefix_size(struct reftable_buf *a, struct reftable_buf *b)
 264 {
 265         int p = 0;
 266         for (; p < a->len && p < b->len; p++) {
 267                 if (a->buf[p] != b->buf[p])
 268                         break;
 269         }
 270
 271         return p;
 272 }
 273
 274 int hash_size(uint32_t id)
 275 {
 276         switch (id) {
 277         case 0:
 278         case GIT_SHA1_FORMAT_ID:
 279                 return GIT_SHA1_RAWSZ;
 280         case GIT_SHA256_FORMAT_ID:
 281                 return GIT_SHA256_RAWSZ;
 282         }
 283         abort();
 284 }