1 // SPDX-License-Identifier: GPL-2.0
2 /*
3 * Copyright (C) 2014, Steven Rostedt <[email protected]>
4 *
5 */
6 #include <stdio.h>
7 #include <stdlib.h>
8 #include <string.h>
9 #include <stdarg.h>
10 #include <errno.h>
11
12 #include "trace-cmd-private.h"
13 #include "trace-hash.h"
14
trace_hash_init(struct trace_hash * hash,int buckets)15 int __hidden trace_hash_init(struct trace_hash *hash, int buckets)
16 {
17 memset(hash, 0, sizeof(*hash));
18
19 hash->buckets = calloc(sizeof(*hash->buckets), buckets);
20 if (!hash->buckets)
21 return -ENOMEM;
22 hash->nr_buckets = buckets;
23
24 /* If a power of two then we can shortcut */
25 if (!(buckets & (buckets - 1)))
26 hash->power = buckets - 1;
27
28 return 0;
29 }
30
trace_hash_free(struct trace_hash * hash)31 void __hidden trace_hash_free(struct trace_hash *hash)
32 {
33 free(hash->buckets);
34 }
35
trace_hash_empty(struct trace_hash * hash)36 int __hidden trace_hash_empty(struct trace_hash *hash)
37 {
38 struct trace_hash_item **bucket;
39
40 trace_hash_for_each_bucket(bucket, hash)
41 if (*bucket)
42 return 0;
43 return 1;
44 }
45
trace_hash_add(struct trace_hash * hash,struct trace_hash_item * item)46 int __hidden trace_hash_add(struct trace_hash *hash, struct trace_hash_item *item)
47 {
48 struct trace_hash_item *next;
49 int bucket = hash->power ? item->key & hash->power :
50 item->key % hash->nr_buckets;
51
52 if (hash->buckets[bucket]) {
53 next = hash->buckets[bucket];
54 next->prev = item;
55 } else
56 next = NULL;
57
58 item->next = next;
59 item->prev = (struct trace_hash_item *)&hash->buckets[bucket];
60
61 hash->buckets[bucket] = item;
62
63 return 1;
64 }
65
66 __hidden struct trace_hash_item *
trace_hash_find(struct trace_hash * hash,unsigned long long key,trace_hash_func match,void * data)67 trace_hash_find(struct trace_hash *hash, unsigned long long key,
68 trace_hash_func match, void *data)
69 {
70 struct trace_hash_item *item;
71 int bucket = hash->power ? key & hash->power :
72 key % hash->nr_buckets;
73
74 for (item = hash->buckets[bucket]; item; item = item->next) {
75 if (item->key == key) {
76 if (!match)
77 return item;
78 if (match(item, data))
79 return item;
80 }
81 }
82
83 return NULL;
84 }
85