Loooooong thought...Perfect algorithm for...

[Jose]

I was kinda stuck on this one, not because of lack of solutions but because I think the ones I invented can be improved.
I have an Amiga linked list, each node being a set a arguments to actions (functions in my code) that are executed if certain conditions are met. As the code stands now they can be executed one after the other (first one lauches the second before it's own process exits), all spawed at the same time, or not spawed at all if the same action (function) is still being executed  because of previous meet conditions that lauched it and it still hasn't finished.
Now the problem is one of the possible actions is to change the arguments of the others and of itself, again if certain conditions are meet. But if a previously linked list of actions to execute, with the option to wait for the previous one to finish before starting it's execution (execute one after the other) set, is still executing, changing the arguments of the list will alter the arguments of the previously still executing list.

The solutions, well having 2 lists, but then what about if not 2 but 4, 6 or more conditions (same conditions can be meet various times per second if program is set to that) that use the same list of actions are meet. I think it would be counter productive or not very memory usage friendly to have the same number of lists of arguments as of condtions that are waiting to be or being executed (because like I said, program can be set to have the same condition veryfied varous times per second and corresponding action it launches can take a bit more time to execute. This probalby would only happend very rarely if at all but I want the program not to have this bug).
Other solution would be to copy the list each time a conditions that is associated with it is lauched. This would be better but if condition is meet a lot of times in a short period it's a whole lot of lists to copy. Probably would work (even the 1st one) but I want it to be better.
Yet another one and the one I'm trying to improve right now (or better where I'm stuck...), would be to copy only the nodes wich are to be changed so that if some still executing code still hasn't finished executing all the actions on the list, the list can be started again at the same time if a conditions associated with it is meet before the previously execution of it has finished. But if I change a pointer on the list it will afect the previous execution if it still hasn't reached that part. If I put two pointers, those would only cover 2 actions and so on...
So I though about dynamically creating a list of pointers to all the action arguments on the list to be executed that if changed in time would afect a still running previous execution of the same list. If one list node needs to be changed a copy of it will be made and then the first one substituted by the changed one. The previouly dynamically created list of pointers would still point to nodes corresponding to the  first organization of the list.  But this still wouldn't be the optimall solution. Suppose I have 19 actions set to wait for the previous one to finish before being lauched. To take off one node or modify it and still be able to execute the list as it was before I'd have to create pointers to all  nodes before immediately before the one I want to chage that are set to wait for the previous node on the list to finish, before their execution starts.
I also though about creatign a linked list of all processes spawed for a given function that are executing at the same time but this would also be big trouble.
I wouldn't mind trying it or trying to write code on the fly as I think but in this case if I want to alter somethign I'll have to alter a whole lot of code.... hence I decided to put a post here asking for advice...
You're probably thinking why I don't stop writing by now... :-D

[Jose]

Just took off some errors sorry if someone was reading, it's a small simple to understand piece of text anyway  :roll:

[Fats]

Jose wrote:
Now the problem is one of the possible actions is to change the arguments of the others and of itself, again if certain conditions are meet. But if a previously linked list of actions to execute, with the option to wait for the previous one to finish before starting it's execution (execute one after the other) set, is still executing, changing the arguments of the list will alter the arguments of the previously still executing list.

I would solve this problem by making a list that records the changes that have to be made to the parameters and apply them at the appropriate time. This would mean that you only allocate memory when something has to be remembered.
If you don't know when is the right time to apply the parameter change, you have a bigger problem.

greets,
Staf.

[Jose]

@fats

