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
RevLine 
[9a1b20c]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>
[d9c8c81]37#include <adt/hash_table.h>
[9a1b20c]38
[abf3564]39#include "trace.h"
[9a1b20c]40#include "proto.h"
41
[062d900]42/* Maps service number to protocol */
43static hash_table_t srv_proto;
[9a1b20c]44
45typedef struct {
[062d900]46 int srv;
[9a1b20c]47 proto_t *proto;
[062d900]48 ht_link_t link;
[9a1b20c]49} srv_proto_t;
50
51typedef struct {
[062d900]52 int method;
[9a1b20c]53 oper_t *oper;
[062d900]54 ht_link_t link;
[9a1b20c]55} method_oper_t;
56
[062d900]57/* Hash table operations. */
[9a1b20c]58
[5e801dc]59static size_t srv_proto_key_hash(const void *key)
[9a1b20c]60{
[5e801dc]61 const int *n = key;
62 return *n;
[9a1b20c]63}
64
[062d900]65static size_t srv_proto_hash(const ht_link_t *item)
[9a1b20c]66{
[062d900]67 srv_proto_t *sp = hash_table_get_inst(item, srv_proto_t, link);
68 return sp->srv;
[9a1b20c]69}
70
[0db0df2]71static bool srv_proto_key_equal(const void *key, size_t hash, const ht_link_t *item)
[9a1b20c]72{
[5e801dc]73 const int *n = key;
[062d900]74 srv_proto_t *sp = hash_table_get_inst(item, srv_proto_t, link);
[5e801dc]75 return sp->srv == *n;
[9a1b20c]76}
77
[61eb2ce2]78static const hash_table_ops_t srv_proto_ops = {
[062d900]79 .hash = srv_proto_hash,
80 .key_hash = srv_proto_key_hash,
81 .key_equal = srv_proto_key_equal,
[4e00f87]82 .equal = NULL,
83 .remove_callback = NULL
[062d900]84};
85
[5e801dc]86static size_t method_oper_key_hash(const void *key)
[9a1b20c]87{
[5e801dc]88 const int *n = key;
89 return *n;
[9a1b20c]90}
91
[062d900]92static size_t method_oper_hash(const ht_link_t *item)
[9a1b20c]93{
[062d900]94 method_oper_t *mo = hash_table_get_inst(item, method_oper_t, link);
95 return mo->method;
[9a1b20c]96}
97
[0db0df2]98static bool method_oper_key_equal(const void *key, size_t hash, const ht_link_t *item)
[9a1b20c]99{
[5e801dc]100 const int *n = key;
[062d900]101 method_oper_t *mo = hash_table_get_inst(item, method_oper_t, link);
[5e801dc]102 return mo->method == *n;
[9a1b20c]103}
104
[61eb2ce2]105static const hash_table_ops_t method_oper_ops = {
[062d900]106 .hash = method_oper_hash,
107 .key_hash = method_oper_key_hash,
108 .key_equal = method_oper_key_equal,
[4e00f87]109 .equal = NULL,
110 .remove_callback = NULL
[062d900]111};
112
[9a1b20c]113void proto_init(void)
114{
[062d900]115 /* todo: check return value. */
116 bool ok = hash_table_create(&srv_proto, 0, 0, &srv_proto_ops);
117 assert(ok);
[9a1b20c]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
[062d900]133 hash_table_insert(&srv_proto, &sp->link);
[9a1b20c]134}
135
136proto_t *proto_get_by_srv(int srv)
137{
[062d900]138 ht_link_t *item = hash_table_find(&srv_proto, &srv);
[1433ecda]139 if (item == NULL)
140 return NULL;
[9a1b20c]141
[062d900]142 srv_proto_t *sp = hash_table_get_inst(item, srv_proto_t, link);
[9a1b20c]143 return sp->proto;
144}
145
[a000878c]146static void proto_struct_init(proto_t *proto, const char *name)
[9a1b20c]147{
148 proto->name = name;
[062d900]149 /* todo: check return value. */
150 bool ok = hash_table_create(&proto->method_oper, 0, 0, &method_oper_ops);
151 assert(ok);
[9a1b20c]152}
153
[a000878c]154proto_t *proto_new(const char *name)
[9a1b20c]155{
156 proto_t *p;
157
158 p = malloc(sizeof(proto_t));
159 proto_struct_init(p, name);
160
161 return p;
162}
163
[8c125ad]164void proto_delete(proto_t *proto)
165{
166 free(proto);
167}
168
[9a1b20c]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
[1b20da0]177 hash_table_insert(&proto->method_oper, &mo->link);
[9a1b20c]178}
179
180oper_t *proto_get_oper(proto_t *proto, int method)
181{
[062d900]182 ht_link_t *item = hash_table_find(&proto->method_oper, &method);
[1433ecda]183 if (item == NULL)
184 return NULL;
[9a1b20c]185
[062d900]186 method_oper_t *mo = hash_table_get_inst(item, method_oper_t, link);
[9a1b20c]187 return mo->oper;
188}
189
[a000878c]190static void oper_struct_init(oper_t *oper, const char *name)
[9a1b20c]191{
192 oper->name = name;
193}
194
[a000878c]195oper_t *oper_new(const char *name, int argc, val_type_t *arg_types,
[abf3564]196 val_type_t rv_type, int respc, val_type_t *resp_types)
[9a1b20c]197{
198 oper_t *o;
[abf3564]199 int i;
[9a1b20c]200
201 o = malloc(sizeof(oper_t));
202 oper_struct_init(o, name);
203
[abf3564]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
[9a1b20c]214 return o;
215}
216
217/** @}
218 */
Note: See TracBrowser for help on using the repository browser.