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