source: mainline/uspace/app/trace/proto.c

Last change on this file was 0db0df2, checked in by Jiří Zárevúcky <zarevucky.jiri@…>, 3 months ago

Hash table improvements

Implement hash_table_foreach macro, analogous to list_foreach.

Remove superfluous argument to hash_table_find_next().
(If the user needs to recheck the part of the list already
checked by hash_table_find(), they can just rerun that function.)

Add hash argument to hash_table_ops_t::key_equal.
The big change here is that users with big keys can store the hash
value alongside key in their entries, and for the low low cost of
sizeof(size_t) bytes eliminate a bunch of expensive key comparisons.

Also added a hash function for strings and arbitrary data.
Found this one by asking ChatGPT, because the latency of accesses
to my book collection is currently a couple of hours.

+ Some drive-by unused #include removal.

  • Property mode set to 100644
File size: 5.0 KB
Line 
1/*
2 * Copyright (c) 2008 Jiri Svoboda
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 *
9 * - Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 * - Redistributions in binary form must reproduce the above copyright
12 * notice, this list of conditions and the following disclaimer in the
13 * documentation and/or other materials provided with the distribution.
14 * - The name of the author may not be used to endorse or promote products
15 * derived from this software without specific prior written permission.
16 *
17 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
18 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
19 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
20 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
21 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
22 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 */
28
29/** @addtogroup trace
30 * @{
31 */
32/** @file
33 */
34
35#include <stdio.h>
36#include <stdlib.h>
37#include <adt/hash_table.h>
38
39#include "trace.h"
40#include "proto.h"
41
42/* Maps service number to protocol */
43static hash_table_t srv_proto;
44
45typedef struct {
46 int srv;
47 proto_t *proto;
48 ht_link_t link;
49} srv_proto_t;
50
51typedef struct {
52 int method;
53 oper_t *oper;
54 ht_link_t link;
55} method_oper_t;
56
57/* Hash table operations. */
58
59static size_t srv_proto_key_hash(const void *key)
60{
61 const int *n = key;
62 return *n;
63}
64
65static size_t srv_proto_hash(const ht_link_t *item)
66{
67 srv_proto_t *sp = hash_table_get_inst(item, srv_proto_t, link);
68 return sp->srv;
69}
70
71static bool srv_proto_key_equal(const void *key, size_t hash, const ht_link_t *item)
72{
73 const int *n = key;
74 srv_proto_t *sp = hash_table_get_inst(item, srv_proto_t, link);
75 return sp->srv == *n;
76}
77
78static const hash_table_ops_t srv_proto_ops = {
79 .hash = srv_proto_hash,
80 .key_hash = srv_proto_key_hash,
81 .key_equal = srv_proto_key_equal,
82 .equal = NULL,
83 .remove_callback = NULL
84};
85
86static size_t method_oper_key_hash(const void *key)
87{
88 const int *n = key;
89 return *n;
90}
91
92static size_t method_oper_hash(const ht_link_t *item)
93{
94 method_oper_t *mo = hash_table_get_inst(item, method_oper_t, link);
95 return mo->method;
96}
97
98static bool method_oper_key_equal(const void *key, size_t hash, const ht_link_t *item)
99{
100 const int *n = key;
101 method_oper_t *mo = hash_table_get_inst(item, method_oper_t, link);
102 return mo->method == *n;
103}
104
105static const hash_table_ops_t method_oper_ops = {
106 .hash = method_oper_hash,
107 .key_hash = method_oper_key_hash,
108 .key_equal = method_oper_key_equal,
109 .equal = NULL,
110 .remove_callback = NULL
111};
112
113void proto_init(void)
114{
115 /* todo: check return value. */
116 bool ok = hash_table_create(&srv_proto, 0, 0, &srv_proto_ops);
117 assert(ok);
118}
119
120void proto_cleanup(void)
121{
122 hash_table_destroy(&srv_proto);
123}
124
125void proto_register(int srv, proto_t *proto)
126{
127 srv_proto_t *sp;
128
129 sp = malloc(sizeof(srv_proto_t));
130 sp->srv = srv;
131 sp->proto = proto;
132
133 hash_table_insert(&srv_proto, &sp->link);
134}
135
136proto_t *proto_get_by_srv(int srv)
137{
138 ht_link_t *item = hash_table_find(&srv_proto, &srv);
139 if (item == NULL)
140 return NULL;
141
142 srv_proto_t *sp = hash_table_get_inst(item, srv_proto_t, link);
143 return sp->proto;
144}
145
146static void proto_struct_init(proto_t *proto, const char *name)
147{
148 proto->name = name;
149 /* todo: check return value. */
150 bool ok = hash_table_create(&proto->method_oper, 0, 0, &method_oper_ops);
151 assert(ok);
152}
153
154proto_t *proto_new(const char *name)
155{
156 proto_t *p;
157
158 p = malloc(sizeof(proto_t));
159 proto_struct_init(p, name);
160
161 return p;
162}
163
164void proto_delete(proto_t *proto)
165{
166 free(proto);
167}
168
169void proto_add_oper(proto_t *proto, int method, oper_t *oper)
170{
171 method_oper_t *mo;
172
173 mo = malloc(sizeof(method_oper_t));
174 mo->method = method;
175 mo->oper = oper;
176
177 hash_table_insert(&proto->method_oper, &mo->link);
178}
179
180oper_t *proto_get_oper(proto_t *proto, int method)
181{
182 ht_link_t *item = hash_table_find(&proto->method_oper, &method);
183 if (item == NULL)
184 return NULL;
185
186 method_oper_t *mo = hash_table_get_inst(item, method_oper_t, link);
187 return mo->oper;
188}
189
190static void oper_struct_init(oper_t *oper, const char *name)
191{
192 oper->name = name;
193}
194
195oper_t *oper_new(const char *name, int argc, val_type_t *arg_types,
196 val_type_t rv_type, int respc, val_type_t *resp_types)
197{
198 oper_t *o;
199 int i;
200
201 o = malloc(sizeof(oper_t));
202 oper_struct_init(o, name);
203
204 o->argc = argc;
205 for (i = 0; i < argc; i++)
206 o->arg_type[i] = arg_types[i];
207
208 o->rv_type = rv_type;
209
210 o->respc = respc;
211 for (i = 0; i < respc; i++)
212 o->resp_type[i] = resp_types[i];
213
214 return o;
215}
216
217/** @}
218 */
Note: See TracBrowser for help on using the repository browser.