"Fossies" - the Fresh Open Source Software Archive

Member "mesa-20.1.8/src/gallium/auxiliary/util/u_idalloc.c" (16 Sep 2020, 2856 Bytes) of package /linux/misc/mesa-20.1.8.tar.xz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "u_idalloc.c" see the Fossies "Dox" file reference documentation.

    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 }