1#include "config.h"
2#include <sys/types.h>
3#include <stdlib.h>
4#include <inttypes.h>
5#include <string.h>
6#include <platform/platform.h>
7#include "topkeys.h"
8
9static topkey_item_t *topkey_item_init(const void *key, int nkey, rel_time_t ct) {
10    topkey_item_t *it = calloc(sizeof(topkey_item_t) + nkey, 1);
11    cb_assert(it);
12    cb_assert(key);
13    cb_assert(nkey > 0);
14    it->ti_nkey = nkey;
15    it->ti_ctime = ct;
16    it->ti_atime = ct;
17    /* Copy the key into the part trailing the struct */
18    memcpy(it + 1, key, nkey);
19    return it;
20}
21
22static size_t topkey_item_size(const topkey_item_t *it) {
23    return sizeof(topkey_item_t) + it->ti_nkey;
24}
25
26static topkey_item_t* topkeys_tail(topkeys_t *tk) {
27    return (topkey_item_t*)(tk->list.prev);
28}
29
30static int my_hash_eq(const void *k1, size_t nkey1,
31                      const void *k2, size_t nkey2) {
32    return nkey1 == nkey2 && memcmp(k1, k2, nkey1) == 0;
33}
34
35topkeys_t *topkeys_init(int max_keys) {
36    static struct hash_ops my_hash_ops;
37    topkeys_t *tk = calloc(sizeof(topkeys_t), 1);
38    if (tk == NULL) {
39        return NULL;
40    }
41
42    my_hash_ops.hashfunc = genhash_string_hash;
43    my_hash_ops.hasheq = my_hash_eq;
44    my_hash_ops.dupKey = NULL;
45    my_hash_ops.dupValue = NULL;
46    my_hash_ops.freeKey = NULL;
47    my_hash_ops.freeValue = NULL;
48
49    cb_mutex_initialize(&tk->mutex);
50    tk->max_keys = max_keys;
51    tk->list.next = &tk->list;
52    tk->list.prev = &tk->list;
53
54    tk->hash = genhash_init(max_keys, my_hash_ops);
55    if (tk->hash == NULL) {
56        return NULL;
57    }
58
59    return tk;
60}
61
62void topkeys_free(topkeys_t *tk) {
63    dlist_t *p;
64    cb_mutex_destroy(&tk->mutex);
65    genhash_free(tk->hash);
66    p = tk->list.next;
67    while (p != &tk->list) {
68        dlist_t *tmp = p->next;
69        free(p);
70        p = tmp;
71    }
72}
73
74static void dlist_remove(dlist_t *list) {
75    cb_assert(list->prev->next == list);
76    cb_assert(list->next->prev == list);
77    list->prev->next = list->next;
78    list->next->prev = list->prev;
79}
80
81static void dlist_insert_after(dlist_t *list, dlist_t *new) {
82    new->next = list->next;
83    new->prev = list;
84    list->next->prev = new;
85    list->next = new;
86}
87
88static void dlist_iter(dlist_t *list,
89                              void (*iterfunc)(dlist_t *item, void *arg),
90                              void *arg)
91{
92    dlist_t *p = list;
93    while ((p = p->next) != list) {
94        iterfunc(p, arg);
95    }
96}
97
98static void topkeys_item_delete(topkeys_t *tk, topkey_item_t *it) {
99    genhash_delete(tk->hash, it + 1, it->ti_nkey);
100    dlist_remove(&it->ti_list);
101    --tk->nkeys;
102    free(it);
103}
104
105topkey_item_t *topkeys_item_get_or_create(topkeys_t *tk, const void *key, size_t nkey, const rel_time_t ct) {
106    topkey_item_t *it = genhash_find(tk->hash, key, nkey);
107    if (it == NULL) {
108        it = topkey_item_init(key, (int)nkey, ct);
109        if (it != NULL) {
110            if (++tk->nkeys > tk->max_keys) {
111                topkeys_item_delete(tk, topkeys_tail(tk));
112            }
113            genhash_update(tk->hash, it + 1, it->ti_nkey,
114                           it, topkey_item_size(it));
115        } else {
116            return NULL;
117        }
118    } else {
119        dlist_remove(&it->ti_list);
120    }
121    dlist_insert_after(&tk->list, &it->ti_list);
122    return it;
123}
124
125struct tk_context {
126    const void *cookie;
127    ADD_STAT add_stat;
128    rel_time_t current_time;
129};
130
131#define TK_FMT(name) #name "=%d,"
132#define TK_ARGS(name) it->name,
133
134static void tk_iterfunc(dlist_t *list, void *arg) {
135    struct tk_context *c = arg;
136    topkey_item_t *it = (topkey_item_t*)list;
137    char val_str[TK_MAX_VAL_LEN];
138    /* This line is magical. The missing comma before item->ctime is because the TK_ARGS macro ends with a comma. */
139    int vlen = snprintf(val_str, sizeof(val_str) - 1, TK_OPS(TK_FMT)"ctime=%"PRIu32",atime=%"PRIu32, TK_OPS(TK_ARGS)
140                        c->current_time - it->ti_ctime, c->current_time - it->ti_atime);
141    c->add_stat((char*)(it + 1), it->ti_nkey, val_str, vlen, c->cookie);
142}
143
144ENGINE_ERROR_CODE topkeys_stats(topkeys_t **tks, size_t shards,
145                                const void *cookie,
146                                const rel_time_t current_time,
147                                ADD_STAT add_stat) {
148    struct tk_context context;
149    size_t i;
150    context.cookie = cookie;
151    context.add_stat = add_stat;
152    context.current_time = current_time;
153    for (i = 0; i < shards; i++) {
154        topkeys_t *tk = tks[i];
155        cb_assert(tk);
156        cb_mutex_enter(&tk->mutex);
157        dlist_iter(&tk->list, tk_iterfunc, &context);
158        cb_mutex_exit(&tk->mutex);
159    }
160    return ENGINE_SUCCESS;
161}
162
163topkeys_t *tk_get_shard(topkeys_t **tks, const void *key, size_t nkey) {
164    /* This is special-cased for 8 */
165    int khash;
166    cb_assert(TK_SHARDS == 8);
167    khash = genhash_string_hash(key, nkey);
168    return tks[khash & 0x07];
169}
170