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 ------------------------------------------------------------------------------
57 #include "rmr_symtab.h"
59 //-----------------------------------------------------------------------------------------------
61 typedef struct Sym_ele
63 struct Sym_ele *next; /* pointer at next element in list */
64 struct Sym_ele *prev; /* larger table, easier deletes */
65 const char *name; /* symbol name */
66 uint64_t nkey; // the numeric key
67 void *val; /* user data associated with name */
68 unsigned long mcount; /* modificaitons to value */
69 unsigned long rcount; /* references to symbol */
71 unsigned int class; /* helps divide things up and allows for duplicate names */
74 typedef struct Sym_tab {
75 Sym_ele **symlist; /* pointer to list of element pointerss */
76 long inhabitants; /* number of active residents */
77 long deaths; /* number of deletes */
81 // -------------------- internal ------------------------------------------------------------------
83 static int sym_hash( const char *n, long size )
90 for( p = n; *p; p++ ) /* a bit of magic */
96 return (int ) (t % size);
99 /* delete element pointed to by eptr at hash loc hv */
100 static void del_ele( Sym_tab *table, int hv, Sym_ele *eptr )
104 sym_tab = table->symlist;
106 if( eptr ) /* unchain it */
109 eptr->prev->next = eptr->next;
111 sym_tab[hv] = eptr->next;
114 eptr->next->prev = eptr->prev;
116 if( eptr->class && eptr->name ) { // class 0 entries are numeric, so name is NOT a pointer
117 free( (void *) eptr->name ); // and if free fails, what? panic?
123 table->inhabitants--;
128 Determine if these are the same.
130 static inline int same( unsigned int c1, unsigned int c2, const char *s1, const char* s2 )
133 return 0; /* different class - not the same */
135 if( *s1 == *s2 && strcmp( s1, s2 ) == 0 )
141 Generic routine to put something into the table
142 called by sym_map or sym_put since the logic for each is pretty
145 static int putin( Sym_tab *table, const char *name, unsigned int class, void *val ) {
146 Sym_ele *eptr; /* pointer into hash table */
147 Sym_ele **sym_tab; /* pointer into hash table */
148 int hv; /* hash value */
149 int rc = 0; /* assume it existed */
150 uint64_t nkey = 0; // numeric key if class == 0
152 sym_tab = table->symlist;
154 if( class ) { // string key
155 hv = sym_hash( name, table->size ); // hash it
156 for( eptr=sym_tab[hv]; eptr && ! same( class, eptr->class, eptr->name, name); eptr=eptr->next );
158 nkey = *((uint64_t *) name);
159 hv = nkey % table->size; // just hash the number
160 for( eptr=sym_tab[hv]; eptr && eptr->nkey != nkey; eptr=eptr->next );
163 if( ! eptr ) { // not found above, so add
165 table->inhabitants++;
167 eptr = (Sym_ele *) malloc( sizeof( Sym_ele) );
175 eptr->mcount = eptr->rcount = 0; /* init counters */
179 eptr->name = strdup( name );
181 eptr->name = NULL; // for a numeric key, just save the value
183 eptr->next = sym_tab[hv]; // add to head of list
186 eptr->next->prev = eptr; /* chain back to new one */
196 // -------------------- visible ------------------------------------------------------------------
198 /* delete all elements in the table */
199 extern void rmr_sym_clear( void *vtable )
205 table = (Sym_tab *) vtable;
206 sym_tab = table->symlist;
208 for( i = 0; i < table->size; i++ )
210 del_ele( table, i, sym_tab[i] );
214 Clear and then free the whole thing.
216 extern void rmr_sym_free( void *vtable ) {
219 table = (Sym_tab *) vtable;
224 rmr_sym_clear( vtable );
225 free( table->symlist );
229 extern void rmr_sym_dump( void *vtable )
236 table = (Sym_tab *) vtable;
237 sym_tab = table->symlist;
239 for( i = 0; i < table->size; i++ )
242 for( eptr = sym_tab[i]; eptr; eptr = eptr->next )
244 if( eptr->val && eptr->class ) {
245 fprintf( stderr, "symtab dump: key=%s val@=%p\n", eptr->name, eptr->val );
247 fprintf( stderr, "symtab dump: nkey=%lu val@=%p\n", (unsigned long) eptr->nkey, eptr->val );
254 Allocate a table the size requested - best if size is prime.
255 Returns a pointer to the management block (handle) or NULL on failure.
257 extern void *rmr_sym_alloc( int size )
262 if( size < 11 ) /* provide a bit of sanity */
265 if( (table = (Sym_tab *) malloc( sizeof( Sym_tab ))) == NULL )
271 memset( table, 0, sizeof( *table ) );
273 if((table->symlist = (Sym_ele **) malloc( sizeof( Sym_ele *) * size )))
275 memset( table->symlist, 0, sizeof( Sym_ele *) * size );
284 return (void *) table; /* user might want to know what the size is */
288 Delete an element given name/class or numeric key (class 0).
290 extern void rmr_sym_del( void *vtable, const char *name, unsigned int class )
294 Sym_ele *eptr; /* pointer into hash table */
295 int hv; /* hash value */
296 uint64_t nkey; // class 0, name points to integer not string
298 table = (Sym_tab *) vtable;
299 sym_tab = table->symlist;
302 hv = sym_hash( name, table->size );
303 for(eptr=sym_tab[hv]; eptr && ! same(class, eptr->class, eptr->name, name); eptr=eptr->next );
305 nkey = *((uint64_t *) name);
306 hv = nkey % table->size; // just hash the number
307 for( eptr=sym_tab[hv]; eptr && eptr->nkey != nkey; eptr=eptr->next );
310 del_ele( table, hv, eptr ); /* ignors null ptr, so safe to always call */
314 Delete element by numberic key.
316 extern void rmr_sym_ndel( void *vtable, uint64_t key ) {
317 rmr_sym_del( vtable, (const char *) &key, 0 );
321 extern void *rmr_sym_get( void *vtable, const char *name, unsigned int class )
325 Sym_ele *eptr; // element from table
326 int hv; // hash value of key
327 uint64_t nkey; // numeric key if class 0
329 if( (table = (Sym_tab *) vtable) == NULL ) {
333 sym_tab = table->symlist;
336 hv = sym_hash( name, table->size );
337 for(eptr=sym_tab[hv]; eptr && ! same(class, eptr->class, eptr->name, name); eptr=eptr->next );
339 nkey = *((uint64_t *) name);
340 hv = nkey % table->size; // just hash the number
341 for( eptr=sym_tab[hv]; eptr && eptr->nkey != nkey; eptr=eptr->next );
354 Retrieve the data referenced by a numerical key.
356 extern void *rmr_sym_pull( void *vtable, uint64_t key ) {
357 return rmr_sym_get( vtable, (const char *) &key, 0 );
361 Put an element with a string key into the table. Replaces the element
362 if it was already there. Class must be >0 and if not 1 will be forced.
363 (class 0 keys are numeric).
364 Returns 1 if new, 0 if existed.
366 extern int rmr_sym_put( void *vtable, const char *name, unsigned int class, void *val )
374 table = (Sym_tab *) vtable;
375 return putin( table, name, class, val );
379 Add a new entry assuming that the key is an unsigned, 64 bit, integer.
381 Returns 1 if new, 0 if existed
383 extern int rmr_sym_map( void *vtable, uint64_t key, void *val ) {
386 table = (Sym_tab *) vtable;
387 return putin( table, (const char *) &key, 0, val );
391 Dump some statistics to stderr dev. Higher level is the more info dumpped
393 extern void rmr_sym_stats( void *vtable, int level )
396 Sym_ele *eptr; /* pointer into the elements */
405 table = (Sym_tab *) vtable;
406 sym_tab = table->symlist;
408 for( i = 0; i < table->size; i++ )
413 for( eptr = sym_tab[i]; eptr; eptr = eptr->next )
417 if( eptr->class ) { // a string key
418 fprintf( stderr, " symtab stats: sym: (%d) key=%s val@=%p ref=%ld mod=%lu\n", i, eptr->name, eptr->val, eptr->rcount, eptr->mcount );
420 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 );
428 if( ch_count > max_chain )
430 max_chain = ch_count;
437 fprintf( stderr, "symtab stats: sym: (%d) chained=%ld\n", i, ch_count );
442 fprintf( stderr, "symtab stats: sym: longest chain: idx=%d has %ld elsements):\n", maxi, max_chain );
443 for( eptr = sym_tab[maxi]; eptr; eptr = eptr->next ) {
445 fprintf( stderr, "\t%s\n", eptr->name );
447 fprintf( stderr, "\t%lu (numeric key)\n", (unsigned long) eptr->nkey );
452 fprintf( stderr, "symtab stats: sym:%ld(size) %ld(inhab) %ld(occupied) %ld(dead) %ld(maxch) %d(>2per)\n",
453 table->size, table->inhabitants, table->size - empty, table->deaths, max_chain, twoper );
457 Drive a user callback function for each entry in a class. It is safe for
458 the user to delete the element as we capture a next pointer before
459 calling their function.
461 extern void rmr_sym_foreach_class( void *vst, unsigned int class, void (* user_fun)( void*, void*, const char*, void*, void* ), void *user_data )
466 Sym_ele *next; /* allows user to delete the node(s) we return */
469 st = (Sym_tab *) vst;
471 if( st && (list = st->symlist) != NULL && user_fun != NULL )
472 for( i = 0; i < st->size; i++ )
473 for( se = list[i]; se; se = next ) /* using next allows user to delet via this */
476 if( class == se->class ) {
477 user_fun( st, se, se->name, se->val, user_data );