From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on inbox.vuxu.org X-Spam-Level: X-Spam-Status: No, score=-1.0 required=5.0 tests=DKIM_SIGNED,DKIM_VALID, MAILING_LIST_MULTI,NICE_REPLY_A,RCVD_IN_DNSWL_NONE autolearn=ham autolearn_force=no version=3.4.4 Received: (qmail 1551 invoked from network); 5 Apr 2021 23:23:58 -0000 Received: from minnie.tuhs.org (45.79.103.53) by inbox.vuxu.org with ESMTPUTF8; 5 Apr 2021 23:23:58 -0000 Received: by minnie.tuhs.org (Postfix, from userid 112) id 8C7069CAF0; Tue, 6 Apr 2021 09:23:53 +1000 (AEST) Received: from minnie.tuhs.org (localhost [127.0.0.1]) by minnie.tuhs.org (Postfix) with ESMTP id 470089C883; Tue, 6 Apr 2021 09:23:07 +1000 (AEST) Authentication-Results: minnie.tuhs.org; dkim=pass (2048-bit key; unprotected) header.d=mhorton-net.20150623.gappssmtp.com header.i=@mhorton-net.20150623.gappssmtp.com header.b="Du8UOKdC"; dkim-atps=neutral Received: by minnie.tuhs.org (Postfix, from userid 112) id 86BD29C883; Tue, 6 Apr 2021 09:23:05 +1000 (AEST) Received: from mail-pl1-f176.google.com (mail-pl1-f176.google.com [209.85.214.176]) by minnie.tuhs.org (Postfix) with ESMTPS id 2A1A69C83D for ; Tue, 6 Apr 2021 09:23:03 +1000 (AEST) Received: by mail-pl1-f176.google.com with SMTP id j7so1756327plx.2 for ; Mon, 05 Apr 2021 16:23:03 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=mhorton-net.20150623.gappssmtp.com; s=20150623; h=subject:to:references:from:message-id:date:user-agent:mime-version :in-reply-to:content-transfer-encoding:content-language; bh=NFBI2TDSA6LTDK4K/tdreo2u3TEaA+KJ1p1K4FwaYn0=; b=Du8UOKdC2E0wNrUG3fz2tla19FqiEBUzdBv78XwXyl2D61pijZbQMKoc5kNtrvfgJs QOPtxusbuKNDc/A4TuKk7rkNlDqTsBFraaAT4PsyZiheoRX/JKK4n+y9aXVT3U4lzZwd Ro4Te9OzIxCmr4Uf4E/0fpzyoLVYMa5kg/127KVZFCSZyAFt1BO1EJTpVbWHhaAMYY6U Mmc8mQRVDXdeA4YxHqz2q3+Ez3d1LG6DhFqx5wUTbWaF2RMRjnY4tK5JK2Ys50/c6HpZ 3ZgtFbpv3VEaz8eSRlF/YAH9Q/+uia1lcb011veWPX/TymVkFwSOOKSRFb3a2Y+4vz+o +ZXw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:subject:to:references:from:message-id:date :user-agent:mime-version:in-reply-to:content-transfer-encoding :content-language; bh=NFBI2TDSA6LTDK4K/tdreo2u3TEaA+KJ1p1K4FwaYn0=; b=kAncGrOkJfPg7uZG5Tr47+ZrlZlq7fNPQupsPkh6f6RwrBhK+YdbiLmEWlbqDL8AVG I6BaomnlD7P+tn/5pdsvG6Juz94Oc17Bw1oe0AzohMTBc8M6LJ4YS7C+0NQV3K3iUk8y 1oSgaFi2GlVzmNLcJ6XcqMIg/qk/qccsIPTEMNlabV0yy6zUH1IVbKxQESClCUzD2fpn fnarSlEbHFw7iuPSPSn2z6Nrdpz1z73XhpdjMHFHo29X8rOKzafBVi63zVPK/Y9yT9cQ U9yroF+LvQX1+ujS7PYPU5K2NEu5ki5syjKiFg1XZWcqqGyZRkDThQWrFwxStzNLTV5U msHw== X-Gm-Message-State: AOAM5313u7X6X3KBEzLWox03xjx4vRyXoRu+ZqB0EUW/GdNhzMt3p4R/ wRA7YZEHFSx54R7IHmhdKR4Jgvtr9Cg0pGfC X-Google-Smtp-Source: ABdhPJxT8Zjtrma1SgzPhYy7DUgtXu9nSUNDQr0fsdB5FjXhzuFqY7VWP/o/L69+YBQE6Z3IXvSgEQ== X-Received: by 2002:a17:90b:4c4d:: with SMTP id np13mr1515449pjb.81.1617664981989; Mon, 05 Apr 2021 16:23:01 -0700 (PDT) Received: from [192.168.1.12] (ip72-197-247-231.sd.sd.cox.net. [72.197.247.231]) by smtp.gmail.com with ESMTPSA id w16sm197601pfj.87.2021.04.05.16.23.01 for (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Mon, 05 Apr 2021 16:23:01 -0700 (PDT) To: tuhs@minnie.tuhs.org References: From: Mary Ann Horton Message-ID: <2f984847-0eb4-031b-5691-bc4311da1e47@mhorton.net> Date: Mon, 5 Apr 2021 16:23:00 -0700 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:78.0) Gecko/20100101 Thunderbird/78.7.1 MIME-Version: 1.0 In-Reply-To: Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit Content-Language: en-US Subject: Re: [TUHS] Data structures in Unix editors X-BeenThere: tuhs@minnie.tuhs.org X-Mailman-Version: 2.1.26 Precedence: list List-Id: The Unix Heritage Society mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: tuhs-bounces@minnie.tuhs.org Sender: "TUHS" This is actually what ed, ex, and vi do as well, albeit not with a standard interface. The buffer is an array of integer offsets into a file. Line n in the buffer is pointed at by buffer[n], whose contents are an offset into the temp file. That offset points to a null terminated line of buffer text. When a new line of text is created (or changed) the new line is appended to the temp file and the corresponding offset goes into the buffer array. One big reason for this was that ed was originally written for a 16 bit machine, and buffers didn't fit in memory. This works very well to insert or delete lines, you only have to copy the line references in the buffer array. It's also convenient for undo, since putting things back just means restoring the original array. My enhanced ed (hed at Wisconsin, Portable ed at Bell Labs) had a second array for undo, and a full copy of the array was made before a change. Bill Joy wrote a fancier implementation in vi, where only lines added or deleted were saved, command-specific. Undo knew which command it had to undo and special-cased each one. The big disadvantage to this structure is that ends of lines are not just newline characters. You can't backspace over a newline, or change newlines to something else.     Mary Ann On 4/1/21 5:56 AM, Tony Finch wrote: > David C. Brock wrote: >> I’d like to read similar discussions of the data structures for ed, em, >> ex/vi. If anyone has suggestions of references, they would be very >> welcome! > A curious one is nvi, which uses the Berkeley DB RECNO interface to access > a text file as an array of lines (RECNO = record number). > > Tony.