Cool, someone had the patience to read it :-D
The problem is that a list of actions (or better the arguments and a pointer to the action to be executed) can be executing  multiple times (some of it's actions could be running at the same time, others wait for the previous ones to finish). For example a list of 2 arguments could be spawed with 6 different processes if the associated conditions are met 3 times, if the arguments are not set to wait for the previous to finish. Or if they were set to that the list would be started with 3 diffrent processes, wich would call the 2nd action before exiting the process.
This means that the list can be constatly upgraded and since it's being executed 2 instances or more at the same time there is no time to make the change. I have to keep the information that was there before the change and I want to do it efficiently.

[KThunder]

i dont think you could keep that as a simple linked list. it would be better to set your code up to manage different processes with common data. if you are going to manage different processes with dependant data things can get pretty messy unless you either separate the different parts of your code that arent dependant and interleave code or skip it and just be inefficient.
btw what are you working on, sounds timing dependant also perhaps? more complex than a copper routine.

i hope i read you correctly my son is all overme about email and he likes the icons especially animated ones. hes 8 :lol:  :-D  :-o   :flame:  :smack:  :banana:

[Jose]

@KThunder
Hi.

"It would be better to set your code up to manage different processes with common data."
I can´t cause if the list suffers changes some processes could still need the list in it's previous form".

 "if you are going to manage different processes with dependant data things can get pretty messy unless you either separate the different parts of your code that arent dependant and interleave code or skip it and just be inefficient."
That's the case...

"btw what are you working on, sounds timing dependant also perhaps? more complex than a copper routine."
I'd tell you but then I'd have to kill you :-D It's motion detection that can launch diferent actions if certain conditions are met. I've reached almost 3000 lines by now. Mostly the GUI and VHI support are still lacking but I keep adding options. I'll post here when I finish it.

"i hope i read you correctly my son is all overme about email and he likes the icons especially animated ones. hes 8"
Cool :-)  

[Jose]

I think I'll go for a dynamically created linked list of pointers, that goes like the forward pointers of the main list. If the main list changes I still have the pointers to the nodes like they were before. The main list nodes could have a counter of the number of processes using it so that when it reaches zero the last process using it could deallocate it's memory if it's not in the main list anymore (a bool could be used for that). The question is if the main list of actions is big I'd spend some time traversing it to copy the pointers but I don't think it would take much time.

This is the best solution I've came up with but I don't know if there will be some details I'm missing...

Anyone with a better idea ?

[Jose]

Ok, one improvement, it doesn't need to be a linked list of pointers I think, an array would suffice and would be faster...

[Jose]

BUMP...

I really don't know what decision to make on this one. I fell like all my solutions are unelegant and later I'll have to change alot of code to change it. Maybe someone that pops up on weekends knows something..
One thing is for sure. I'll keep the program halted till I find a decent solution (it's been halted like this before and it was worth the wait..)

Maybe with a :pint: someone will be more willing to help.. :-)

[Karlos]

@Jose

I don't really know what you are trying to accomplish here. I'm not clear on 2 things:

1) Are the functions executed as new processes
2) If so, why is this needed?

Certainly, if your functions take fixed arguments and run sequentially, a simple approach to storing a list of operations is to define a structure that contains a function pointer (to the code to be executed) and the rest of the structure comprises the arguments.

If they are the same layout you can just make an array of these.

[Jose]

@Karlos

Hey!! Haven't seen you here for a while..:-)

"I don't really know what you are trying to accomplish here. "
Fair enouph, I screwed up the first post pretty much..

"I'm not clear on 2 things:

1) Are the functions executed as new processes
2) If so, why is this needed?"

1- Yes
2- Ok.... I'll talk a bit more about what I'm doing...
That is needed beacuse my program doesn't just do motion detection on the whole screen. The user can define an infinite number of areas inside it where detection is independently made. If motion is detected in one of these areas (or any user defined combination of them :-))a corresponding user defined list of actions is executed (hence the linked list with function arguments). This means that a group of actions can start right after the other. Of course the linked lists only contain the arguments to functions (actions) inside the program (maybe later I'll put hooks too..), and diferent lists can contain arguments to the same function.
So far so good but I've put up an option to repeat and start right away the execution of a list if the corresponding condition is detected again, EVEN if the previous one's arguments haven't all been executed.
So far so good too. But...
One of the actions is to change the arguments inside a list of actions. If this happends and the list still hasn't finished executing, it's arguments are changed.


"Certainly, if your functions take fixed arguments and run sequentially, a simple approach to storing a list of operations is to define a structure that contains a function pointer (to the code to be executed) and the rest of the structure comprises the arguments.

If they are the same layout you can just make an array of these.  "

:lol:
I'm amazed myself at how far I've complicated it..

