Last active
September 27, 2021 17:19
-
-
Save dtinth/c88221fd422b8e7a4be1880a2985c014 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
#include <stdlib.h> | |
#include <time.h> | |
int iCurNumChannels; | |
int vecChannelOrder[100]; | |
unsigned int vecChannels[100]; | |
#define INVALID_CHANNEL_ID 101 | |
void InitChannel(int iNewChanID, unsigned int InetAddr) | |
{ | |
vecChannels[iNewChanID] = InetAddr; | |
} | |
int CompareAddresses(unsigned int InetAddr1, unsigned int InetAddr2) | |
{ | |
// return InetAddr1 < InetAddr2 ? -1 : InetAddr1 > InetAddr2 ? 1 | |
// : 0; | |
return (int)InetAddr1 - (int)InetAddr2; | |
} | |
unsigned int GenerateRandomAddress() | |
{ | |
unsigned int iRand = rand(); | |
if (rand() % 2 == 0) | |
{ | |
// rand() does not return negative numbers, so force iRand to go into negative range. | |
iRand |= 1 << 31; | |
} | |
return iRand; | |
} | |
void DumpChannels() | |
{ | |
int i; | |
for (i = 0; i < iCurNumChannels; i++) | |
{ | |
printf("%d: %d => %u\n", i, vecChannelOrder[i], vecChannels[vecChannelOrder[i]]); | |
} | |
} | |
int FindChannel(int CheckAddr) | |
{ | |
int iNewChanID = INVALID_CHANNEL_ID; | |
int l = 0, r = iCurNumChannels, i; | |
// use binary search to find the channel | |
while (r > l) | |
{ | |
int t = (r + l) / 2; | |
int cmp = CompareAddresses(CheckAddr, vecChannels[vecChannelOrder[t]]); | |
if (cmp == 0) | |
{ | |
// address and port match | |
return vecChannelOrder[t]; | |
} | |
if (cmp < 0) | |
{ | |
l = t + 1; | |
} | |
else | |
{ | |
r = t; | |
} | |
} | |
// allocate a new channel | |
i = iCurNumChannels++; // save index of free channel and increment count | |
iNewChanID = vecChannelOrder[i]; | |
InitChannel(iNewChanID, CheckAddr); | |
// now l == r == position in vecChannelOrder to insert iNewChanID | |
// move channel IDs up by one starting at the top and working down | |
while (i > r) | |
{ | |
int j = i--; | |
vecChannelOrder[j] = vecChannelOrder[i]; | |
} | |
// insert the new channel ID in the correct place | |
vecChannelOrder[i] = iNewChanID; | |
return iNewChanID; | |
} | |
int seed = 78; | |
int main() | |
{ | |
int i; | |
int iMaxNumChannels = 100; | |
srand(seed); | |
// Reset the state | |
iCurNumChannels = 0; | |
for (i = 0; i < iMaxNumChannels; i++) | |
{ | |
vecChannelOrder[i] = i; | |
} | |
// Generate 16 random addresses | |
srand(seed); | |
unsigned int address[16]; | |
for (i = 0; i < 16; i++) | |
{ | |
address[i] = GenerateRandomAddress(); | |
} | |
// Use `FindChannel` to allocate a channel for each address | |
int channelIds[16]; | |
for (i = 0; i < 16; i++) | |
{ | |
int chanID = FindChannel(address[i]); | |
printf("Assigned channel %d to address %u\n", chanID, address[i]); | |
channelIds[i] = chanID; | |
} | |
// Print the channels | |
DumpChannels(); | |
// Try again... This time we should get the same channel ID back. | |
// If not, list all the violations. | |
int violations = 0; | |
for (i = 0; i < 16; i++) | |
{ | |
int chanID = FindChannel(address[i]); | |
int prevChanID = channelIds[i]; | |
if (chanID != prevChanID) | |
{ | |
printf("Address %u got channel ID %d, which is different from previous channel ID %d\n", address[i], chanID, prevChanID); | |
violations++; | |
} | |
} | |
printf("seed=%d, %d violations\n", seed, violations); | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment