Add transport provider status to message buffer
[ric-plt/lib/rmr.git] / src / rmr / common / src / symtab.c
1 // : vi ts=4 sw=4 noet :
2 /*
3 ==================================================================================
4         Copyright (c) 2019 Nokia
5         Copyright (c) 2018-2019 AT&T Intellectual Property.
6
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
10
11            http://www.apache.org/licenses/LICENSE-2.0
12
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 ==================================================================================
19 */
20
21 /*
22 ------------------------------------------------------------------------------
23 Mnemonic:       symtab.c
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
26                         original copyright.
27
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.
35
36 Date:           11 Feb 2000
37 Author:         E. Scott Daniels
38
39 Mod:            2016 23 Feb - converted Symtab refs so that caller need only a
40                                 void pointer to use and struct does not need to be exposed.
41                         2018 30 Nov - Augmented from original form (see above).
42 ------------------------------------------------------------------------------
43 */
44
45 #include <stdio.h>
46 #include <unistd.h>
47 #include <string.h>
48 #include <stdlib.h>
49 #include <memory.h>
50 #include <netdb.h>
51
52 #include "rmr_symtab.h"
53
54 //-----------------------------------------------------------------------------------------------
55
56 typedef struct Sym_ele
57 {
58         struct Sym_ele *next;   /* pointer at next element in list */
59         struct Sym_ele *prev;   /* larger table, easier deletes */
60         const char *name;               /* symbol name */
61         uint64_t nkey;                  // the numeric key
62         void *val;              /* user data associated with name */
63         unsigned long mcount;   /* modificaitons to value */
64         unsigned long rcount;   /* references to symbol */
65         //unsigned int flags;
66         unsigned int class;             /* helps divide things up and allows for duplicate names */
67 } Sym_ele;
68
69 typedef struct Sym_tab {
70         Sym_ele **symlist;                      /* pointer to list of element pointerss */
71         long    inhabitants;            /* number of active residents */
72         long    deaths;                         /* number of deletes */
73         long    size;
74 } Sym_tab;
75
76 // -------------------- internal ------------------------------------------------------------------
77
78 static int sym_hash( const char *n, long size )
79 {
80         const char *p;
81         long t = 0;
82         unsigned long tt = 0;
83         unsigned long x = 79;
84
85         for( p = n; *p; p++ )      /* a bit of magic */
86                 t = (t * 79 ) + *p;
87
88         if( t < 0 )
89                 t = ~t;
90
91         return (int ) (t % size);
92 }
93
94 /* delete element pointed to by eptr at hash loc hv */
95 static void del_ele( Sym_tab *table, int hv, Sym_ele *eptr )
96 {
97         Sym_ele **sym_tab;
98
99         sym_tab = table->symlist;
100
101         if( eptr )         /* unchain it */
102         {
103                 if( eptr->prev )
104                         eptr->prev->next = eptr->next;
105                 else
106                         sym_tab[hv] = eptr->next;
107
108                 if( eptr->next )
109                         eptr->next->prev = eptr->prev;
110
111                 if( eptr->class && eptr->name ) {                               // class 0 entries are numeric, so name is NOT a pointer
112                         free( (void *) eptr->name );                    // and if free fails, what?  panic?
113                 }
114
115                 free( eptr );
116
117                 table->deaths++;
118                 table->inhabitants--;
119         }
120 }
121
122 /*
123         Determine if these are the same.
124 */
125 static inline int same( unsigned int c1, unsigned int c2, const char *s1, const char* s2 )
126 {
127         if( c1 != c2 )
128                 return 0;               /* different class - not the same */
129
130         if( *s1 == *s2 && strcmp( s1, s2 ) == 0 )
131                 return 1;
132         return 0;
133 }
134
135 /*
136         Generic routine to put something into the table
137         called by sym_map or sym_put since the logic for each is pretty
138         much the same.
139 */
140 static int putin( Sym_tab *table, const char *name, unsigned int class, void *val ) {
141         Sym_ele *eptr;                  /* pointer into hash table */
142         Sym_ele **sym_tab;      /* pointer into hash table */
143         int hv;                 /* hash value */
144         int rc = 0;             /* assume it existed */
145         uint64_t nkey = 0;              // numeric key if class == 0
146
147         sym_tab = table->symlist;
148
149         if( class ) {                                                           // string key
150                 hv = sym_hash( name, table->size );             // hash it
151                 for( eptr=sym_tab[hv]; eptr && ! same( class, eptr->class, eptr->name, name); eptr=eptr->next );
152         } else {
153                 nkey = *((uint64_t *) name);
154                 hv = nkey % table->size;                                        // just hash the number
155                 for( eptr=sym_tab[hv]; eptr && eptr->nkey != nkey; eptr=eptr->next );
156         }
157
158         if( ! eptr ) {                  // not found above, so add
159                 rc++;
160                 table->inhabitants++;
161
162                 eptr = (Sym_ele *) malloc( sizeof( Sym_ele) );
163                 if( ! eptr ) {
164                         fprintf( stderr, "[FAIL] symtab/putin: out of memory\n" );
165                         return -1;
166                 }
167
168                 eptr->prev = NULL;
169                 eptr->class = class;
170                 eptr->mcount = eptr->rcount = 0;        /* init counters */
171                 eptr->val = NULL;
172                 eptr->nkey = nkey;
173                 if( class ) {
174                         eptr->name = strdup( name );
175                 } else {
176                         eptr->name = NULL;                              // for a numeric key, just save the value
177                 }
178                 eptr->next = sym_tab[hv];                       // add to head of list
179                 sym_tab[hv] = eptr;
180                 if( eptr->next )
181                         eptr->next->prev = eptr;         /* chain back to new one */
182         }
183
184         eptr->mcount++;
185
186         eptr->val = val;
187
188         return rc;
189 }
190
191 // -------------------- visible  ------------------------------------------------------------------
192
193 /* delete all elements in the table */
194 extern void rmr_sym_clear( void *vtable )
195 {
196         Sym_tab *table;
197         Sym_ele **sym_tab;
198         int i;
199
200         table = (Sym_tab *) vtable;
201         sym_tab = table->symlist;
202
203         for( i = 0; i < table->size; i++ )
204                 while( sym_tab[i] )
205                         del_ele( table, i, sym_tab[i] );
206 }
207
208 /*
209         Clear and then free the whole thing.
210 */
211 extern void rmr_sym_free( void *vtable ) {
212         Sym_tab *table;
213
214         table = (Sym_tab *) vtable;
215
216         if( table == NULL )
217                 return;
218
219         rmr_sym_clear( vtable );
220         free( table->symlist );
221         free( table );
222 }
223
224 extern void rmr_sym_dump( void *vtable )
225 {
226         Sym_tab *table;
227         int i;
228         Sym_ele *eptr;
229         Sym_ele **sym_tab;
230
231         table = (Sym_tab *) vtable;
232         sym_tab = table->symlist;
233
234         for( i = 0; i < table->size; i++ )
235         {
236                 if( sym_tab[i] )
237                 for( eptr = sym_tab[i]; eptr; eptr = eptr->next )
238                 {
239                         if( eptr->val && eptr->class ) {
240                                 fprintf( stderr, "key=%s val@=%p\n", eptr->name, eptr->val );
241                         } else {
242                                 fprintf( stderr, "nkey=%lu val@=%p\n", (unsigned long) eptr->nkey, eptr->val );
243                         }
244                 }
245         }
246 }
247
248 /*
249         Allocate a table the size requested - best if size is prime.
250         Returns a pointer to the management block (handle) or NULL on failure.
251 */
252 extern void *rmr_sym_alloc( int size )
253 {
254         int i;
255         Sym_tab *table;
256
257         if( size < 11 )     /* provide a bit of sanity */
258                 size = 11;
259
260         if( (table = (Sym_tab *) malloc( sizeof( Sym_tab ))) == NULL )
261         {
262                 fprintf( stderr, "rmr_sym_alloc: unable to get memory for symtable (%d elements)", size );
263                 return NULL;
264         }
265
266         memset( table, 0, sizeof( *table ) );
267
268         if((table->symlist = (Sym_ele **) malloc( sizeof( Sym_ele *) * size )))
269         {
270                 memset( table->symlist, 0, sizeof( Sym_ele *) * size );
271                 table->size = size;
272         }
273         else
274         {
275                 fprintf( stderr, "sym_alloc: unable to get memory for %d elements", size );
276                 return NULL;
277         }
278
279         return (void *) table;    /* user might want to know what the size is */
280 }
281
282 /*
283         Delete an element given name/class or numeric key (class 0).
284 */
285 extern void rmr_sym_del( void *vtable, const char *name, unsigned int class )
286 {
287         Sym_tab *table;
288         Sym_ele **sym_tab;
289         Sym_ele *eptr;                  /* pointer into hash table */
290         int hv;                 /* hash value */
291         uint64_t        nkey;           // class 0, name points to integer not string
292
293         table = (Sym_tab *) vtable;
294         sym_tab = table->symlist;
295
296         if( class ) {
297                 hv = sym_hash( name, table->size );
298                 for(eptr=sym_tab[hv]; eptr &&  ! same(class, eptr->class, eptr->name, name); eptr=eptr->next );
299         } else {
300                 nkey = *((uint64_t *) name);
301                 hv = nkey % table->size;                        // just hash the number
302                 for( eptr=sym_tab[hv]; eptr && eptr->nkey != nkey; eptr=eptr->next );
303         }
304
305         del_ele( table, hv, eptr );    /* ignors null ptr, so safe to always call */
306 }
307
308 /*
309         Delete element by numberic key.
310 */
311 extern void *rmr_sym_ndel(  void *vtable, uint64_t key ) {
312         rmr_sym_del( vtable, (const char *) &key, 0 );
313 }
314
315
316 extern void *rmr_sym_get( void *vtable, const char *name, unsigned int class )
317 {
318         Sym_tab *table;
319         Sym_ele **sym_tab;
320         Sym_ele *eptr;                  // element from table
321         int hv;                 // hash value of key
322         uint64_t nkey;                  // numeric key if class 0
323
324         table = (Sym_tab *) vtable;
325         sym_tab = table->symlist;
326
327         if( class ) {
328                 hv = sym_hash( name, table->size );
329                 for(eptr=sym_tab[hv]; eptr &&  ! same(class, eptr->class, eptr->name, name); eptr=eptr->next );
330         } else {
331                 nkey = *((uint64_t *) name);
332                 hv = nkey % table->size;                        // just hash the number
333                 for( eptr=sym_tab[hv]; eptr && eptr->nkey != nkey; eptr=eptr->next );
334         }
335
336         if( eptr )
337         {
338                 eptr->rcount++;
339                 return eptr->val;
340         }
341
342         return NULL;
343 }
344
345 /*
346         Retrieve the data referenced by a numerical key.
347 */
348 extern void *rmr_sym_pull(  void *vtable, uint64_t key ) {
349         return rmr_sym_get( vtable, (const char *) &key, 0 );
350 }
351
352 /*
353         Put an element with a string key into the table. Replaces the element
354         if it was already there.  Class must be >0 and if not 1 will be forced.
355         (class 0 keys are numeric).
356         Returns 1 if new, 0 if existed.
357 */
358 extern int rmr_sym_put( void *vtable, const char *name, unsigned int class, void *val )
359 {
360         Sym_tab *table;
361
362         if( class == 0 ) {
363                 class = 1;
364         }
365
366         table = (Sym_tab *) vtable;
367         return putin( table, name, class, val );
368 }
369
370 /*
371         Add a new entry assuming that the key is an unsigned, 64 bit, integer.
372
373         Returns 1 if new, 0 if existed
374 */
375 extern int rmr_sym_map( void *vtable, uint64_t key, void *val ) {
376         Sym_tab *table;
377
378         table = (Sym_tab *) vtable;
379         return putin( table, (const char *) &key, 0, val );
380 }
381
382 /*
383         Dump some statistics to stderr dev. Higher level is the more info dumpped
384 */
385 extern void rmr_sym_stats( void *vtable, int level )
386 {
387         Sym_tab *table;
388         Sym_ele *eptr;    /* pointer into the elements */
389         Sym_ele **sym_tab;
390         int i;
391         int empty = 0;
392         long ch_count;
393         long max_chain = 0;
394         int maxi = 0;
395         int twoper = 0;
396
397         table = (Sym_tab *) vtable;
398         sym_tab = table->symlist;
399
400         for( i = 0; i < table->size; i++ )
401         {
402                 ch_count = 0;
403                 if( sym_tab[i] )
404                 {
405                         for( eptr = sym_tab[i]; eptr; eptr = eptr->next )
406                         {
407                                 ch_count++;
408                                 if( level > 3 ) {
409                                         if( eptr->class  ) {                                    // a string key
410                                                 fprintf( stderr, "sym: (%d) key=%s val@=%p ref=%ld mod=%lu\n", i, eptr->name, eptr->val, eptr->rcount, eptr->mcount );
411                                         } else {
412                                                 fprintf( stderr, "sym: (%d) key=%lu val@=%p ref=%ld mod=%lu\n", i, (unsigned long) eptr->nkey, eptr->val, eptr->rcount, eptr->mcount );
413                                         }
414                                 }
415                         }
416                 }
417                 else
418                         empty++;
419
420                 if( ch_count > max_chain )
421                 {
422                         max_chain = ch_count;
423                         maxi = i;
424                 }
425                 if( ch_count > 1 )
426                         twoper++;
427
428                 if( level > 2 )
429                         fprintf( stderr, "sym: (%d) chained=%ld\n", i, ch_count );
430         }
431
432         if( level > 1 )
433         {
434                 fprintf( stderr, "sym: longest chain: idx=%d has %ld elsements):\n", maxi, max_chain );
435                 for( eptr = sym_tab[maxi]; eptr; eptr = eptr->next ) {
436                         if( eptr->class ) {
437                                 fprintf( stderr, "\t%s\n", eptr->name );
438                         } else {
439                                 fprintf( stderr, "\t%lu (numeric key)\n", (unsigned long) eptr->nkey );
440                         }
441                 }
442         }
443
444         fprintf( stderr, "sym:%ld(size)  %ld(inhab) %ld(occupied) %ld(dead) %ld(maxch) %d(>2per)\n",
445                         table->size, table->inhabitants, table->size - empty, table->deaths, max_chain, twoper );
446 }
447
448 /*
449         Drive a user callback function for each entry in a class. It is safe for
450         the user to delete the element as we capture a next pointer before
451         calling their function.
452 */
453 extern void rmr_sym_foreach_class( void *vst, unsigned int class, void (* user_fun)( void*, void*, const char*, void*, void* ), void *user_data )
454 {
455         Sym_tab *st;
456         Sym_ele **list;
457         Sym_ele *se;
458         Sym_ele *next;          /* allows user to delete the node(s) we return */
459         int     i;
460
461         st = (Sym_tab *) vst;
462
463         if( st && (list = st->symlist) != NULL && user_fun != NULL )
464                 for( i = 0; i < st->size; i++ )
465                         for( se = list[i]; se; se = next )              /* using next allows user to delet via this */
466                         {
467                                 next = se->next;
468                                 if( class == se->class ) {
469                                         user_fun( st, se, se->name, se->val, user_data );
470                                 }
471                         }
472 }