Summary:ASTERISK-04769: [patch] Add functions CUT and SORT
Reporter:Tilghman Lesher (tilghman)Labels:
Date Opened:2005-08-03 13:04:42Date Closed:2008-01-15 15:45:44.000-0600
Versions:Frequency of
Environment:Attachments:( 0) 20050803__cut_and_sort.diff.txt
( 1) 20050826__cut_and_sort.diff.txt
( 2) vsnprintf_test.c
Description:Part of this is a translation of the application Cut() into the function CUT, but this also adds the function SORT.  I have done this with defines, such that the same file can be compiled in both HEAD and STABLE, for those people who would like the functionality of Sort() without upgrading to HEAD.




   -- Executing NoOp("Zap/29-1", "negone,zero,half,one,two,e,three,pi,hundred,thousand") in new stack
Comments:By: Brian West (bkw918) 2005-08-17 12:58:00

Thats HOT!!!

By: Kevin P. Fleming (kpfleming) 2005-08-24 23:33:23

This one will go into 1.2, if we can get it ready quickly (Mark wants as many function conversions in 1.2 as possible).

I see a few issues in the code, though:

1) The #ifdef stuff will have to be removed before commit, obviously.

2) I don't like seeing the result of strncat() being ignored; can you use ast_build_string() instead? (this also eliminates having to call strlen() in the loop)

3) ast_build_string() could probably also be used in the output loop, instead of repeatedly calling strlen().

4) It's apparent to me that ast_separate_app_args needs to actually allocate the argv[] array, so that it can be used efficiently without requiring large stack-allocated arrays like other apps are already doing (which you've wisely avoided). I'm willing to rework that API function and its callers if you think it would be applicable here...

By: Tilghman Lesher (tilghman) 2005-08-25 00:06:27

1.  There aren't any ifdef's in the code.  If you mean the version checks, they're there to allow the module to be compiled under 1.0, without any editing of the source.  (I've already tried this, and it works.)  I'm not suggesting that this be included in 1.0, as it quite obviously is a new feature, but it is useful to enable people to use the Sort() application in 1.0, should they have such a need.
2.  I don't see why.  strncat() simply returns the first argument, which doesn't tell us anything we don't already know.  There is certainly no need to check that value.
3.  ast_build_string() would require that we reformat the array structures into new structures, before calling the function.  I think it's entirely inappropriate, especially since we aren't doing any format conversions in the output; it's just a concatenation of strings, for which strncat() is quite a bit more efficient.
4.  I don't think it's applicable here.  The elegance of this code is that we're using the qsort(3) library function, which requires us to sort structures in an array, using our custom callback function.  Trying to shoehorn the code into fitting argv[]-type arguments isn't as elegant and could unnecessarily obfuscate the code.

By: Kevin P. Fleming (kpfleming) 2005-08-25 19:29:51

Yeah, I was confusing strncat() with snprintf()... sorry for the misdirection.

By: Kevin P. Fleming (kpfleming) 2005-08-25 20:05:04

OK, I've now tried to commit this, and found a number of problems:

1) You cannot redeclare ENOMEM. All E<FOO> defines should be considered off-limits, since you don't know what the system headers will define.

2) sort_internal will probably cause segfaults if the supplied 'data' pointer points to an empty string, since it assumes it will have found at least one sortable_key.

3) The call to qsort() passes in the count of keys found, not the number of sortable_key structures filled in. The remaining structures (those that were skipped because no value was supplied) will have random data in them. Should keys specified without values should raise an error instead of being skipped, since the syntax specification does not allow them to be optional? The output loop also goes through the all the allocated structures, including the ones that were not populated with keys/values.

4) The output loop in cut_internal _is_ using snprintf and ignoring the result, only to call strlen() to find out what snprintf could have told you. I still think using ast_build_string() would be better here. The output loop in sort_internal may very well be more efficient using ast_build_string() even though it's not formatting the output strings, but that's a minor issue.

By: Tilghman Lesher (tilghman) 2005-08-26 00:21:44

1) Fixed.

2) Fixed.

3) The random data has been fixed by initializing the memory, as in 2.  I'm also going to decrement the count of sets found when the value is missing (or actually, when the ':' is missing).  That should ensure that we only sort the items for which there is complete data.  As this is a function and not an application, I think this is the best way to handle the error condition, instead of returning a blank (which is the only other way I can think of to signal an error in a function).

4) Because the Cut range may be discontinuous (i.e. 1&3-5&7), I don't think there's a better way to do this.  As far as the efficiency of strncat vs. vsnprintf, I'd very much like to see how vsnprintf may be faster, since strncat is basically just a memcpy (and additionally, you'd have to assemble the pieces of the sortable_key structures into a char *[], which is even less efficient.

By: Tilghman Lesher (tilghman) 2005-08-26 00:53:18

Test uploaded, which shows that, even in a case which is unfairly tilted towards snprintf, never mind vsnprintf, strncat() still came out ahead.

The strncat() case is almost identical to the code submitted in the patch, while the snprintf is over-simplified.  If there was any way for vsnprintf to win, it would have with this case, yet strncat() was still twice as fast.

By: Kevin P. Fleming (kpfleming) 2005-08-26 16:00:14

Thanks for building the test program; I ran out of time to do it myself last night.

I've committed this patch to CVS HEAD, thanks!

By: Digium Subversion (svnbot) 2008-01-15 15:45:44.000-0600

Repository: asterisk
Revision: 6422

U   trunk/apps/app_cut.c

r6422 | kpfleming | 2008-01-15 15:45:44 -0600 (Tue, 15 Jan 2008) | 3 lines

convert Cut() into CUT() function (issue ASTERISK-4769)
add SORT() function (issue ASTERISK-4769)