[systemd-bugs] [Bug 76746] New: shared: strv_extend_strv is quadratic

[bugzilla-daemon at freedesktop.org]

https://bugs.freedesktop.org/show_bug.cgi?id=76746

          Priority: medium
            Bug ID: 76746
          Assignee: systemd-bugs at lists.freedesktop.org
           Summary: shared: strv_extend_strv is quadratic
        QA Contact: systemd-bugs at lists.freedesktop.org
          Severity: normal
    Classification: Unclassified
                OS: All
          Reporter: mustrumr97 at gmail.com
          Hardware: Other
            Status: NEW
           Version: unspecified
         Component: general
           Product: systemd

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;
}

-- 
You are receiving this mail because:
You are the QA Contact for the bug.
You are the assignee for the bug.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.freedesktop.org/archives/systemd-bugs/attachments/20140328/2e981493/attachment.html>