kern/include/smallidpool.h

   1 /* Copyright (c) 2015 Google Inc.
   2  * Ron Minnich <rminnich@google.com>
   3  * Barret Rhoden <brho@cs.berkeley.edu>
   4  *
   5  * Trivial thread-safe ID pool for small sets of things (< 64K)
   6  * implemented as a stack.
   7  */
   8
   9 #pragma once
  10
  11 #define MAX_U16_POOL_SZ (1 << 16)
  12
  13 #include <atomic.h>
  14
  15 /* IDS is the stack of 16 bit integers we give out.  TOS is the top of stack -
  16  * it is the index of the next slot that can be popped, if there are any.  It's
  17  * a u32 so it can be greater than a u16.
  18  *
  19  * All free slots in ids will be below the TOS, ranging from indexes [0, TOS),
  20  * where if TOS == 0, then there are no free slots to push.
  21  *
  22  * We can hand out u16s in the range [0, 65535].
  23  *
  24  * The check array is used instead of a bitfield because these architectures
  25  * suck at those. */
  26
  27 struct u16_pool {
  28         spinlock_t lock;
  29         uint32_t tos;
  30         uint16_t *ids;
  31         uint8_t *check;
  32         int size;
  33 };
  34
  35 struct u16_pool *create_u16_pool(unsigned int size);
  36 int get_u16(struct u16_pool *id);
  37 void put_u16(struct u16_pool *id, int v);