#define CDS_JA_RANGE_KEY_BITS 64
+enum cds_ja_range_type {
+ CDS_JA_RANGE_ALLOCATED,
+ CDS_JA_RANGE_FREE,
+ CDS_JA_RANGE_REMOVED,
+};
+
+/*
+ * Range goes from start (inclusive) to end (inclusive).
+ * Range start is used as node key in the Judy array.
+ */
+struct cds_ja_range {
+ uint64_t end;
+ struct cds_ja_node ja_node;
+ pthread_mutex_t lock;
+ void *priv;
+ enum cds_ja_range_type type;
+
+ /* not required on lookup fast-path */
+ uint64_t start;
+ struct rcu_head head;
+};
+
struct cds_ja_range *cds_ja_range_lookup(struct cds_ja *ja, uint64_t key)
{
struct cds_ja_node *node, *last_node;
struct cds_ja_range *range_create(
uint64_t start, /* inclusive */
uint64_t end, /* inclusive */
+ void *priv,
enum cds_ja_range_type type)
{
struct cds_ja_range *range;
return NULL;
range->start = start;
range->end = end;
+ range->priv = priv;
range->type = type;
pthread_mutex_init(&range->lock, NULL);
return range;
free_range_cb);
}
-struct cds_ja_range *cds_ja_range_add(struct cds_ja *ja,
+int cds_ja_range_add(struct cds_ja *ja,
uint64_t start, /* inclusive */
- uint64_t end) /* inclusive */
+ uint64_t end, /* inclusive */
+ void *priv)
{
struct cds_ja_node *old_node, *old_node_end;
struct cds_ja_range *old_range, *old_range_end, *new_range, *ranges[3];
old_range = caa_container_of(old_node, struct cds_ja_range, ja_node);
switch (CMM_LOAD_SHARED(old_range->type)) {
case CDS_JA_RANGE_ALLOCATED:
- return NULL;
+ return -EEXIST;
case CDS_JA_RANGE_FREE:
break;
case CDS_JA_RANGE_REMOVED:
switch (CMM_LOAD_SHARED(old_range->type)) {
case CDS_JA_RANGE_ALLOCATED:
case CDS_JA_RANGE_FREE: /* fall-through */
- return NULL;
+ return -EEXIST;
case CDS_JA_RANGE_REMOVED:
goto retry;
}
if (end == old_range->end) {
/* 1 range */
ranges[0] = new_range = range_create(start, end,
- CDS_JA_RANGE_ALLOCATED);
+ priv, CDS_JA_RANGE_ALLOCATED);
nr_ranges = 1;
} else {
/* 2 ranges */
ranges[0] = new_range = range_create(start, end,
- CDS_JA_RANGE_ALLOCATED);
+ priv, CDS_JA_RANGE_ALLOCATED);
ranges[1] = range_create(end + 1, old_range->end,
- CDS_JA_RANGE_FREE);
+ NULL, CDS_JA_RANGE_FREE);
nr_ranges = 2;
}
} else {
if (end == old_range->end) {
/* 2 ranges */
ranges[0] = range_create(old_range->start, start - 1,
- CDS_JA_RANGE_FREE);
+ NULL, CDS_JA_RANGE_FREE);
ranges[1] = new_range = range_create(start, end,
- CDS_JA_RANGE_ALLOCATED);
+ priv, CDS_JA_RANGE_ALLOCATED);
nr_ranges = 2;
} else {
/* 3 ranges */
ranges[0] = range_create(old_range->start, start - 1,
- CDS_JA_RANGE_FREE);
+ NULL, CDS_JA_RANGE_FREE);
ranges[1] = new_range = range_create(start, end,
- CDS_JA_RANGE_ALLOCATED);
+ priv, CDS_JA_RANGE_ALLOCATED);
ranges[2] = range_create(end + 1, old_range->end,
- CDS_JA_RANGE_FREE);
+ NULL, CDS_JA_RANGE_FREE);
nr_ranges = 3;
}
}
rcu_free_range(ja, old_range);
- return new_range;
+ return 0;
}
int cds_ja_range_del(struct cds_ja *ja, struct cds_ja_range *range)
/* Create new free range */
start = merge_ranges[0]->start;
end = merge_ranges[nr_merge - 1]->end;
- new_range = range_create(start, end, CDS_JA_RANGE_FREE);
+ new_range = range_create(start, end, NULL, CDS_JA_RANGE_FREE);
ret = cds_ja_add(ja, start, &new_range->ja_node);
assert(!ret);
ja = _cds_ja_new(CDS_JA_RANGE_KEY_BITS, flavor);
if (!ja)
return NULL;
- range = range_create(0, UINT64_MAX, CDS_JA_RANGE_FREE);
+ range = range_create(0, UINT64_MAX, NULL, CDS_JA_RANGE_FREE);
if (!range)
goto free_ja;
+ cds_lfht_rcu_flavor(ja->ht)->read_lock();
ret = cds_ja_add(ja, 0, &range->ja_node);
+ cds_lfht_rcu_flavor(ja->ht)->read_unlock();
if (ret)
goto free_range;
return ja;
return NULL;
}
-int cds_ja_range_destroy(struct cds_ja *ja)
+int cds_ja_range_destroy(struct cds_ja *ja,
+ void (*free_priv)(void *ptr))
{
uint64_t key;
struct cds_ja_node *ja_node;
int ret = 0;
+ cds_lfht_rcu_flavor(ja->ht)->read_lock();
cds_ja_for_each_key_rcu(ja, key, ja_node) {
struct cds_ja_node *tmp_node;
ret = cds_ja_del(ja, key, &range->ja_node);
if (ret)
goto error;
+ if (free_priv)
+ free_priv(range->priv);
/* Alone using Judy array, OK to free now */
free_range(range);
}
}
+ cds_lfht_rcu_flavor(ja->ht)->read_unlock();
return cds_ja_destroy(ja);
error:
+ cds_lfht_rcu_flavor(ja->ht)->read_unlock();
return ret;
}