Packet tunneling over UDP, multiple channels
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
 
 
 
 

136 lines
3.3 KiB

  1. #include <stdlib.h>
  2. #include <string.h>
  3. #include "htable.h"
  4. //// Generic hash table implementation
  5. // Determine the index for a key. On match, it returns the index into
  6. // the table. On mismatch it returns -i-1 for the first free spot
  7. // where the keyed element would fit.
  8. static int htindex(htable *table,unsigned char *key) {
  9. if ( table->data == 0 ) {
  10. table->data = calloc( 256, sizeof( unsigned char* ) );
  11. table->size = 256;
  12. }
  13. unsigned int hash = (*table->hashcode)( table, key ) % table->size;
  14. unsigned int i = hash;
  15. int hole = -1;
  16. for ( ;; ) {
  17. unsigned char *x = table->data[ i++ ];
  18. if ( x == 0 ) {
  19. return ( hole >= 0 )? -hole : - (int) i;
  20. }
  21. if ( x == (unsigned char *)1 ) {
  22. if ( hole < 0 ) {
  23. hole = i;
  24. }
  25. } else if ( memcmp( x + table->offset, key, table->esize ) == 0 ) {
  26. return i-1;
  27. }
  28. if ( i >= table->size ) {
  29. i = 0;
  30. }
  31. if ( i == hash ) {
  32. break;
  33. }
  34. }
  35. return -1;
  36. }
  37. // Find the keyed element, and assign the x pointer, or assign 0.
  38. // Returns 1 if element is found and 0 otherwise.
  39. int htfind(htable *table,void *key,unsigned char **x) {
  40. pthread_mutex_lock( &table->lock );
  41. int i = htindex( table, key );
  42. if ( i < 0 ) {
  43. *x = 0;
  44. pthread_mutex_unlock( &table->lock );
  45. return 0;
  46. }
  47. *x = table->data[ i ];
  48. pthread_mutex_unlock( &table->lock );
  49. return 1;
  50. }
  51. // Forward
  52. static void htgrow(htable *table);
  53. // Add the given element.
  54. void htadd(htable *table,unsigned char *p) {
  55. pthread_mutex_lock( &table->lock );
  56. if ( table->fill >= table->size / 2 ) {
  57. htgrow( table );
  58. }
  59. int i = htindex( table, p + table->offset );
  60. if ( i < 0 ) {
  61. i = -i - 1;
  62. if ( table->data[ i ] != 0 ) {
  63. table->holes--;
  64. } else {
  65. table->fill++;
  66. }
  67. } else {
  68. // There is a match already what to do?
  69. }
  70. table->data[ i ] = p;
  71. pthread_mutex_unlock( &table->lock );
  72. }
  73. // Return the next element starting at i, or 0 if there are no more.
  74. // Also increment the index to be of the element + 1, or -1 if there
  75. // are no more elements.
  76. static unsigned char *htnext(htable *table,int *i) {
  77. if ( *i < 0 ) {
  78. return 0;
  79. }
  80. unsigned char **p = table->data + *i;
  81. unsigned char **e = table->data + table->size;
  82. for ( ; p < e; p++ ) {
  83. (*i) += 1;
  84. if ( *p != 0 && *p != (unsigned char*)1 ) {
  85. return *p;
  86. }
  87. }
  88. (*i) = -1;
  89. return 0;
  90. }
  91. static void htrehash(htable *table,unsigned int size) {
  92. htable old = *table;
  93. table->data = calloc( size, sizeof( unsigned char * ) );
  94. table->size = size;
  95. table->fill = 0;
  96. table->holes = 0;
  97. int i = 0;
  98. unsigned char *p;
  99. while ( ( p = htnext( &old, &i ) ) != 0 ) {
  100. htadd( table, p );
  101. }
  102. free( old.data );
  103. }
  104. static void htgrow(htable *table) {
  105. if ( table->data == 0 ) {
  106. table->data = calloc( 256, sizeof( unsigned char * ) );
  107. table->size = 256;
  108. table->fill = 0;
  109. table->holes = 0;
  110. return;
  111. }
  112. htrehash( table, table->size << 8 );
  113. }
  114. // Delete the given element.
  115. void htdelete(htable *table,unsigned char *p) {
  116. pthread_mutex_lock( &table->lock );
  117. int i = htindex( table, p + table->offset );
  118. if ( i >= 0 ) {
  119. table->data[ i ] = (unsigned char *)1;
  120. table->holes += 1;
  121. if ( table->holes > table->fill / 2 ) {
  122. htrehash( table, table->size );
  123. }
  124. }
  125. pthread_mutex_unlock( &table->lock );
  126. }