Currently  the code do lauch, keep options on functions and their arguments includes this...

Code: [Select]

struct ActionSet /* Set of action functions */
{ struct ActionFunction *Next; /* 2 create forward linked list (can point 2 an ActionSet too */
  WORD ActionType; /* Must be set to ACTION_SET when dynamically allocated */
  char *ActionSetName; /*NULL terminated string*/
  struct ActionFunction *ActionFunctionList; /* Pointer 2 forward linked list of ActionFunction structures (or ActionSets, can be mixed) */
  LONG PadLong; /* so some arguments have same offset as in ActionFunction */
  BOOL IncludeInReport; /* Include in report when it's corresponding ConditionsToCheck is */
  LONG PreLoad; /* Pre load from disk on ini */
  BOOL Wait4Previous; /* Only try 2 launch after previous has finished */
  BOOL NoExecDupOnSameCond; /* Don't allow spawing of any function if one is already spawed from same ConditionsToCheck and still running */
  BOOL Executing; /* See previous element comment */
  UBYTE SpawPriority; /* Spaq priority in relation to others corresponding 2 same ConditionsToCheck */
  BOOL LaunchIndependently; /* Don't wait till previous action(set) finishes to spawn it */
};
struct ActionFunction
{ struct ActionFunction *Next; /* 2 create forward linked list (can point 2 an ActionSet too */
  WORD ActionType; /* Must be set to ACTION_FUNCTION when dynamically allocated */
  char *ActionFunctionName;
  void (*FunctionPtr)(); /* Ptr 2 action function */
  APTR FuncArguments; /* Ptr 2 structure with function arguments (defined internally in each function, starts with MinArgs) */
  BOOL IncludeInReport; /* Include in report when it's corresponding ActionSet (if exists) and ConditionsToCheck are */
  BOOL PreLoad; /* Pre load from disk on ini */
  BOOL Wait4Previous; /* If set will only try 2 launch after previous has finished */
  /* Global definitions */
  struct GlobalFMLstNode *GFMLstNd; /* Ptr 2 list 2 check general info on function behaviour */
  BOOL GlobalNoSpawIfExecuting /* Don't spaw if one is running */
  BOOL GlobalSpawLaterIfExecuting; /* If false and one is executing won't do anything, else will add to WaitList */
  /* Definitions 4 ConditionsToCheck ActionFunction is in */
  BOOL NoExecDupOnSameCond; /* Don't spaw another if one spawed from same ConditionsToCheck is already executing */
  BOOL LaunchIndependently; /* Don't wait till previous action(set) finishes to spawn it */
  BOOL Executing; /* If the action was spawed on a previous detection and is still running */
  UBYTE SpawPriority; /* Spaw priority in relation to others corresponding 2 same ConditionsToCheck */
  BYTE AlignByte; /* To align structure (faster) */
};
struct MinArgs /* Minimal arguments to function, most functions have their own extended version starting with MinArgs */
{ struct Message ArgMsg;
  WORD Type; /* 4 manager 2 recognize it when message is returned */
  LONG Size; /* Size of function's argument structure (= sizeof(struct MinArg) if not extended) */
  /* Internal for ActionManager to do report management */
  BOOL AllowTimeOut; /* Some functions might run continuously, when TRUE GUI doesn't allow timeouts to be set */
  struct timeval TimeOutVal; /* Time till timeout is considered */
  struct timerequest *TimeOutTReq; /* Ptr to timerequest that triggers timeout on ActionManager, so that it cancels it if function ReplyMsg() first (thus no timeout ) */
  BOOL DoReport; /* How Act was called so that next waiting actions (set 2 Wait4Previous) 2 know */
  struct ActionReport *ActsRep; /* Ptr to struct with report info 4 function 2 fill results */
  LONG StopSignal; /* In case function can/should be able 2 be stoped */
  BOOL (*ActNext) (struct ActionFunction *ActionList); /* 2 launch next action if it's set 2 Wait4Previous */
};


[Jose]

BTW I got more than 3000 lines of code and most stuff works well. Various detection algorithms are included, more or less simple, but they include options on minimal size and height, minimal color difference...etc..

There I've finally told my idea :-)