Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

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