Bug 76746

Summary:	shared: strv_extend_strv is quadratic
Product:	systemd	Reporter:	Hristo Venev <hristo>
Component:	general	Assignee:	systemd-bugs
Status:	RESOLVED WONTFIX	QA Contact:	systemd-bugs
Severity:	normal
Priority:	medium
Version:	unspecified
Hardware:	Other
OS:	All
Whiteboard:
i915 platform:		i915 features:
Bug Depends on:	76745
Bug Blocks:

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.