Skip to content

Instantly share code, notes, and snippets.

@cloudwu
Last active August 29, 2024 03:36
Show Gist options
  • Save cloudwu/dcbf583f7034ef6c0f8adec3f76860f0 to your computer and use it in GitHub Desktop.
Save cloudwu/dcbf583f7034ef6c0f8adec3f76860f0 to your computer and use it in GitHub Desktop.
Unique handle
#include "handle.h"
#include <stdlib.h>
#include <assert.h>
#include <string.h>
#define HANDLE_USED 0x80000000
size_t
handle_size(int bits) {
int n = 1 << bits;
return sizeof(struct handle) + sizeof(unsigned int) * (n - 1);
}
void
handle_init(struct handle *H, struct handle *old, int bits, size_t sz) {
assert(sz >= handle_size(bits));
int n = (1 << bits);
H->bits = bits;
if (old == NULL) {
int i;
for (i=1;i<n-1;i++) {
H->h[i] = i+1;
}
H->h[0] = 1 + n;
H->h[n-1] = 0;
H->freelist = 0;
} else {
assert(bits > old->bits);
int c = 1 << (bits - old->bits);
memset(H->h, 0, sizeof(unsigned int) * n);
int i;
// rehash
int old_n = 1 << old->bits;
int mask = (1 << H->bits) - 1;
int old_mask = old_n -1;
for (i=0;i<old_n;i++) {
unsigned int v = old->h[i];
if (v & HANDLE_USED) {
int index = v & mask;
H->h[index] = v;
// mark lower slots
unsigned int base = ((v & ~HANDLE_USED) & ~mask);
int old_index = index & old_mask;
int j;
for (j = 0; j < c ; j++) {
if (old_index < index) {
H->h[old_index] = base + mask + 1;
} else if (old_index > index) {
H->h[old_index] = base;
}
old_index += old_mask + 1;
}
}
}
// link free
int free_head = -1;
int free_current = -1;
for (i=0;i<n;i++) {
if (!(H->h[i] & HANDLE_USED)) {
if (free_head < 0) {
free_head = free_current = i;
} else {
H->h[free_current] |= i;
free_current = i;
}
}
}
// set free list
H->h[free_current] = free_head;
H->freelist = free_head;
}
}
unsigned int
handle_new(struct handle *H) {
int free_node = H->freelist;
unsigned int v = H->h[free_node];
if (v & HANDLE_USED)
return 0;
int mask = (1 << H->bits) - 1;
int next = v & mask;
unsigned int next_v = H->h[next];
H->h[free_node] = (v & ~mask) | (next_v & mask);
unsigned int r = (next_v & ~mask) | next;
H->h[next] = r | HANDLE_USED;
return r;
}
// 0 succ
int
handle_import(struct handle *H, unsigned int id, int invalid) {
int mask = (1 << H->bits) - 1;
int index = id & mask;
unsigned int v = H->h[index];
if (v & HANDLE_USED)
return -1;
if (invalid) {
if ((id & ~mask) > (v & ~mask)) {
H->h[index] = (id & ~mask) | (v & mask);
}
} else {
// remove index
int prev = H->freelist;
int next;
while ((next = H->h[prev] & mask) != index) {
prev = next;
}
H->h[prev] = (H->h[prev] & ~mask) | (v & mask);
H->h[index] = id | HANDLE_USED;
}
return 0;
}
int
handle_invalid(struct handle *H, unsigned int id) {
int mask = (1 << H->bits) - 1;
return H->h[id & mask] != (id | HANDLE_USED);
}
void
handle_remove(struct handle *H, unsigned int id) {
if (handle_invalid(H, id))
return;
int mask = (1 << H->bits) - 1;
int inc = mask + 1;
id = (id + inc) & ~HANDLE_USED;
if (id == 0)
id = inc;
int index = id & mask;
unsigned int last = H->h[H->freelist];
if (last & HANDLE_USED) {
// full
H->freelist = index;
H->h[index] = (id & ~mask) | index;
} else {
int next = last & mask;
H->h[H->freelist] = (last & ~mask) | index;
H->h[index] = (id & ~mask) | next;
H->freelist = index;
}
}
unsigned int
handle_each(struct handle *H, unsigned int last) {
int n = 1 << H->bits;
if (last == 0) {
// first
int i;
for (i=0;i<n;i++) {
unsigned int v = H->h[i];
if (v & HANDLE_USED) {
return v & ~HANDLE_USED;
}
}
return 0;
}
int mask = (1 << H->bits) - 1;
int index = last & mask;
while (++index < n) {
unsigned int v = H->h[index];
if (v & HANDLE_USED) {
return v & ~HANDLE_USED;
}
}
return 0;
}
unsigned int
handle_each_available(struct handle *H, unsigned int last) {
int mask = (1 << H->bits) - 1;
if (last == 0) {
// first
unsigned int v = H->h[H->freelist];
if (v & HANDLE_USED)
return 0;
return (v & ~mask) | H->freelist;
}
int index = last & mask;
unsigned int v = H->h[index];
if (v & HANDLE_USED)
return 0;
int next = v & mask;
if (next == H->freelist)
return 0;
v = H->h[next];
return (v & ~mask) | next;
}
unsigned int
handle_index(struct handle *H, int index) {
int mask = (1 << H->bits) - 1;
return H->h[index & mask];
}
#ifdef TEST_HANDLE_MAIN
#include <stdio.h>
static void
print_handle(struct handle *H) {
printf("FREE ");
unsigned int id = 0;
while ((id = handle_each_available(H, id))) {
printf("%u ", id);
}
printf("\n");
printf("USED ");
id = 0;
while ((id = handle_each(H, id))) {
printf("%u ", id);
}
printf("\n");
}
int
main() {
size_t sz = handle_size(2);
struct handle *H = malloc(sz);
handle_init(H, NULL, 2, sz);
print_handle(H);
int i;
for (i=0;i<4;i++) {
unsigned int v = handle_new(H);
printf("Alloc %u\n", v);
print_handle(H);
}
unsigned int id = 1;
for (i=0;i<4;i++) {
handle_remove(H, id);
unsigned int old_id = id;
id = handle_new(H);
printf("Realloc %d->%d\n", old_id, id);
}
print_handle(H);
sz = handle_size(4);
struct handle *H2 = malloc(sz);
handle_init(H2, H, 4, sz);
print_handle(H2);
for (i=0;i<8;i++) {
unsigned int v = handle_new(H2);
printf("Alloc %u\n", v);
print_handle(H2);
}
printf("COPY handles\n");
struct handle *H3 = malloc(sz);
handle_init(H3, NULL, 4, sz);
print_handle(H3);
unsigned int iter = 0;
while ((iter = handle_each(H2, iter))) {
handle_import(H3, iter, 0);
}
print_handle(H3);
while ((iter = handle_each_available(H2, iter))) {
handle_import(H3, iter, 1);
}
print_handle(H3);
return 0;
}
#endif
#ifndef object_handle_h
#define object_handle_h
#include <stddef.h>
struct handle {
int bits;
int freelist;
unsigned int h[1];
};
size_t handle_size(int bits);
void handle_init(struct handle *H, struct handle *old, int bits, size_t sz);
unsigned int handle_new(struct handle *H);
int handle_import(struct handle *H, unsigned int id, int invalid); // 0 succ
unsigned int handle_index(struct handle *H, int index);
int handle_invalid(struct handle *H, unsigned int id);
void handle_remove(struct handle *H, unsigned int id);
unsigned int handle_each(struct handle *H, unsigned int last);
unsigned int handle_each_available(struct handle *H, unsigned int last);
#endif
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment