1 // : vi ts=4 sw=4 noet :
3 ==================================================================================
4 Copyright (c) 2019-2020 Nokia
5 Copyright (c) 2018-2020 AT&T Intellectual Property.
7 Licensed under the Apache License, Version 2.0 (the "License");
8 you may not use this file except in compliance with the License.
9 You may obtain a copy of the License at
11 http://www.apache.org/licenses/LICENSE-2.0
13 Unless required by applicable law or agreed to in writing, software
14 distributed under the License is distributed on an "AS IS" BASIS,
15 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
16 See the License for the specific language governing permissions and
17 limitations under the License.
18 ==================================================================================
22 ------------------------------------------------------------------------------
24 Abstract: Symbol table -- slightly streamlined from it's original 2000 version
25 (a part of the {X}fm opensource code), though we must retain the
28 Things changed for the Ric Msg implemention (Nov 2018):
29 - no concept of copy/free of the user data (functions removed)
30 - add ability to support an integer key (class 0)
31 Numeric key is an unsigned, 64bit key.
32 - externally visible names given a rmr_ extension as it's being
33 incorporated into the RIC msg routing library and will be
34 available to user applications.
36 There is NO logging from this module! The caller is asusmed to
37 report any failures as it might handle them making any error messages
38 generated here misleading if not incorrect.
41 Author: E. Scott Daniels
43 Mod: 2016 23 Feb - converted Symtab refs so that caller need only a
44 void pointer to use and struct does not need to be exposed.
45 2018 30 Nov - Augmented from original form (see above).
46 ------------------------------------------------------------------------------
58 #include "rmr_symtab.h"
60 //-----------------------------------------------------------------------------------------------
62 typedef struct Sym_ele
64 struct Sym_ele *next; /* pointer at next element in list */
65 struct Sym_ele *prev; /* larger table, easier deletes */
66 const char *name; /* symbol name */
67 uint64_t nkey; // the numeric key
68 void *val; /* user data associated with name */
69 unsigned long mcount; /* modificaitons to value */
70 unsigned long rcount; /* references to symbol */
72 unsigned int class; /* helps divide things up and allows for duplicate names */
75 typedef struct Sym_tab {
76 Sym_ele **symlist; /* pointer to list of element pointerss */
77 long inhabitants; /* number of active residents */
78 long deaths; /* number of deletes */
82 // -------------------- internal ------------------------------------------------------------------
84 static int sym_hash( const char *n, long size )
89 for( p = n; *p; p++ ) /* a bit of magic */
95 return (int ) (t % size);
99 Delete element pointed to by eptr which is assumed to be
100 a member of the list at symtab[i].
102 static void del_ele( Sym_tab *table, int hv, Sym_ele *eptr )
106 sym_tab = table->symlist;
108 if( eptr ) /* unchain it */
111 eptr->prev->next = eptr->next;
113 sym_tab[hv] = eptr->next;
116 eptr->next->prev = eptr->prev;
118 if( eptr->class && eptr->name ) { // class 0 entries are numeric, so name is NOT a pointer
119 free( (void *) eptr->name ); // and if free fails, what? panic?
125 table->inhabitants--;
130 Delete the head element from table[i]. This isn't really
131 needed, but keeps code analysers from claiming that memory
132 is being used after it is freed.
134 static void del_head_ele( Sym_tab *table, int hv ) {
136 Sym_ele *eptr; // first in list
139 if( hv < 0 || hv >= table->size ) {
143 sym_tab = table->symlist;
144 if( (eptr = sym_tab[hv]) != NULL ) // not an empty element; yank it off
146 if( (sym_tab[hv] = eptr->next) != NULL ) { // bump list to next if not the only thing here
147 sym_tab[hv]->prev = NULL; // new head
149 eptr->next = NULL; // take no chances
151 if( eptr->class && eptr->name ) { // class 0 entries are numeric, so name is NOT a pointer
152 free( (void *) eptr->name );
158 table->inhabitants--;
163 Determine if these are the same.
165 static inline int same( unsigned int c1, unsigned int c2, const char *s1, const char* s2 )
168 return 0; /* different class - not the same */
170 if( *s1 == *s2 && strcmp( s1, s2 ) == 0 )
176 Generic routine to put something into the table
177 called by sym_map or sym_put since the logic for each is pretty
180 static int putin( Sym_tab *table, const char *name, unsigned int class, void *val ) {
181 Sym_ele *eptr; /* pointer into hash table */
182 Sym_ele **sym_tab; /* pointer into hash table */
183 int hv; /* hash value */
184 int rc = 0; /* assume it existed */
185 uint64_t nkey = 0; // numeric key if class == 0
187 sym_tab = table->symlist;
189 if( class ) { // string key
190 hv = sym_hash( name, table->size ); // hash it
191 for( eptr=sym_tab[hv]; eptr && ! same( class, eptr->class, eptr->name, name); eptr=eptr->next );
193 nkey = *((uint64_t *) name);
194 hv = nkey % table->size; // just hash the number
195 for( eptr=sym_tab[hv]; eptr && eptr->nkey != nkey; eptr=eptr->next );
198 if( ! eptr ) { // not found above, so add
200 table->inhabitants++;
202 eptr = (Sym_ele *) malloc( sizeof( Sym_ele) );
210 eptr->mcount = eptr->rcount = 0; /* init counters */
214 eptr->name = strdup( name );
216 eptr->name = NULL; // for a numeric key, just save the value
218 eptr->next = sym_tab[hv]; // add to head of list
221 eptr->next->prev = eptr; /* chain back to new one */
231 // -------------------- visible ------------------------------------------------------------------
233 /* delete all elements in the table */
234 extern void rmr_sym_clear( void *vtable )
240 table = (Sym_tab *) vtable;
241 sym_tab = table->symlist;
243 for( i = 0; i < table->size; i++ ) {
244 while( sym_tab[i] ) {
245 del_head_ele( table, i ); // delete the head element (and keep bloody sonar from claiming use after free)
251 Clear and then free the whole thing.
253 extern void rmr_sym_free( void *vtable ) {
256 table = (Sym_tab *) vtable;
261 rmr_sym_clear( vtable );
262 free( table->symlist );
266 extern void rmr_sym_dump( void *vtable )
273 table = (Sym_tab *) vtable;
274 sym_tab = table->symlist;
276 for( i = 0; i < table->size; i++ ) {
278 for( eptr = sym_tab[i]; eptr; eptr = eptr->next ) {
279 if( eptr->val && eptr->class ) {
280 fprintf( stderr, "symtab dump: key=%s val@=%p\n", eptr->name, eptr->val );
282 fprintf( stderr, "symtab dump: nkey=%lu val@=%p\n", (unsigned long) eptr->nkey, eptr->val );
290 Allocate a table the size requested - best if size is prime.
291 Returns a pointer to the management block (handle) or NULL on failure.
293 extern void *rmr_sym_alloc( int size )
297 if( size < 11 ) /* provide a bit of sanity */
300 if( (table = (Sym_tab *) malloc( sizeof( Sym_tab ))) == NULL )
306 memset( table, 0, sizeof( *table ) );
308 if((table->symlist = (Sym_ele **) malloc( sizeof( Sym_ele *) * size )))
310 memset( table->symlist, 0, sizeof( Sym_ele *) * size );
319 return (void *) table; /* user might want to know what the size is */
323 Delete an element given name/class or numeric key (class 0).
325 extern void rmr_sym_del( void *vtable, const char *name, unsigned int class )
329 Sym_ele *eptr; /* pointer into hash table */
330 int hv; /* hash value */
331 uint64_t nkey; // class 0, name points to integer not string
333 table = (Sym_tab *) vtable;
334 sym_tab = table->symlist;
337 hv = sym_hash( name, table->size );
338 for(eptr=sym_tab[hv]; eptr && ! same(class, eptr->class, eptr->name, name); eptr=eptr->next );
340 nkey = *((uint64_t *) name);
341 hv = nkey % table->size; // just hash the number
342 for( eptr=sym_tab[hv]; eptr && eptr->nkey != nkey; eptr=eptr->next );
345 del_ele( table, hv, eptr ); /* ignors null ptr, so safe to always call */
349 Delete element by numberic key.
351 extern void rmr_sym_ndel( void *vtable, uint64_t key ) {
352 rmr_sym_del( vtable, (const char *) &key, 0 );
356 extern void *rmr_sym_get( void *vtable, const char *name, unsigned int class )
360 Sym_ele *eptr; // element from table
361 int hv; // hash value of key
362 uint64_t nkey; // numeric key if class 0
364 if( (table = (Sym_tab *) vtable) == NULL ) {
368 sym_tab = table->symlist;
371 hv = sym_hash( name, table->size );
372 for(eptr=sym_tab[hv]; eptr && ! same(class, eptr->class, eptr->name, name); eptr=eptr->next );
374 nkey = *((uint64_t *) name);
375 hv = nkey % table->size; // just hash the number
376 for( eptr=sym_tab[hv]; eptr && eptr->nkey != nkey; eptr=eptr->next );
389 Retrieve the data referenced by a numerical key.
391 extern void *rmr_sym_pull( void *vtable, uint64_t key ) {
392 return rmr_sym_get( vtable, (const char *) &key, 0 );
396 Put an element with a string key into the table. Replaces the element
397 if it was already there. Class must be >0 and if not 1 will be forced.
398 (class 0 keys are numeric).
399 Returns 1 if new, 0 if existed.
401 extern int rmr_sym_put( void *vtable, const char *name, unsigned int class, void *val )
409 table = (Sym_tab *) vtable;
410 return putin( table, name, class, val );
414 Add a new entry assuming that the key is an unsigned, 64 bit, integer.
416 Returns 1 if new, 0 if existed
418 extern int rmr_sym_map( void *vtable, uint64_t key, void *val ) {
421 table = (Sym_tab *) vtable;
422 return putin( table, (const char *) &key, 0, val );
426 Dump some statistics to stderr dev. Higher level is the more info dumpped
428 extern void rmr_sym_stats( void *vtable, int level )
431 Sym_ele *eptr; /* pointer into the elements */
440 table = (Sym_tab *) vtable;
441 sym_tab = table->symlist;
443 for( i = 0; i < table->size; i++ )
448 for( eptr = sym_tab[i]; eptr; eptr = eptr->next )
452 if( eptr->class ) { // a string key
453 fprintf( stderr, " symtab stats: sym: (%d) key=%s val@=%p ref=%ld mod=%lu\n", i, eptr->name, eptr->val, eptr->rcount, eptr->mcount );
455 fprintf( stderr, "symtab stats: sym: (%d) key=%lu val@=%p ref=%ld mod=%lu\n", i, (unsigned long) eptr->nkey, eptr->val, eptr->rcount, eptr->mcount );
463 if( ch_count > max_chain )
465 max_chain = ch_count;
472 fprintf( stderr, "symtab stats: sym: (%d) chained=%ld\n", i, ch_count );
477 fprintf( stderr, "symtab stats: sym: longest chain: idx=%d has %ld elsements):\n", maxi, max_chain );
478 for( eptr = sym_tab[maxi]; eptr; eptr = eptr->next ) {
480 fprintf( stderr, "\t%s\n", eptr->name );
482 fprintf( stderr, "\t%lu (numeric key)\n", (unsigned long) eptr->nkey );
487 fprintf( stderr, "symtab stats: sym:%ld(size) %ld(inhab) %ld(occupied) %ld(dead) %ld(maxch) %d(>2per)\n",
488 table->size, table->inhabitants, table->size - empty, table->deaths, max_chain, twoper );
492 Drive a user callback function for each entry in a class. It is safe for
493 the user to delete the element as we capture a next pointer before
494 calling their function.
496 extern void rmr_sym_foreach_class( void *vst, unsigned int class, void (* user_fun)( void*, void*, const char*, void*, void* ), void *user_data )
501 Sym_ele *next; /* allows user to delete the node(s) we return */
504 if( (st = (Sym_tab *) vst) == NULL ) {
508 if( (list = st->symlist) != NULL && user_fun != NULL ) {
509 for( i = 0; i < st->size; i++ ) {
512 next = se->next; // allow callback to delete from the list w/o borking us
513 if( class == se->class ) {
514 user_fun( st, se, se->name, se->val, user_data );