Bug 76746 - shared: strv_extend_strv is quadratic
Summary: shared: strv_extend_strv is quadratic
Status: RESOLVED WONTFIX
Alias: None
Product: systemd
Classification: Unclassified
Component: general (show other bugs)
Version: unspecified
Hardware: Other All
: medium normal
Assignee: systemd-bugs
QA Contact: systemd-bugs
URL:
Whiteboard:
Keywords:
Depends on: 76745
Blocks:
  Show dependency treegraph
 
Reported: 2014-03-28 16:40 UTC by Hristo Venev
Modified: 2014-04-21 01:04 UTC (History)
0 users

See Also:
i915 platform:
i915 features:


Attachments

Description Hristo Venev 2014-03-28 16:40:54 UTC
Depends on bug 76745

strv_extend_strv(a, b)

Current implementation: O(|a|*|b|+sum(i in b,strlen(i)))

Non-retard implementation: O(|a|+|b|+sum(i in b,strlen(i)))

int strv_extend_strv(char ***a, **b){
    size_t n=strv_length(*a), m=strv_length(b), i;
    
    char **tmp=realloc(*a, sizeof(char*)*(n+m+1));
    if(!tmp) return -ENOMEM;
    *a=tmp;
    for(i=0;i<m;i++){
        tmp[n+i]=strdup(b[i]);
        if(!tmp[n+i]) return -ENOMEM;
    }
    a[n+m]=NULL;
    return 0;
}
Comment 1 David Strauss 2014-03-28 21:32:49 UTC
Please submit patches to the mailing list, not to Bugzilla.
Comment 2 Hristo Venev 2014-03-29 11:44:22 UTC
This is not a patch.
Comment 3 David Strauss 2014-04-06 07:36:20 UTC
Clearly, it's not a patch. But, because you're suggesting a specific code change, I'm asking you to submit the appropriate patches to the mailing list.
Comment 4 Hristo Venev 2014-04-08 12:12:29 UTC
I'm not suggesting this specific implementation. I just think it would be good to have linear strv_extend_strv.
Comment 5 Zbigniew Jedrzejewski-Szmek 2014-04-21 01:04:40 UTC
Eh, strv_extend_strv is only used for things where the number of items is ~O(1). Config dirs are limited by implementation to something like 6, and how many modules can you specify on the command line? If you care to provide a patch, then please do so (on the mailing list), but imo current implementation is sufficient.


Use of freedesktop.org services, including Bugzilla, is subject to our Code of Conduct. How we collect and use information is described in our Privacy Policy.