Add new message types
[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         if( (table = (Sym_tab *) vtable) == NULL ) {
325                 return NULL;
326         }
327
328         sym_tab = table->symlist;
329
330         if( class ) {
331                 hv = sym_hash( name, table->size );
332                 for(eptr=sym_tab[hv]; eptr &&  ! same(class, eptr->class, eptr->name, name); eptr=eptr->next );
333         } else {
334                 nkey = *((uint64_t *) name);
335                 hv = nkey % table->size;                        // just hash the number
336                 for( eptr=sym_tab[hv]; eptr && eptr->nkey != nkey; eptr=eptr->next );
337         }
338
339         if( eptr )
340         {
341                 eptr->rcount++;
342                 return eptr->val;
343         }
344
345         return NULL;
346 }
347
348 /*
349         Retrieve the data referenced by a numerical key.
350 */
351 extern void *rmr_sym_pull(  void *vtable, uint64_t key ) {
352         return rmr_sym_get( vtable, (const char *) &key, 0 );
353 }
354
355 /*
356         Put an element with a string key into the table. Replaces the element
357         if it was already there.  Class must be >0 and if not 1 will be forced.
358         (class 0 keys are numeric).
359         Returns 1 if new, 0 if existed.
360 */
361 extern int rmr_sym_put( void *vtable, const char *name, unsigned int class, void *val )
362 {
363         Sym_tab *table;
364
365         if( class == 0 ) {
366                 class = 1;
367         }
368
369         table = (Sym_tab *) vtable;
370         return putin( table, name, class, val );
371 }
372
373 /*
374         Add a new entry assuming that the key is an unsigned, 64 bit, integer.
375
376         Returns 1 if new, 0 if existed
377 */
378 extern int rmr_sym_map( void *vtable, uint64_t key, void *val ) {
379         Sym_tab *table;
380
381         table = (Sym_tab *) vtable;
382         return putin( table, (const char *) &key, 0, val );
383 }
384
385 /*
386         Dump some statistics to stderr dev. Higher level is the more info dumpped
387 */
388 extern void rmr_sym_stats( void *vtable, int level )
389 {
390         Sym_tab *table;
391         Sym_ele *eptr;    /* pointer into the elements */
392         Sym_ele **sym_tab;
393         int i;
394         int empty = 0;
395         long ch_count;
396         long max_chain = 0;
397         int maxi = 0;
398         int twoper = 0;
399
400         table = (Sym_tab *) vtable;
401         sym_tab = table->symlist;
402
403         for( i = 0; i < table->size; i++ )
404         {
405                 ch_count = 0;
406                 if( sym_tab[i] )
407                 {
408                         for( eptr = sym_tab[i]; eptr; eptr = eptr->next )
409                         {
410                                 ch_count++;
411                                 if( level > 3 ) {
412                                         if( eptr->class  ) {                                    // a string key
413                                                 fprintf( stderr, "sym: (%d) key=%s val@=%p ref=%ld mod=%lu\n", i, eptr->name, eptr->val, eptr->rcount, eptr->mcount );
414                                         } else {
415                                                 fprintf( stderr, "sym: (%d) key=%lu val@=%p ref=%ld mod=%lu\n", i, (unsigned long) eptr->nkey, eptr->val, eptr->rcount, eptr->mcount );
416                                         }
417                                 }
418                         }
419                 }
420                 else
421                         empty++;
422
423                 if( ch_count > max_chain )
424                 {
425                         max_chain = ch_count;
426                         maxi = i;
427                 }
428                 if( ch_count > 1 )
429                         twoper++;
430
431                 if( level > 2 )
432                         fprintf( stderr, "sym: (%d) chained=%ld\n", i, ch_count );
433         }
434
435         if( level > 1 )
436         {
437                 fprintf( stderr, "sym: longest chain: idx=%d has %ld elsements):\n", maxi, max_chain );
438                 for( eptr = sym_tab[maxi]; eptr; eptr = eptr->next ) {
439                         if( eptr->class ) {
440                                 fprintf( stderr, "\t%s\n", eptr->name );
441                         } else {
442                                 fprintf( stderr, "\t%lu (numeric key)\n", (unsigned long) eptr->nkey );
443                         }
444                 }
445         }
446
447         fprintf( stderr, "sym:%ld(size)  %ld(inhab) %ld(occupied) %ld(dead) %ld(maxch) %d(>2per)\n",
448                         table->size, table->inhabitants, table->size - empty, table->deaths, max_chain, twoper );
449 }
450
451 /*
452         Drive a user callback function for each entry in a class. It is safe for
453         the user to delete the element as we capture a next pointer before
454         calling their function.
455 */
456 extern void rmr_sym_foreach_class( void *vst, unsigned int class, void (* user_fun)( void*, void*, const char*, void*, void* ), void *user_data )
457 {
458         Sym_tab *st;
459         Sym_ele **list;
460         Sym_ele *se;
461         Sym_ele *next;          /* allows user to delete the node(s) we return */
462         int     i;
463
464         st = (Sym_tab *) vst;
465
466         if( st && (list = st->symlist) != NULL && user_fun != NULL )
467                 for( i = 0; i < st->size; i++ )
468                         for( se = list[i]; se; se = next )              /* using next allows user to delet via this */
469                         {
470                                 next = se->next;
471                                 if( class == se->class ) {
472                                         user_fun( st, se, se->name, se->val, user_data );
473                                 }
474                         }
475 }