src/gallium/auxiliary/util/u_idalloc.c

   1 /**************************************************************************
   2  *
   3  * Copyright 2017 Valve Corporation
   4  * All Rights Reserved.
   5  *
   6  * Permission is hereby granted, free of charge, to any person obtaining a
   7  * copy of this software and associated documentation files (the
   8  * "Software"), to deal in the Software without restriction, including
   9  * without limitation the rights to use, copy, modify, merge, publish,
  10  * distribute, sub license, and/or sell copies of the Software, and to
  11  * permit persons to whom the Software is furnished to do so, subject to
  12  * the following conditions:
  13  *
  14  * The above copyright notice and this permission notice (including the
  15  * next paragraph) shall be included in all copies or substantial portions
  16  * of the Software.
  17  *
  18  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
  19  * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  20  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT.
  21  * IN NO EVENT SHALL THE AUTHORS AND/OR ITS SUPPLIERS BE LIABLE FOR
  22  * ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
  23  * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
  24  * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  25  *
  26  **************************************************************************/
  27
  28 /**
  29  * @file
  30  * A simple allocator that allocates and release "numbers".
  31  *
  32  * @author Samuel Pitoiset <samuel.pitoiset@gmail.com>
  33  */
  34
  35 #include "util/u_idalloc.h"
  36 #include "util/u_math.h"
  37 #include <stdlib.h>
  38
  39 void
  40 util_idalloc_init(struct util_idalloc *buf)
  41 {
  42    memset(buf, 0, sizeof(*buf));
  43 }
  44
  45 void
  46 util_idalloc_fini(struct util_idalloc *buf)
  47 {
  48    if (buf->data)
  49       free(buf->data);
  50 }
  51
  52 void
  53 util_idalloc_resize(struct util_idalloc *buf, unsigned new_num_elements)
  54 {
  55    new_num_elements = align(new_num_elements, 32);
  56
  57    if (new_num_elements > buf->num_elements) {
  58       unsigned i;
  59
  60       buf->data = realloc(buf->data,
  61                           (new_num_elements / 32) * sizeof(*buf->data));
  62
  63       for (i = buf->num_elements / 32; i < new_num_elements / 32; i++)
  64          buf->data[i] = 0;
  65       buf->num_elements = new_num_elements;
  66    }
  67 }
  68
  69 unsigned
  70 util_idalloc_alloc(struct util_idalloc *buf)
  71 {
  72    unsigned num_elements = buf->num_elements;
  73
  74    for (unsigned i = 0; i < num_elements / 32; i++) {
  75       if (buf->data[i] == 0xffffffff)
  76          continue;
  77
  78       unsigned bit = ffs(~buf->data[i]) - 1;
  79       buf->data[i] |= 1u << bit;
  80       return i * 32 + bit;
  81    }
  82
  83    /* No slots available, resize and return the first free. */
  84    util_idalloc_resize(buf, num_elements * 2);
  85
  86    buf->data[num_elements / 32] |= 1 << (num_elements % 32);
  87
  88    return num_elements;
  89 }
  90
  91 void
  92 util_idalloc_free(struct util_idalloc *buf, unsigned id)
  93 {
  94    assert(id < buf->num_elements);
  95    buf->data[id / 32] &= ~(1 << (id % 32));
  96 }