diff options
Diffstat (limited to 'lib/skiplist.c')
| -rw-r--r-- | lib/skiplist.c | 43 |
1 files changed, 24 insertions, 19 deletions
diff --git a/lib/skiplist.c b/lib/skiplist.c index fc42857418..c5219f7381 100644 --- a/lib/skiplist.c +++ b/lib/skiplist.c @@ -65,17 +65,25 @@ DEFINE_MTYPE_STATIC(LIB, SKIP_LIST, "Skip List"); DEFINE_MTYPE_STATIC(LIB, SKIP_LIST_NODE, "Skip Node"); +DEFINE_MTYPE_STATIC(LIB, SKIP_LIST_STATS, "Skiplist Counters"); #define BitsInRandom 31 #define MaxNumberOfLevels 16 #define MaxLevel (MaxNumberOfLevels-1) -#define newNodeOfLevel(l) XCALLOC(MTYPE_SKIP_LIST_NODE, sizeof(struct skiplistnode)+(l)*sizeof(struct skiplistnode *)) +#define newNodeOfLevel(l) \ + XCALLOC(MTYPE_SKIP_LIST_NODE, \ + sizeof(struct skiplistnode) \ + + (l) * sizeof(struct skiplistnode *)) + +/* XXX must match type of (struct skiplist).level_stats */ +#define newStatsOfLevel(l) \ + XCALLOC(MTYPE_SKIP_LIST_STATS, ((l) + 1) * sizeof(int)) static int randomsLeft; static int randomBits; -#if 1 +#ifdef SKIPLIST_DEBUG #define CHECKLAST(sl) \ do { \ if ((sl)->header->forward[0] && !(sl)->last) \ @@ -138,7 +146,7 @@ struct skiplist *skiplist_new(int flags, new->level = 0; new->count = 0; new->header = newNodeOfLevel(MaxNumberOfLevels); - new->stats = newNodeOfLevel(MaxNumberOfLevels); + new->level_stats = newStatsOfLevel(MaxNumberOfLevels); new->flags = flags; if (cmp) @@ -166,7 +174,7 @@ void skiplist_free(struct skiplist *l) p = q; } while (p); - XFREE(MTYPE_SKIP_LIST_NODE, l->stats); + XFREE(MTYPE_SKIP_LIST_STATS, l->level_stats); XFREE(MTYPE_SKIP_LIST, l); } @@ -180,11 +188,13 @@ int skiplist_insert(register struct skiplist *l, register void *key, CHECKLAST(l); +#ifdef SKIPLIST_DEBUG /* DEBUG */ if (!key) { flog_err(EC_LIB_DEVELOPMENT, "%s: key is 0, value is %p", __func__, value); } +#endif p = l->header; k = l->level; @@ -214,10 +224,10 @@ int skiplist_insert(register struct skiplist *l, register void *key, q->flags = SKIPLIST_NODE_FLAG_INSERTED; /* debug */ #endif - ++(l->stats->forward[k]); + ++(l->level_stats[k]); #ifdef SKIPLIST_DEBUG - zlog_debug("%s: incremented stats @%p:%d, now %ld", __func__, l, k, - l->stats->forward[k] - (struct skiplistnode *)NULL); + zlog_debug("%s: incremented level_stats @%p:%d, now %d", __func__, l, k, + l->level_stats[k]); #endif do { @@ -298,12 +308,10 @@ int skiplist_delete(register struct skiplist *l, register void *key, k++) { p->forward[k] = q->forward[k]; } - --(l->stats->forward[k - 1]); + --(l->level_stats[k - 1]); #ifdef SKIPLIST_DEBUG - zlog_debug("%s: decremented stats @%p:%d, now %ld", - __func__, l, k - 1, - l->stats->forward[k - 1] - - (struct skiplistnode *)NULL); + zlog_debug("%s: decremented level_stats @%p:%d, now %d", + __func__, l, k - 1, l->level_stats[k - 1]); #endif if (l->del) (*l->del)(q->value); @@ -559,11 +567,10 @@ int skiplist_delete_first(register struct skiplist *l) l->last = NULL; } - --(l->stats->forward[nodelevel]); + --(l->level_stats[nodelevel]); #ifdef SKIPLIST_DEBUG - zlog_debug("%s: decremented stats @%p:%d, now %ld", __func__, l, - nodelevel, - l->stats->forward[nodelevel] - (struct skiplistnode *)NULL); + zlog_debug("%s: decremented level_stats @%p:%d, now %d", __func__, l, + nodelevel, l->level_stats[nodelevel]); #endif if (l->del) @@ -587,9 +594,7 @@ void skiplist_debug(struct vty *vty, struct skiplist *l) vty_out(vty, "Skiplist %p has max level %d\n", l, l->level); for (i = l->level; i >= 0; --i) - vty_out(vty, " @%d: %ld\n", i, - (long)((l->stats->forward[i]) - - (struct skiplistnode *)NULL)); + vty_out(vty, " @%d: %d\n", i, l->level_stats[i]); } static void *scramble(int i) |