1 // : vi ts=4 sw=4 noet :
3 ==================================================================================
4 Copyright (c) 2019 Nokia
5 Copyright (c) 2018-2019 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 - externally visible names given a rmr_ extension as it's being
32 incorporated into the RIC msg routing library and will be
33 available to user applications.
36 Author: E. Scott Daniels
38 Mod: 2016 23 Feb - converted Symtab refs so that caller need only a
39 void pointer to use and struct does not need to be exposed.
40 2018 30 Nov - Augmented from original form (see above).
41 ------------------------------------------------------------------------------
50 #include "rmr_symtab.h"
52 //-----------------------------------------------------------------------------------------------
54 typedef struct Sym_ele
56 struct Sym_ele *next; /* pointer at next element in list */
57 struct Sym_ele *prev; /* larger table, easier deletes */
58 const char *name; /* symbol name */
59 unsigned int nkey; // the numeric key
60 void *val; /* user data associated with name */
61 unsigned long mcount; /* modificaitons to value */
62 unsigned long rcount; /* references to symbol */
64 unsigned int class; /* helps divide things up and allows for duplicate names */
67 typedef struct Sym_tab {
68 Sym_ele **symlist; /* pointer to list of element pointerss */
69 long inhabitants; /* number of active residents */
70 long deaths; /* number of deletes */
74 // -------------------- internal ------------------------------------------------------------------
76 static int sym_hash( const char *n, long size )
83 for( p = n; *p; p++ ) /* a bit of magic */
89 return (int ) (t % size);
92 /* delete element pointed to by eptr at hash loc hv */
93 static void del_ele( Sym_tab *table, int hv, Sym_ele *eptr )
97 sym_tab = table->symlist;
99 if( eptr ) /* unchain it */
102 eptr->prev->next = eptr->next;
104 sym_tab[hv] = eptr->next;
107 eptr->next->prev = eptr->prev;
109 if( eptr->class && eptr->name ) { // class 0 entries are numeric, so name is NOT a pointer
110 free( (void *) eptr->name ); // and if free fails, what? panic?
116 table->inhabitants--;
121 Determine if these are the same.
123 static inline int same( unsigned int c1, unsigned int c2, const char *s1, const char* s2 )
126 return 0; /* different class - not the same */
128 if( *s1 == *s2 && strcmp( s1, s2 ) == 0 )
134 Generic routine to put something into the table
135 called by sym_map or sym_put since the logic for each is pretty
138 static int putin( Sym_tab *table, const char *name, unsigned int class, void *val ) {
139 Sym_ele *eptr; /* pointer into hash table */
140 Sym_ele **sym_tab; /* pointer into hash table */
141 int hv; /* hash value */
142 int rc = 0; /* assume it existed */
143 unsigned int nkey = 0; // numeric key if class == 0
145 sym_tab = table->symlist;
147 if( class ) { // string key
148 hv = sym_hash( name, table->size ); // hash it
149 for( eptr=sym_tab[hv]; eptr && ! same( class, eptr->class, eptr->name, name); eptr=eptr->next );
151 nkey = *((int *) name);
152 hv = nkey % table->size; // just hash the number
153 for( eptr=sym_tab[hv]; eptr && eptr->nkey != nkey; eptr=eptr->next );
156 if( ! eptr ) { // not found above, so add
158 table->inhabitants++;
160 eptr = (Sym_ele *) malloc( sizeof( Sym_ele) );
162 fprintf( stderr, "[FAIL] symtab/putin: out of memory\n" );
168 eptr->mcount = eptr->rcount = 0; /* init counters */
172 eptr->name = strdup( name );
174 eptr->name = NULL; // for a numeric key, just save the value
176 eptr->next = sym_tab[hv]; // add to head of list
179 eptr->next->prev = eptr; /* chain back to new one */
189 // -------------------- visible ------------------------------------------------------------------
191 /* delete all elements in the table */
192 extern void rmr_sym_clear( void *vtable )
198 table = (Sym_tab *) vtable;
199 sym_tab = table->symlist;
201 for( i = 0; i < table->size; i++ )
203 del_ele( table, i, sym_tab[i] );
207 Clear and then free the whole thing.
209 extern void rmr_sym_free( void *vtable ) {
212 table = (Sym_tab *) vtable;
217 rmr_sym_clear( vtable );
218 free( table->symlist );
222 extern void rmr_sym_dump( void *vtable )
229 table = (Sym_tab *) vtable;
230 sym_tab = table->symlist;
232 for( i = 0; i < table->size; i++ )
235 for( eptr = sym_tab[i]; eptr; eptr = eptr->next )
237 if( eptr->val && eptr->class ) {
238 fprintf( stderr, "key=%s val@=%p\n", eptr->name, eptr->val );
240 fprintf( stderr, "nkey=%d val@=%p\n", eptr->nkey, eptr->val );
247 Allocate a table the size requested - best if size is prime.
248 Returns a pointer to the management block (handle) or NULL on failure.
250 extern void *rmr_sym_alloc( int size )
255 if( size < 11 ) /* provide a bit of sanity */
258 if( (table = (Sym_tab *) malloc( sizeof( Sym_tab ))) == NULL )
260 fprintf( stderr, "rmr_sym_alloc: unable to get memory for symtable (%d elements)", size );
264 memset( table, 0, sizeof( *table ) );
266 if((table->symlist = (Sym_ele **) malloc( sizeof( Sym_ele *) * size )))
268 memset( table->symlist, 0, sizeof( Sym_ele *) * size );
273 fprintf( stderr, "sym_alloc: unable to get memory for %d elements", size );
277 return (void *) table; /* user might want to know what the size is */
281 Delete an element given name/class or numeric key (class 0).
283 extern void rmr_sym_del( void *vtable, const char *name, unsigned int class )
287 Sym_ele *eptr; /* pointer into hash table */
288 int hv; /* hash value */
289 unsigned int nkey; // class 0, name points to integer not string
291 table = (Sym_tab *) vtable;
292 sym_tab = table->symlist;
295 hv = sym_hash( name, table->size );
296 for(eptr=sym_tab[hv]; eptr && ! same(class, eptr->class, eptr->name, name); eptr=eptr->next );
298 nkey = *((int *) name);
299 hv = nkey % table->size; // just hash the number
300 for( eptr=sym_tab[hv]; eptr && eptr->nkey != nkey; eptr=eptr->next );
303 del_ele( table, hv, eptr ); /* ignors null ptr, so safe to always call */
307 Delete element by numberic key.
309 extern void *rmr_sym_ndel( void *vtable, int key ) {
310 rmr_sym_del( vtable, (const char *) &key, 0 );
314 extern void *rmr_sym_get( void *vtable, const char *name, unsigned int class )
318 Sym_ele *eptr; // element from table
319 int hv; // hash value of key
320 unsigned int nkey; // numeric key if class 0
322 table = (Sym_tab *) vtable;
323 sym_tab = table->symlist;
326 hv = sym_hash( name, table->size );
327 for(eptr=sym_tab[hv]; eptr && ! same(class, eptr->class, eptr->name, name); eptr=eptr->next );
329 nkey = *((int *) name);
330 hv = nkey % table->size; // just hash the number
331 for( eptr=sym_tab[hv]; eptr && eptr->nkey != nkey; eptr=eptr->next );
344 Retrieve the data referenced by a numerical key.
346 extern void *rmr_sym_pull( void *vtable, int key ) {
347 return rmr_sym_get( vtable, (const char *) &key, 0 );
351 Put an element with a string key into the table. Replaces the element
352 if it was already there. Class must be >0 and if not 1 will be forced.
353 (class 0 keys are numeric).
354 Returns 1 if new, 0 if existed.
356 extern int rmr_sym_put( void *vtable, const char *name, unsigned int class, void *val )
364 table = (Sym_tab *) vtable;
365 return putin( table, name, class, val );
369 Add a new entry assuming that the key is an unsigned integer.
371 Returns 1 if new, 0 if existed
373 extern int rmr_sym_map( void *vtable, unsigned int key, void *val ) {
376 table = (Sym_tab *) vtable;
377 return putin( table, (const char *) &key, 0, val );
381 Dump some statistics to stderr dev. Higher level is the more info dumpped
383 extern void rmr_sym_stats( void *vtable, int level )
386 Sym_ele *eptr; /* pointer into the elements */
395 table = (Sym_tab *) vtable;
396 sym_tab = table->symlist;
398 for( i = 0; i < table->size; i++ )
403 for( eptr = sym_tab[i]; eptr; eptr = eptr->next )
407 if( eptr->class ) { // a string key
408 fprintf( stderr, "sym: (%d) key=%s val@=%p ref=%ld mod=%lu\n", i, eptr->name, eptr->val, eptr->rcount, eptr->mcount );
410 fprintf( stderr, "sym: (%d) key=%d val@=%p ref=%ld mod=%lu\n", i, eptr->nkey, eptr->val, eptr->rcount, eptr->mcount );
418 if( ch_count > max_chain )
420 max_chain = ch_count;
427 fprintf( stderr, "sym: (%d) chained=%ld\n", i, ch_count );
432 fprintf( stderr, "sym: longest chain: idx=%d has %ld elsements):\n", maxi, max_chain );
433 for( eptr = sym_tab[maxi]; eptr; eptr = eptr->next ) {
435 fprintf( stderr, "\t%s\n", eptr->name );
437 fprintf( stderr, "\t%d (numeric key)\n", eptr->nkey );
442 fprintf( stderr, "sym:%ld(size) %ld(inhab) %ld(occupied) %ld(dead) %ld(maxch) %d(>2per)\n",
443 table->size, table->inhabitants, table->size - empty, table->deaths, max_chain, twoper );
447 Drive a user callback function for each entry in a class. It is safe for
448 the user to delete the element as we capture a next pointer before
449 calling their function.
451 extern void rmr_sym_foreach_class( void *vst, unsigned int class, void (* user_fun)( void*, void*, const char*, void*, void* ), void *user_data )
456 Sym_ele *next; /* allows user to delete the node(s) we return */
459 st = (Sym_tab *) vst;
461 if( st && (list = st->symlist) != NULL && user_fun != NULL )
462 for( i = 0; i < st->size; i++ )
463 for( se = list[i]; se; se = next ) /* using next allows user to delet via this */
466 if( class == se->class ) {
467 user_fun( st, se, se->name, se->val, user_data );