src/util/sparse_array.h

   1 /*
   2  * Copyright © 2019 Intel Corporation
   3  *
   4  * Permission is hereby granted, free of charge, to any person obtaining a
   5  * copy of this software and associated documentation files (the "Software"),
   6  * to deal in the Software without restriction, including without limitation
   7  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
   8  * and/or sell copies of the Software, and to permit persons to whom the
   9  * Software is furnished to do so, subject to the following conditions:
  10  *
  11  * The above copyright notice and this permission notice (including the next
  12  * paragraph) shall be included in all copies or substantial portions of the
  13  * Software.
  14  *
  15  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  16  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  17  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
  18  * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  19  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
  20  * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
  21  * IN THE SOFTWARE.
  22  */
  23
  24 #ifndef _UTIL_SPARSE_ARRAY_H
  25 #define _UTIL_SPARSE_ARRAY_H
  26
  27 #include <stdint.h>
  28
  29 #include "c11/threads.h"
  30 #include "macros.h"
  31 #include "u_atomic.h"
  32 #include "u_math.h"
  33
  34 #ifdef __cplusplus
  35 extern "C" {
  36 #endif
  37
  38 struct util_sparse_array_node;
  39
  40 /** A thread-safe automatically growing sparse array data structure
  41  *
  42  * This data structure has the following very nice properties:
  43  *
  44  *  1. Accessing an element is basically constant time.  Technically, it's
  45  *     O(log_b n) where the base b is the node size and n is the maximum
  46  *     index.  However, node sizes are expected to be fairly large and the
  47  *     index is a uint64_t so, if your node size is 256, it's O(8).
  48  *
  49  *  2. The data stored in the array is never moved in memory.  Instead, the
  50  *     data structure only ever grows and new nodes are added as-needed.  This
  51  *     means it's safe to store a pointer to something stored in the sparse
  52  *     array without worrying about a realloc invalidating it.
  53  *
  54  *  3. The data structure is thread-safe.  No guarantees are made about the
  55  *     data stored in the sparse array but it is safe to call
  56  *     util_sparse_array_get(arr, idx) from as many threads as you'd like and
  57  *     we guarantee that two calls to util_sparse_array_get(arr, idx) with the
  58  *     same array and index will always return the same pointer regardless
  59  *     contention between threads.
  60  *
  61  *  4. The data structure is lock-free.  All manipulations of the tree are
  62  *     done by a careful use of atomics to maintain thread safety and no locks
  63  *     are ever taken other than those taken implicitly by calloc().  If no
  64  *     allocation is required, util_sparse_array_get(arr, idx) does a simple
  65  *     walk over the tree should be efficient even in the case where many
  66  *     threads are accessing the sparse array at once.
  67  */
  68 struct util_sparse_array {
  69    size_t elem_size;
  70    unsigned node_size_log2;
  71
  72    struct util_sparse_array_node *root;
  73 };
  74
  75 void util_sparse_array_init(struct util_sparse_array *arr,
  76                             size_t elem_size, size_t node_size);
  77
  78 void util_sparse_array_finish(struct util_sparse_array *arr);
  79
  80 void *util_sparse_array_get(struct util_sparse_array *arr, uint64_t idx);
  81
  82 void util_sparse_array_validate(struct util_sparse_array *arr);
  83
  84 #ifdef __cplusplus
  85 } /* extern C */
  86 #endif
  87
  88 #endif /* _UTIL_SPARSE_ARRAY_H */