Newsgroups: php.internals Path: news.php.net Xref: news.php.net php.internals:106006 Return-Path: Delivered-To: mailing list internals@lists.php.net Received: (qmail 67732 invoked from network); 20 Jun 2019 19:51:49 -0000 Received: from unknown (HELO mail-io1-f51.google.com) (209.85.166.51) by pb1.pair.com with SMTP; 20 Jun 2019 19:51:49 -0000 Received: by mail-io1-f51.google.com with SMTP id r185so5755473iod.6 for ; Thu, 20 Jun 2019 10:06:46 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:references:in-reply-to:from:date:message-id:subject:to; bh=yNAX1LKNc/u26LSJhjP2WomuR7z4btVc/MQgBYcPnkg=; b=OhP6Rtoz7WNH65TtGfwxF2ZOqQ2KUCMnQUi0M7B/ojh1F+GnHdRTWNxXlCRN29yT48 jB+TrvJJwsNE0I9vWBvEeFwD3d0OjxxyP6JY3ZnKjSuCjcNCXhIllzw1AbC3U09N9P1z Qee5v4IC5pBzLFXliz64HKZ8srsEz/jzCl6UxqMNwK+pn4nNlcqjisBMwnP7ryjjhxjy 6EbB+cDDp3WyjtCoJ2scRgx0zAh+otLqR1KnSHDpNkZP5Wu0RsXctJrnsH38J9l6lSfC JiaEEZscwDWl0H+CevUeM3YCOnURSVGMw3VYCThyc29YrdOdJCa2Wwcg1oJDSBm1Hxdl fyTg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to; bh=yNAX1LKNc/u26LSJhjP2WomuR7z4btVc/MQgBYcPnkg=; b=hszs78yGaMYfyRQFDz8+tovGDTz4y2zQkc3hmp/cGU6U0sRfu1b0FMLbArHxiT62N/ ZuXX/BMTuKVtXiWXv5btCqQoxN9IxJBHef6DVlHUBu6Nntw4p6VtdfMk+KiXbUp2pqlq uKX+nXJS19g+txD1lZ210sPM/qyu2g0PAo+gA8FCGWETv+qGzSfSgcY1JxOJk/UQA6V8 er/xv1GIqOfKuEyHHoLdijMYbnDPg5auDavzJyDiGvHJJLlshbWmZBBT2RgBcaMfeCdV lzC0jsls9WGynmn/SU0HBcv/LaqmyO4Hwad328oa1lz8xJE2avCkuFJHgSCVSdAmsNXY shkg== X-Gm-Message-State: APjAAAVswiQXBfgs/MNh9DH57zAUSbi/NuuWnxziqBdi/ZAO+XlBxgrV u6/tFwtbLC8/kPfzqYab+6RXUnodoYucbZcdw1XFje3DVFc= X-Google-Smtp-Source: APXvYqymu9x83SVd3uQe8e2NZDu7l3HIVP3q2DOQSEJfVpAoBD1moGU1ll6PAevHc8DyLsiRi1Fwk9ilJ9f/voVO65Y= X-Received: by 2002:a5e:8518:: with SMTP id i24mr21735220ioj.149.1561050405476; Thu, 20 Jun 2019 10:06:45 -0700 (PDT) MIME-Version: 1.0 References: In-Reply-To: Date: Thu, 20 Jun 2019 18:06:34 +0100 Message-ID: To: PHP Internals Content-Type: multipart/alternative; boundary="000000000000e51d51058bc45e18" Subject: Re: [PHP-DEV][RFC] Normalize array's "auto-increment" value on copy on write From: rowan.collins@gmail.com (Rowan Collins) --000000000000e51d51058bc45e18 Content-Type: text/plain; charset="UTF-8" On Thu, 20 Jun 2019 at 13:11, Wes wrote: > I left that out of scope for the RFC, for reasons I don't have the > knowledge to describe properly. In the following example, `unset()` should > reset the auto increment to `1` only after the third `unset()` call > > ``` > $array = [0, 1, 2, 3]; // auto increment is 4 because there are "holes" in > the index > unset($array[1]); // auto increment is still 4 > unset($array[2]); // auto increment is still 4 > unset($array[3]); // auto increment is 1, because the index sequence is > contiguous, without holes > ``` > I wonder if it would be possible (and sufficient) to detect if the element being removed was the highest key, and only then look for the new "next" value. The new value can be found either by decrementing the known value until you hit an existing entry (optimal for large arrays with few gaps in the sequence of keys) or by checking all the keys and finding the max (optimal for small but sparse arrays like [12, 145, 65546]). # pseudocode: if ( key_being_unset == array.next_key - 1 ) { if ( short_or_likely_to_be_sparse(array) ) { new_highest_key = max(array.keys); } else { # Find highest unused number, starting from the one just deleted do { new_highest_key = key_being_unset - 1; } while ( not key_exists(array, new_highest_key) ); array.next_key = new_highest_key + 1; } } I've no idea if this is plausible or not. Regards, -- Rowan Collins [IMSoP] --000000000000e51d51058bc45e18--