1 /*
2 gnauralnet_lists.c
3 Methods and variables for creating/accessing linked lists that run GnauralNet
4 Depends on:
5 gnauralnet.h
6 gnauralnet_clocksync.c
7 gnauralnet_lists.c
8 gnauralnet_main.c
9 gnauralnet_socket.c
10
11 Copyright (C) 2008 Bret Logan
12
13 This program is free software; you can redistribute it and/or modify
14 it under the terms of the GNU General Public License as published by
15 the Free Software Foundation; either version 2 of the License, or
16 (at your option) any later version.
17
18 This program is distributed in the hope that it will be useful,
19 but WITHOUT ANY WARRANTY; without even the implied warranty of
20 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
21 GNU General Public License for more details.
22
23 You should have received a copy of the GNU General Public License
24 along with this program; if not, write to the Free Software
25 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
26 */
27
28 #include "gnauralnet.h"
29
30 //Todo:
31 //- make GN_FriendList_NextFriend() and GN_FriendList_RandomFriend() not
32 // have to count so much; they are inefficient, could be speeded up
33 // by using placeholders. The effort is in ensuring the placeholders
34 // never hold deleted info
35
36 //////////////////
37 //Linked FriendList routines:
38 /////////////////////////////////////////////////////
39 //This creates and adds a new GN_Friend to the
40 //end of an existing linked list, or starts new list if
41 //GN_My.FirstFriend == NULL. Most importantly, it gives
42 //the old last Friend's NextFriend the address to the new Friend,
43 //gives this new Friend's PrevFriend address to old lasts Friend,
44 //and sets new Friend's NextFriend to NULL.
45 //It will return NULL if malloc fails
46 //NOTE: Issue 20080115b, ID is a problem, since virgins don't know IDs,
47 //and Invites deliberately don't use them (to avoid abusers that could fake
48 //IDs) the solution is to make sure IP and Port haven't been
49 //seen before either:
GN_FriendList_AddFriend(unsigned int ID,unsigned int IP,unsigned short Port)50 GN_Friend *GN_FriendList_AddFriend (unsigned int ID, //MUST BE IN NET ORDER
51 unsigned int IP, //MUST BE IN NET ORDER
52 unsigned short Port) //MUST BE IN NET ORDER
53 {
54 GN_Friend *curFriend = GN_My.FirstFriend;
55 GN_Friend *lastFriend = NULL;
56
57 GN_My.FriendCount = 1; //starts at 1 to include new one being created
58
59 GN_DBGOUT ("Create new friend entry");
60
61 //find end of list:
62 while (curFriend != NULL)
63 {
64 lastFriend = curFriend;
65 curFriend = curFriend->NextFriend;
66 ++GN_My.FriendCount;
67 }
68
69 GN_DBGOUT_INT ("Current friend count:", GN_My.FriendCount);
70
71 //allot the memory:
72 curFriend = (GN_Friend *) malloc (sizeof (GN_Friend));
73
74 //make sure memory got alotted:
75 if (NULL == curFriend)
76 {
77 return NULL; //no harm done, just failed
78 }
79
80 //zero everything (since most things want to be zero at start):
81 //THIS IS VERY IMPORTANT:
82 memset (curFriend, 0, sizeof (GN_Friend));
83
84 //set up the things I know now (caller must do rest):
85 curFriend->ID = ID;
86 curFriend->IP = IP;
87 curFriend->Port = Port;
88 g_get_current_time (&(curFriend->TimeOfDiscovery));
89
90 //link the new Friend correctly with its Neighbors:
91 curFriend->PrevFriend = lastFriend;
92 curFriend->NextFriend = NULL;
93
94 if (lastFriend != NULL)
95 {
96 lastFriend->NextFriend = curFriend;
97 }
98 else
99 {
100 GN_DBGOUT ("Creating a GN_My.FirstFriend");
101 GN_My.FirstFriend = curFriend;
102 }
103
104 GN_FriendList_FriendCount (); //do this any time one is added or deleted
105 return curFriend;
106 }
107
108 /////////////////////////////////////////////////////
GN_FriendList_DeleteAll()109 void GN_FriendList_DeleteAll ()
110 {
111 GN_Friend *curFriend = GN_My.FirstFriend;
112 GN_Friend *nextFriend;
113 unsigned int count = 0;
114
115 GN_My.FriendCount = GN_My.LoverCount = 0;
116 if (curFriend == NULL)
117 {
118 return;
119 }
120
121 while (curFriend->NextFriend != NULL)
122 {
123 // GN_DBGOUT_INT("Cleanup Friend", count);
124 nextFriend = curFriend->NextFriend;
125 free (curFriend);
126 curFriend = nextFriend;
127 ++count;
128 }
129
130 //still need to get the last one:
131 if (curFriend != NULL)
132 {
133 GN_DBGOUT_INT ("Cleanup Last Friend", count);
134 free (curFriend);
135 ++count;
136 }
137
138 //critical:
139 GN_My.FirstFriend = NULL;
140 GN_DBGOUT_INT ("Friends Deleted:", count);
141 }
142
143 /////////////////////////////////////////////////////
GN_FriendList_DeleteFriend(GN_Friend * curFriend)144 void GN_FriendList_DeleteFriend (GN_Friend * curFriend)
145 {
146 if (curFriend == NULL)
147 {
148 return;
149 }
150
151 //It IS legal to delete the ONLY point, but must be dealt with differently:
152 //NOTE: I tried checking like this:
153 // if (curFriend == GN_My.FirstFriend)
154 //but finally realized that the logic was flawed because is not at all
155 //assumable that the first point is the only one left. This is correct:
156 if (curFriend->NextFriend == NULL && curFriend->PrevFriend == NULL)
157 {
158 free (curFriend);
159 //critical:
160 GN_My.FirstFriend = NULL;
161 GN_My.FriendCount = GN_My.LoverCount = 0;
162 GN_DBGOUT ("Cleanedup Last Friend");
163 return;
164 }
165
166 GN_Friend *prevFriend = curFriend->PrevFriend;
167
168 //first check to see if GN_My.FirstFriend got deleted:
169 if (prevFriend == NULL)
170 {
171 GN_My.FirstFriend = GN_My.FirstFriend->NextFriend;
172 GN_My.FirstFriend->PrevFriend = NULL;
173 }
174 else
175 {
176 //Make previous Friend now link to the next Friend after the one to be deleted:
177 prevFriend->NextFriend = curFriend->NextFriend;
178 if (curFriend->NextFriend != NULL) //i.e., if this point is not the last Friend in the llist:
179 {
180 //Make NextFriend now call the prevFriend PrevFriend:
181 curFriend->NextFriend->PrevFriend = prevFriend;
182 }
183 }
184 //Assuming I've linked everything remaining properly, can now free the memory:
185 free (curFriend);
186 curFriend = NULL; //does this do anything??!
187 GN_FriendList_FriendCount (); //do this any time one is added or deleted
188 }
189
190 /////////////////////////////////////////////////////
191 //this resets GN_My.FriendCount and GN_My.LoverCount, and also returns GN_My.FriendCount
GN_FriendList_FriendCount()192 unsigned int GN_FriendList_FriendCount ()
193 {
194 GN_Friend *curFriend = GN_My.FirstFriend;
195
196 GN_My.FriendCount = 0;
197 GN_My.LoverCount = 0;
198
199 while (curFriend != NULL)
200 {
201 ++GN_My.FriendCount;
202 if (0 != curFriend->RunningID && curFriend->RunningID == GN_My.RunningID)
203 {
204 ++GN_My.LoverCount;
205 }
206 //all list passes need this:
207 curFriend = curFriend->NextFriend;
208 }
209 return GN_My.FriendCount;
210 }
211
212 ///////////////////////////////////////
213 //Gnaurals that know only IP & Port, but not remote IDs, must start with this:
GN_FriendList_Invite(unsigned int IP,unsigned short Port)214 void GN_FriendList_Invite (unsigned int IP, //MUST BE IN NET ORDER
215 unsigned short Port) //MUST BE IN NET ORDER)
216 {
217 //now deal with special-cases, Virgins:
218 //Philosophy is to send an official invitation hello without adding the friend:
219 GN_Friend tmpFriend;
220
221 //zero everything (since most things want to be zero at start):
222 //THIS IS VERY IMPORTANT:
223 memset (&tmpFriend, 0, sizeof (GN_Friend));
224
225 //set up only the things GN_ProcessOutgoingData() needs:
226 tmpFriend.ID = GNAURALNET_UNKNOWN;
227 tmpFriend.IP = IP;
228 tmpFriend.Port = Port;
229
230 GN_DBGOUT ("Requesting a formal invitation:");
231 GN_ProcessOutgoingData (&tmpFriend);
232 }
233
234 /////////////////////////////////////////////////////
235 //This is a very important function because it gets
236 //called any time a packet comes in, it must be fast,
237 //and needs to do some security/accuracy checks.
238 //Returns friend if ID is already on list, NULL otherwise
239 //NOTE: if ID is GNAURALNET_UNKNOWN, this function will
240 //check for IP/Port instead of ID; This is because
241 //Invites may want eventually need to check for IP/Port.
242 //IP/Port can prove you know someone, but can't prove that you don't.
GN_FriendList_GetFriend(unsigned int ID,unsigned int IP,unsigned short Port)243 GN_Friend *GN_FriendList_GetFriend (unsigned int ID, //MUST BE IN NET ORDER
244 unsigned int IP, //MUST BE IN NET ORDER
245 unsigned short Port) //MUST BE IN NET ORDER
246 {
247 GN_Friend *curFriend = GN_My.FirstFriend;
248
249 if (GNAURALNET_UNKNOWN != ID)
250 //first deal with regular, using IDs:
251 {
252 while (curFriend != NULL)
253 {
254 if (curFriend->ID == ID)
255 {
256 if (curFriend->IP != IP || curFriend->Port != Port)
257 {
258 GN_ERROUT ("ID found, but wrong IP/Port!");
259 GN_ERROUT ("Incoming info:");
260 GN_PrintAddressInfo (ID, IP, Port);
261 GN_ERROUT ("FriendList info:");
262 GN_PrintAddressInfo (curFriend->ID, curFriend->IP, curFriend->Port);
263 }
264 return curFriend;
265 }
266 //all list passes need this:
267 curFriend = curFriend->NextFriend;
268 }
269 }
270 else
271 //Now look according to IP/Port:
272 {
273 while (curFriend != NULL)
274 {
275 if (curFriend->IP == IP && curFriend->Port == Port)
276 {
277 GN_DBGOUT ("Gave Friend her valid ID");
278 curFriend->ID = ID; //necessary?
279 return curFriend;
280 }
281 //all list passes need this:
282 curFriend = curFriend->NextFriend;
283 }
284 }
285
286 GN_DBGOUT ("Friend is NOT known");
287 return NULL;
288 }
289
290 /////////////////////////////////////////////////////
291 //This returns a new Friend every call, or NULL if there
292 //are no friends, rotating through the FriendList.
293 //NOTE: I initially try to use a static
294 //GN_Friend holding last place; but that was very dangerous
295 //with the constantly adding and deleting friends. The
296 //approach here is inefficient, but never dangerous.
GN_FriendList_NextFriend()297 GN_Friend *GN_FriendList_NextFriend ()
298 {
299 static unsigned int count = 0;
300 unsigned int i = 0;
301 GN_Friend *curFriend = GN_My.FirstFriend;
302
303 while (curFriend != NULL)
304 {
305 if (i == count)
306 {
307 ++count;
308 return curFriend;
309 }
310 ++i;
311 //all list passes need this:
312 curFriend = curFriend->NextFriend;
313 }
314 //if it got here, there are either no friends or count went over:
315 if (NULL != GN_My.FirstFriend)
316 {
317 // GN_DBGOUT_INT ("NextFriend resetting at:", count);
318 }
319 count = 0;
320 return GN_My.FirstFriend;
321 }
322
323 /////////////////////////////////////////////////////
324 //This returns a random Friend off FriendList, or NULL
325 //if there are less than 2 friends.
326 //Currently there is no ensured good distribution. Tis a total hack
327 //Problems with it include not checking if GN_My.FriendCount is
328 //accurate, not checking if it's a repeat send to same guy, etc.
329 ////20080115: excludeFriend added to not send invites to themselves.
330 //It can be anything if you don't care
GN_FriendList_RandomFriend(GN_Friend * excludeFriend)331 GN_Friend *GN_FriendList_RandomFriend (GN_Friend * excludeFriend)
332 {
333 if (2 > GN_My.FriendCount)
334 {
335 return NULL;
336 }
337
338 unsigned int count = 0;
339 unsigned int i = rand () % GN_My.FriendCount;
340 GN_Friend *curFriend = GN_My.FirstFriend;
341
342 while (curFriend != NULL)
343 {
344 if (i == count)
345 {
346 if (curFriend != excludeFriend)
347 {
348 return curFriend;
349 }
350 else
351 {
352 GN_DBGOUT ("Recursively reentering GN_FriendList_RandomFriend()");
353 //geeze:
354 return GN_FriendList_RandomFriend (excludeFriend);
355 }
356 }
357 ++count;
358 //all list passes need this:
359 curFriend = curFriend->NextFriend;
360 }
361 //Shouldn't get here:
362 GN_DBGOUT_INT ("RandomFriend acting badly:", i);
363 return NULL;
364 }
365